Linked list in Python
Una linked list (nel nostro caso, una doubly linked list )è una struttura dati dove gli elementi sono ordinati linearmente e il loro ordine è dato dai puntatori presenti in ogni elemento della lista.
Di seguito mostrerò l’implementazione di una doubly linked list in Python, dove ogni elemento ha un puntatore all’elemento precedente e un puntatore all’elemento successivo.
Mostrerò, inoltre, l’implementazione di un iteratore per la nostra lista, in modo rendere possibile l’utilizzo del costrutto for di Python anche con la nostra linked list.
class Node: """Linked list node implementation""" def __init__(self, key): self.next = None self.prev = None self.key = key def __str__(self): return "Node("+str(self.key)+")" class LinkedList: """Linked list implementation""" def __init__(self): self.head = None def insert(self, x): if(not isinstance(x, Node)): raise ValueError x.next = self.head if(self.head != None): self.head.prev = x self.head = x def search(self, key): node = self.head while(node != None and node.key != key): node = node.next return node def delete(self, node): if(not isinstance(node, Node)): raise ValueError if(node.prev != None): node.prev.next = node.next else: self.head = node.next if(node.next != None): node.next.prev = node.prev def __iter__(self): return LinkedListIterator(self) class LinkedListIterator: """Linked list iterator implementation""" def __init__(self, linkedList): self.linkedList = linkedList self.currNode = self.linkedList.head def next(self): if(self.currNode == None): raise StopIteration retv = self.currNode self.currNode = self.currNode.next return retv mylist = LinkedList(); for i in xrange(10, 0, -1): mylist.insert(Node(i)) for i in mylist: print i
La prima classe definita, Node, rappresenta ogni elemento della nostra lista.
Successivamente, viene definita la classe LinkedList con i tre metodi fondamentali: insert, search e delete.
Ogni elemento inserito viene posto in prima posizione. La ricerca scorre linearmente la lista, mentre la cancellazione si occupa di aggiornare i puntatori dell’elemento che precede/segue l’elemento cancellato.
Viene infine implementato il metodo speciale __iter__, per consentire la creazione di un iteratore che useremo poi nel for, alla fine del listato.
Per maggiori informazioni su iteratori e costrutto for in Python: Iterators.
Per la lista di ulteriori metodi in grado di emulare le funzionalità di una lista in Python vedi: Emulating container types