A double-linked list is a linked list in which each node not only links to the next one, but also to the previous one. The main advantage of a double-linked list is that items can not only be easily added and removed at the head of the list, but also at the tail. Moreover, the linked list can be searched in two directions.

An implementation of a double-linked list is given below. It includes not only adding and removing nodes at the head and tail, but also finding a node with a particular value, and inserting a value after a node. This code is quite long, but mostly straightforward. The main thing to learn from it is that you have to be careful when adding or removing nodes, as this may impact many of the references in the linked list.

class DoubleNode:
    def __init__( self, value, prevnode, nextnode ):
        self.value = value
        self.prevnode = prevnode
        self.nextnode = nextnode
        
class DoubleLinkedList:
    def __init__( self ):
        self.head = None
        self.tail = None
    def addhead( self, value ):
        node = DoubleNode( value, None, self.head )
        self.head = node
        secondnode = self.head.nextnode
        if secondnode != None:
            secondnode.prevnode = self.head
        else:
            self.tail = self.head
    def addtail( self, value ):
        node = DoubleNode( value, self.tail, None )
        self.tail = node
        penultnode = self.tail.prevnode
        if penultnode != None:
            penultnode.nextnode = self.tail
        else:
            self.head = self.tail
    def removehead( self ):
        if self.head != None:
            self.head = self.head.nextnode
            if self.head != None:
                self.head.prevnode = None
            else:
                self.tail = None
    def removetail( self ):
        if self.tail != None:
            self.tail = self.tail.prevnode
            if self.tail != None:
                self.tail.nextnode = None
            else:
                self.head = None
    def find( self, value ):
        node = self.head
        while node != None:
            if node.value == value:
                return node
            node = node.nextnode
        return None
    def insert( self, node, value ):
        if node == None:
            self.addhead( value )
        elif node.nextnode == None:
            self.addtail( value )
        else:
            newnode = DoubleNode( value, node, node.nextnode )
            node.nextnode = newnode
            newnode.nextnode.prevnode = newnode
            
dll = DoubleLinkedList()
dll.addhead( 2 )
dll.addhead( 1 )
dll.addtail( 3 )
dll.addtail( 4 )

cur = dll.head
while cur != None:
    print( cur.value )
    cur = cur.nextnode
    
for i in range( 6 ):
    if dll.find( i ):
        print( i, "found" )
    else:
        print( i, "not found")
        
node = dll.find( 3 )
dll.insert( node, 10 )

Exercise: Add some code to add extra nodes to the double-linked list, remove some nodes, and traverse the double-linked list from tail to head.

As I said, quite a bit of code is needed to ensure that all the links remain correct. When nodes are added to the head of the list, not only the new node must be created, but the second node also must be updated. When nodes are added to the tail, also the penultimate node must be updated. Special care must be taken to deal with a double-linked list with no nodes or with just one node: any updates affect both the head and the tail. Even more updates must be made when inserting nodes in the linked list.

One point of criticism that can be given with respect to the code is that in principle it is possible to call the insert() method with a node which is not actually in the double-linked list. There are various ways to solve this. Probably the best is to maintain, next to the head and tail references, also a current reference which is positioned at some node in the double-linked list. Using new methods, the current reference can be moved forward and backward through the list. Inserting is only possible after the node that is indicated by current. This is similar to how file pointers are used when overwriting parts of a binary file (see the corresponding chapter). I did not add this approach to the code above, as it would make the code even longer as more references must be maintained.

What you learned

In this chapter, you learned about:

• Linking objects
• Single-linked lists
• Double-linked lists