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