Linked List¶
Una linked list è un modo diverso di memorizzare una sequenza di elementi. Può essere vista come un albero unario, ovvero un albero in cui ogni nodo, eccetto l’unica foglia, ha un solo figlio. La memorizzazione di una linked list differisce da quello di una list standard per il fatto che gli elementi sono memorizzati in memoria non in modo contiguo. Per esempio, consideriamo la collezione di elementi mostrati in Figura 1. Questi elementi sono collegati, memorizzando per ciascuno l’indirizzo di memoria del successivo (che nella terminologia dell’albero unario corrisponde all’unico figlio), come mostrato in Figura 2.
Figura 1: Elementi della lista in memoria
Figura 2: Posizionamento relativo mantenuto da link espliciti.
La posizione del primo elemento della lista deve essere esplicitamente mantenuta. A partire da quella possiamo accedere a tutti gli altri. Questo elemento corrisponde alla testa della lista. L’ultimo elemento della lista ha bisogno di sapere che non ci sono altri elementi successivi (che è una foglia).
Se vogliamo implementare una coda, dando un’implementazione diversa e più efficiente rispetto a quella che abbiamo visto con le liste standard, possiamo implementarla attraverso una linked list, mantenendo sia il primo elemento della lista che l’ultimo. In questo modo è facile implementare sia l’accodamento che l’estrazione in O(1) tempo. Infatti, assumendo che la testa corrisponda all’ultimo elemento inserito e che la coda della lista contenga il primo elemento inserito, l’estrazione ritorna l’ultimo elemento della lista mentre l’accodamento effettua semplicemente un add come spiegato di seguito, aggiungendo un elemento in testa e spostando la testa dell’intera lista al nuovo elemento.
La classe Node¶
Come per l’albero, l’entità node è il mattone di base per costruire la nostra lista. Listing 1 mostra la classe corrispondente, con i relativi metodi per accedere.
Listing 1
class Node:
def __init__(self,initdata):
self.data = initdata
self.next = None
def getData(self):
return self.data
def getNext(self):
return self.next
def setData(self,newdata):
self.data = newdata
def setNext(self,newnext):
self.next = newnext
Creiamo un oggetto Node come al solito.
>>> temp = Node(93)
>>> temp.getData()
93
Il valore None è importante per indicare che siamo in una foglia, ovvero che non c’è nessun successore. Nel costruttore, chiaramente stiamo creando una lista (o albero unario) con un solo elemento (una sola foglia) è quindi next è impostato a
None.
Figura 3: Un oggetto Node contiene l’elemento e il riferimento al prossimo
Figura 4: Una rappresentazione tipica per un Node
La classe Linked List¶
La linked list è costruita come collezione di nodi dove ogni nodo è collegato al prossimo con un riferimento esplicito. Listing 2 mostra il costruttore.
Ogni oggetto di tipo LinkedList mantiene un singolo riferimento alla testa della lista.
Listing 2
class LinkedList:
def __init__(self):
self.head = None
L’assegnamento seguente
>>> mylist = LinkedList()
crea la linked list mostrata in Figura 5. La lista che abbiamo visto prima apparirà come mostrato in Figura 6.
Figura 5: Una lista vuota
Figura 6: Una Linked List di interi
Il metodo isEmpty mostrato in Listing 3 controlla se la testa è vuota per decidere se la lista è vuota.
Listing 3
def isEmpty(self):
return self.head == None
Per aggiungere elementi alla nostra lista, dobbiamo implementare add. Il posto più semplice dove inserire un elemento è la testa. In particolare, il nuovo elemento diventa il primo elemento e la lista viene legata a questo.
La linked list mostrata in Figura 6 è stata costruita chiamando il metodo add come segue.
>>> mylist.add(31)
>>> mylist.add(77)
>>> mylist.add(17)
>>> mylist.add(93)
>>> mylist.add(26)
>>> mylist.add(54)
Il metodo add è mostrato in Listing 4. L’ordine è importante. Se le linee 3 e 4 vengono invertite succede ciò che è mostrato in in Figura 8, ovvero tutti i nodi originali vengono persi e non possiamo più accedervi.
Listing 4
def add(self,item):
temp = Node(item)
temp.setNext(self.head)
self.head = temp
Figura 7: Aggiungere un nuovo Node
Figure 8: Risultato dell’inversione di due passi nel metodo add
Listing 5 mostra l’implementazione del metodo size per contare il numero di nodi. Si tratta di una visita. Figura 9 mostra il processo corrispondente.
Listing 5
1 2 3 4 5 6 7 8 | def size(self):
current = self.head
count = 0
while current != None:
count = count + 1
current = current.getNext()
return count
|
Figure 9: Traversing the Linked List from the Head to the End
Listing 6 mostra l’implementazione del metodo search che anch’esso visita la lista.
Listing 6
1 2 3 4 5 6 7 8 9 10 | def search(self,item):
current = self.head
found = False
while current != None and not found:
if current.getData() == item:
found = True
else:
current = current.getNext()
return found
|
Come esempio, consideriamo search passandogli 17.
>>> mylist.search(17)
True
Il processo può essere visto in Figura 10.
Figure 10: Ricerca del valore 17
Listing 7 mostra il metodo remove. Figura 11 mostra l’inizializzazione di previous e current, mentre Figura 12 mostra come cambiano i riferimenti.
Listing 7
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | def remove(self,item):
current = self.head
previous = None
found = False
while not found:
if current.getData() == item:
found = True
else:
previous = current
current = current.getNext()
if previous == None:
self.head = current.getNext()
else:
previous.setNext(current.getNext())
|
Figure 11: Valori iniziali di previous e current
Figure 12: previous e current come si muovono
Una volta che la fase di ricerca nel remove è stata fatta, dobbiamo rimuovere il nodo. Figura 13 mostra il link che deve esser modificato. Se il link è la testa (vedi Figura 14), caso in cui previous è None, dobbiamo modificare la testa.
Figura 13: Rimuovere un elemento dal centro della lista
Figure 14: Rimuovere il primo elemento della lista
Possiamo provare la classe LinkedList in ActiveCode 1.
Il codice completo della classe LinkedList (linkedlistcomplete)
I metodi rimanenti necessari per implementare una coda, append, insert, index e pop sono lasciati come esercizio. Per implementarli ci dobbiamo ricordare dove avvengono i cambiamenti se all’inizio o in fondo, per cui per spendere meno tempo dovremo memorizzare sia l’inizio che il fondo della lista nell’oggetto LinkedList.