Liste: liste semplicemente e doppiamente concatenate

5.1 Definizione di una lista e i suoi tipi

Una lista è una struttura dati dinamica composta da elementi (nodi), dove ogni nodo contiene dati e riferimenti ad altri nodi. A differenza degli array, le liste possono cambiare dimensione durante l'esecuzione del programma.

Importante! In questo caso, non stiamo parlando della classe list di Python, stiamo parlando di una struttura dati dalla teoria degli algoritmi.

Tipi di liste:

• Lista semplicemente concatenata (Singly Linked List): Ogni nodo contiene dati e un riferimento al nodo successivo.
• Lista doppiamente concatenata (Doubly Linked List): Ogni nodo contiene dati, un riferimento al nodo successivo e un riferimento al nodo precedente.

5.2 Principio di funzionamento di una lista semplicemente concatenata

Struttura di una lista semplicemente concatenata:

• Nodo (Node): È composto da due parti: i dati e un riferimento al nodo successivo.
• Testa (Head): Puntatore al primo nodo della lista.

Principio di funzionamento:

• Aggiunta di un nodo: Si verifica creando un nuovo nodo e aggiornando il riferimento dell'ultimo nodo al nuovo nodo.
• Rimozione di un nodo: Richiede l'aggiornamento del riferimento del nodo precedente al nodo successivo del nodo da rimuovere.

Esempio di implementazione:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class SinglyLinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node

    def display(self):
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

# Esempio di utilizzo:
sll = SinglyLinkedList()
sll.append(1)
sll.append(2)
sll.append(3)
sll.display()  # Output: 1 -> 2 -> 3 -> None

5.3 Principio di funzionamento di una lista doppiamente concatenata

Struttura di una lista doppiamente concatenata:

• Nodo (Node): È composto da tre parti: i dati, un riferimento al nodo successivo e un riferimento al nodo precedente.
• Testa (Head): Puntatore al primo nodo della lista.
• Coda (Tail): Puntatore all'ultimo nodo della lista (non obbligatorio, ma spesso utilizzato).

Principio di funzionamento:

• Aggiunta di un nodo: Si verifica creando un nuovo nodo e aggiornando i riferimenti dell'ultimo nodo e del nuovo nodo.
• Rimozione di un nodo: Richiede l'aggiornamento dei riferimenti dei nodi precedenti e successivi al nodo da rimuovere.

Esempio di implementazione:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
        self.prev = None

class DoublyLinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node
        new_node.prev = last

    def display(self):
        current = self.head
        while current:
            print(current.data, end=" <-> ")
            current = current.next
        print("None")

# Esempio di utilizzo:
dll = DoublyLinkedList()
dll.append(1)
dll.append(2)
dll.append(3)
dll.display()  # Output: 1 <-> 2 <-> 3 <-> None

5.4 Operazioni principali

Operazioni principali: inserimento, rimozione, ricerca

Inserimento:

• Lista semplicemente concatenata: L'inserimento di un nuovo nodo alla fine della lista richiede di attraversare tutti i nodi fino all'ultimo e l'aggiornamento del riferimento dell'ultimo nodo.
• Lista doppiamente concatenata: L'inserimento di un nuovo nodo alla fine della lista è simile alla lista semplicemente concatenata, ma richiede anche l'aggiornamento del riferimento prev del nuovo nodo al nodo precedente.

Rimozione:

• Lista semplicemente concatenata: La rimozione di un nodo richiede di attraversare la lista fino al nodo che deve essere rimosso e l'aggiornamento del riferimento del nodo precedente al nodo successivo di quello da rimuovere.
• Lista doppiamente concatenata: La rimozione di un nodo richiede l'aggiornamento dei riferimenti next e prev dei nodi adiacenti al nodo da rimuovere.

Ricerca: Attraversamento della lista dalla testa alla coda e confronto dei dati di ogni nodo con il valore ricercato. Complessità temporale — O(n).

5.5 Esempio di utilizzo delle liste

Facciamo un esempio implementando uno stack basato su una lista semplicemente concatenata.

Uno stack può essere facilmente implementato utilizzando una lista semplicemente concatenata, con metodi per aggiungere push e rimuovere pop elementi. Dovrebbe avere 2 metodi:

• push — aggiunta di un nuovo elemento alla fine della lista
• pop — rimozione dell'ultimo elemento dalla fine della lista

Esempio di implementazione:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class Stack:
    def __init__(self):
        self.top = None

    def push(self, data):
        new_node = Node(data)
        new_node.next = self.top
        self.top = new_node

    def pop(self):
        if not self.top:
            return None
        data = self.top.data
        self.top = self.top.next
        return data

    def display(self):
        current = self.top
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

# Esempio di utilizzo:
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
stack.display()  # Output: 3 -> 2 -> 1 -> None
print(stack.pop())  # Output: 3
stack.display()  # Output: 2 -> 1 -> None