Doubly Linked List in Python

Here is round two for linked lists, the doubly linked list. It’s not very much more complex than a singly linked list. Breaking things into cases using the self.count attribute makes the code easier to read and reason about.

class DoublyLinkedList:
    
    class Node:
        def __init__( self, data, prevNode, nextNode ):
            self.data = data
            self.prevNode = prevNode
            self.nextNode = nextNode
        
    def __init__( self, data=None ):
        self.first = None
        self.last = None
        self.count = 0
    def addFirst( self, data ):
        if self.count == 0:
            self.first = self.Node( data, None, None )
            self.last = self.first
        elif self.count > 0:
            # create a new node pointing to self.first
            node = self.Node( data, None, self.first )
            # have self.first point back to the new node
            self.first.prevNode = node
            # finally point to the new node as the self.first
            self.first = node
        self.current = self.first
        self.count += 1
    def popFirst( self ):
        if self.count == 0:
            raise RuntimeError("Cannot pop from an empty linked list")
        result = self.first.data
        if self.count == 1:
            self.first = None
            self.last = None
        else:
            self.first = self.first.nextNode
            self.first.prevNode = None
        self.current = self.first
        self.count -= 1
        return result
    def popLast( self ):
        if self.count == 0:
            raise RuntimeError("Cannot pop from an empty linked list")
        result = self.last.data
        if self.count == 1:
            self.first = None
            self.last = None
        else:
            self.last = self.last.prevNode
            self.last.nextNode = None
        self.count -= 1
        return result
    def addLast( self, data ):
        if self.count == 0:
            self.addFirst(0)
        else:
            self.last.nextNode = self.Node( data, self.last, None )
            self.last = self.last.nextNode
            self.count += 1
    def __repr__( self ):
        result = ""
        if self.count == 0:
            return "..."
        cursor = self.first
        for i in range( self.count ):
            result += "{}".format(cursor.data)
            cursor = cursor.nextNode
            if cursor is not None:
                result += " --- "
        return result
    def __iter__( self ):
        # lets Python know this class is iterable
        return self
    def next( self ):
        # provides things iterating over class with next element
        if self.current is None:
            # allows us to re-iterate
            self.current = self.first
            raise StopIteration
        else:
            result = self.current.data
            self.current = self.current.nextNode
            return result
    def __len__( self ):
        return self.count
    
dll = DoublyLinkedList()
dll.addFirst("days")
dll.addFirst("dog")
dll.addLast("of summer")

assert list( dll ) == ["dog", "days", "of summer" ]
assert dll.popFirst() == "dog"
assert list( dll ) == ["days", "of summer"]
assert dll.popLast() == "of summer"
assert list( dll ) == ["days"]

Leave a Reply

Your email address will not be published. Required fields are marked *