Doubly Linked List—Python

We saw in Singly Linked List the benefits of using a linked list over an array. Linked lists are data structures that grow and expand as needed. Not only is it easy to add an element at the beginning or end of a linked list, but it is also easy to insert elements at arbitrary positions within the list. We can also easily remove elements from the linked list when they are no longer needed.

The doubly linked list is a varient of the singly linked list. The main complaint about a singly linked list is that it can only traverse the list in one direction starting at the head and working until it reaches the end of the list. Clients may not notice a performance hit when operating on small lists, but large lists will almost certainly have a performance hit.

Doubly linked lists work by tracking both the next node and previous nodes in the list. Tracking both nodes creates more overhead when inserting or removing from the list, but it allows the list to work in a bi-directional fashion. That can allow for a major performance boost when operating on large lists.

Here is the entire code followed by an explanation as to how it works. Note that the topic is the Doubly Linked List so I won’t be covering the unit testing code in this module, but I did include for those who are interested.

class Node:
    def __init__(self, element=None, next_node=None, prev_node=None):
        self.element = element
        self.next_node = next_node
        self.prev_node = prev_node

    def __str__(self):
        if self.element:
            return self.element.__str__()
        else:
            return 'Empty Node'

    def __repr__(self):
        return self.__str__()


class DoublyLinkedList:
    def __init__(self):
        self.head = Node(element='Head')
        self.tail = Node(element='Tail')

        self.head.next_node = self.tail
        self.tail.prev_node = self.head

    def size(self):
        count = 0
        current = self.head.next_node

        while current is not None and current != self.tail:
            count += 1
            current = current.next_node

        return count

    def insert_front(self, data):
        node = Node(element=data, next_node=self.head.next_node, prev_node=self.head)
        self.head.next_node.prev_node = node
        self.head.next_node = node

    def insert_last(self, data):
        node = Node(element=data, next_node=self.tail, prev_node=self.tail.prev_node)
        self.tail.prev_node.next_node = node
        self.tail.prev_node = node

    def insert(self, data, position):
        if position == 0:
            self.insert_front(data)
        elif position == self.size():
            self.insert_last(data)
        else:
            if 0 < position < self.size():
                current_node = self.head.next_node
                count = 0
                while count < (position - 1):
                    current_node = current_node.next_node
                    count += 1

                node = Node(element=data, next_node=current_node.next_node, prev_node=current_node)
                current_node.next_node.prev_node = node
                current_node.next_node = node
            else:
                raise IndexError

    def remove_first(self):
        self.head = self.head.next_node
        self.head.prev_node = None

    def remove_last(self):
        self.tail = self.tail.prev_node
        self.tail.next_node = None

    def remove(self, position):
        if position == 0:
            self.remove_first()
        elif position == self.size():
            self.remove_last()
        else:
            if 0 < position < self.size():
                current_node = self.head.next_node
                current_pos = 0

                while current_pos < position:
                    current_node = current_node.next_node
                    current_pos += 1

                next_node = current_node.next_node
                prev_node = current_node.prev_node

                next_node.prev_node = prev_node
                prev_node.next_node = next_node
            else:
                raise IndexError

    def fetch(self, position):
        if 0 <= position < self.size():
            current_node = self.head.next_node
            current_pos = 0

            while current_pos < position:
                current_node = current_node.next_node
                current_pos += 1

            return current_node.element
        else:
            raise IndexError


import unittest
from random import randint


class TestDoublyLinkedList(unittest.TestCase):
    names = ['Bob Belcher',
             'Linda Belcher',
             'Tina Belcher',
             'Gene Belcher',
             'Louise Belcher']

    def test_init(self):
        dll = DoublyLinkedList()
        self.assertIsNotNone(dll.head)
        self.assertIsNotNone(dll.tail)
        self.assertEqual(dll.size(), 0)

    def test_insert_front(self):
        dll = DoublyLinkedList()
        for name in TestDoublyLinkedList.names:
            dll.insert_front(name)

        self.assertEqual(dll.fetch(0), TestDoublyLinkedList.names[4])
        self.assertEqual(dll.fetch(1), TestDoublyLinkedList.names[3])
        self.assertEqual(dll.fetch(2), TestDoublyLinkedList.names[2])
        self.assertEqual(dll.fetch(3), TestDoublyLinkedList.names[1])
        self.assertEqual(dll.fetch(4), TestDoublyLinkedList.names[0])

    def test_insert_last(self):
        dll = DoublyLinkedList()
        for name in TestDoublyLinkedList.names:
            dll.insert_last(name)

        for i in range(len(TestDoublyLinkedList.names) - 1):
            self.assertEqual(dll.fetch(i), TestDoublyLinkedList.names[i])

    def test_insert(self):
        dll = DoublyLinkedList()
        for name in TestDoublyLinkedList.names:
            dll.insert_last(name)

        pos = randint(0, len(TestDoublyLinkedList.names) - 1)

        dll.insert('Teddy', pos)
        self.assertEqual(dll.fetch(pos), 'Teddy')

    def test_remove_first(self):
        dll = DoublyLinkedList()
        for name in TestDoublyLinkedList.names:
            dll.insert_last(name)

        for i in range(dll.size(), 0, -1):
            self.assertEqual(dll.size(), i)
            dll.remove_first()

    def test_remove_last(self):
        dll = DoublyLinkedList()
        for name in TestDoublyLinkedList.names:
            dll.insert_last(name)

        for i in range(dll.size(), 0, -1):
            self.assertEqual(dll.size(), i)
            dll.remove_last()

    def test_remove(self):
        dll = DoublyLinkedList()
        for name in TestDoublyLinkedList.names:
            dll.insert_last(name)

        dll.remove(1)

        self.assertEqual(dll.fetch(0), 'Bob Belcher')
        self.assertEqual(dll.fetch(1), 'Tina Belcher')
        self.assertEqual(dll.fetch(2), 'Gene Belcher')
        self.assertEqual(dll.fetch(3), 'Louise Belcher')


if __name__ == '__main__':
    unittest.main()

Node

Like the singly linked list, the doubly linked list begins with a Node class that holds the data contained in the list and references to the previous and next nodes. Here is the code for the Node.

class Node:
    def __init__(self, element=None, next_node=None, prev_node=None):
        self.element = element
        self.next_node = next_node
        self.prev_node = prev_node

    def __str__(self):
        if self.element:
            return self.element.__str__()
        else:
            return 'Empty Node'

    def __repr__(self):
        return self.__str__()

Here is a break down of each methods in the Node class.

__init__

The __init__ method creates the node. All three of its parameters are optional, but basically we are setting the data contained in the node, and building refrences to next_node and previous_node.

def __init__(self, element=None, next_node=None, prev_node=None):
    self.element = element
    self.next_node = next_node
    self.prev_node = prev_node

__str__ and __repr__

I found that there was more work invloved with debugging doubly linked list, so in this version of the Node class, I chose to implement __str__ and __repr__ so that I could easily identify each Node in my debugger.

def __str__(self):
    # Check if self.element is null
    if self.element:
        # Just return the string representation
        # of self.element
        return self.element.__str__()
    else:
        # Otherwise return Empty Node
        # to indicate the node does not
        # hold data
        return 'Empty Node'

# We are just going to reuse the
# code in __str__ here
def __repr__(self):
    return self.__str__()

Doubly Linked List

This is an example of a doubly linked list. It’s not opitmized for the simply fact that we are learning. If you need an optimized list structure, you Python’s list object.

class DoublyLinkedList:
    def __init__(self):
        self.head = Node(element='Head')
        self.tail = Node(element='Tail')

        self.head.next_node = self.tail
        self.tail.prev_node = self.head

    def size(self):
        count = 0
        current = self.head.next_node

        while current is not None and current != self.tail:
            count += 1
            current = current.next_node

        return count

    def insert_front(self, data):
        node = Node(element=data, next_node=self.head.next_node, prev_node=self.head)
        self.head.next_node.prev_node = node
        self.head.next_node = node

    def insert_last(self, data):
        node = Node(element=data, next_node=self.tail, prev_node=self.tail.prev_node)
        self.tail.prev_node.next_node = node
        self.tail.prev_node = node

    def insert(self, data, position):
        if position == 0:
            self.insert_front(data)
        elif position == self.size():
            self.insert_last(data)
        else:
            if 0 < position < self.size():
                current_node = self.head.next_node
                count = 0
                while count < (position - 1):
                    current_node = current_node.next_node
                    count += 1

                node = Node(element=data, next_node=current_node.next_node, prev_node=current_node)
                current_node.next_node.prev_node = node
                current_node.next_node = node
            else:
                raise IndexError

    def remove_first(self):
        self.head = self.head.next_node
        self.head.prev_node = None

    def remove_last(self):
        self.tail = self.tail.prev_node
        self.tail.next_node = None

    def remove(self, position):
        if position == 0:
            self.remove_first()
        elif position == self.size():
            self.remove_last()
        else:
            if 0 < position < self.size():
                current_node = self.head.next_node
                current_pos = 0

                while current_pos < position:
                    current_node = current_node.next_node
                    current_pos += 1

                next_node = current_node.next_node
                prev_node = current_node.prev_node

                next_node.prev_node = prev_node
                prev_node.next_node = next_node
            else:
                raise IndexError

    def fetch(self, position):
        if 0 <= position < self.size():
            current_node = self.head.next_node
            current_pos = 0

            while current_pos < position:
                current_node = current_node.next_node
                current_pos += 1

            return current_node.element
        else:
            raise IndexError

__init__

This doubly linked list implementation makes use of a head and a tail node. We traversing the list, the code will look for either head or tail as a means to detect if we are at the end of the list.

def __init__(self):
    self.head = Node(element='Head')
    self.tail = Node(element='Tail')

    self.head.next_node = self.tail
    self.tail.prev_node = self.head

We pass the strings “Head” and “Tail” as the element data for each of these nodes for debugging purpose. Since Node implements __str__ and __repr__, we will see Heads and Tail in the debugger (at least when using PyCharm).

The next two lines do the work of pointing head and tail at each other. When the list is created, head.next_node is tail. Conversly, tail.prev_node is head. This indicates an empty list.

size

This code inefficient on purpose. A better implementation would use a length varaible and increment or decrment it as Nodes are added and removed. However, in this case, I wanted to show how to traverse a list without the clutter of adding or removing Nodes.

def size(self):
    count = 0
    current = self.head.next_node

    while current is not None and current != self.tail:
        count += 1
        current = current.next_node

    return count

We start by making a count variable and a current variable that points at self.head.next_node. It’s really important that we use self.head.next_node instead of self.head because self.head’s purpose is to mark the beginning of the list, not contain data. If we failed to make this distinction, the size of the list will be off by one.

Now, we are going to traverse the list increment count by one an each iteration of the loop. We should check for None for defensive programming purposes, but the critical part of the loop condition is if current != self.tail. The self.tail Node marks the end of the list and so we do not wish to include it in the size of our list.

insert_front

This method inserts a new Node at the front of the Linked List.

def insert_front(self, data):
    node = Node(element=data, next_node=self.head.next_node, prev_node=self.head)
    self.head.next_node.prev_node = node
    self.head.next_node = node

Nodes inserted at the front of the list need their prev_node to point at self.head and their next_node to point at the Node located at self.head.next_node.

To complete the insertion, we now need to update self.head.next_node.prev_node to point back at the new Node that we created (otherwise, it would still point at self.head). Likewise, we need to update self.head.next_node to point at our new Node.

insert_last

The code for this is almost identical to insert_head with the main difference being that we are working on the tail Node rather than the head Node.

def insert_last(self, data):
    node = Node(element=data, next_node=self.tail, prev_node=self.tail.prev_node)
    self.tail.prev_node.next_node = node
    self.tail.prev_node = node

Once again, we create a new Node. It’s next_node has to point at self.tail and it’s prev_node needs to point at self.tail.prev_node.

To complete the insertion, we need to update self.tail.prev_node.next_node to point at our new Node (otherwise it will continue to point at self.tail). We also need to point self.tail.prev_node at our new Node.

insert

This method handles the insertion of a Node into the middle of the list. Keep in mind that it has to handle four possible cases.

  • Position could be 0 (front of list)
  • Position could be equal to size() (end of list)
  • Position is in the middle of the list
  • Position is size() (out of bounds)
def insert(self, data, position):
    if position == 0:
        # First case, we insert at front
        self.insert_front(data)
    elif position == self.size():
        # Second case, we insert at end
        self.insert_last(data)
    else:
        if 0 < position < self.size():
            # Third case, insert in middle
            current_node = self.head.next_node
            count = 0
            while count < (position - 1):
                current_node = current_node.next_node
                count += 1

            node = Node(element=data, next_node=current_node.next_node, prev_node=current_node)
            current_node.next_node.prev_node = node
            current_node.next_node = node
        else:
            # Fourth case, index out of bounds
            raise IndexError

The comments point out how this code handles each of the possible cases. Let's focus on the insertion. We begin by creating a count variable and current_node variable. Now, we need to traverse the list until we arrive at the node right before the desired position. Each interation of the loop requires us to point current_node at current_node.next_node.

Once we arrive at our destination, we create a new Node. We will point it's next_node at current_node.next_node and its prev_node at current_node. Doing the insertion at this point in the list causes the new node to appear at the position index specified in the method parameters.

To complete the insertion, we point current_node.next_node.prev_node at the new Node (otherwise it would still point at current_node). Likewise, we point current_node.next_node at our new Node.

Again, I should mention that this code is inefficient again. Normally we would make use of the bidirectional capabilities of the list and decide if we want to traverse the list in forward (like we do here) or in reverse. For example, if we are trying insert into a list at size() – 2, it doesn't make sense to start at the head node and traverse forward to find our insertion point when we could start at tail and move backwards.

remove_first

It’s really simple to remove nodes from the head of a doubly linked list.

def remove_first(self):
     self.head = self.head.next_node
     self.head.prev_node = None

You will notice that all we need to do is point self.head at self.head.next_node. Then we just set self.head.prev_node to None so that it doesn’t continue to point at the old self.head. The old Node will get garbage collected by the Python runtime.

remove_last

Removing the tail from the list is just as easy as removing the head.

def remove_last(self):
    self.tail = self.tail.prev_node
    self.tail.next_node = None

In this case, we just point self.tail at self.tail.prev_node. To remove the old Node, we next poitn self.tail.next_node to None. The old Node will get garbage collected by the Python runtime.

remove

Remove needs to handle the same cases that insert has to handle. Otherwise it works by traversing the list of the position to remove and deletes the Node.

def remove(self, position):
    if position == 0:
        # First case, remove at front
        self.remove_first()
    elif position == self.size():
        # Second case, remove from end
        self.remove_last()
    else:
        if 0 < position < self.size():
            # 3rd case, remove at middle
            current_node = self.head.next_node
            current_pos = 0

            while current_pos < position:
                current_node = current_node.next_node
                current_pos += 1

            next_node = current_node.next_node
            prev_node = current_node.prev_node

            next_node.prev_node = prev_node
            prev_node.next_node = next_node
        else:
            # 4th case, invalid position
            raise IndexError

Again, we will focus on the removal part of this code. We begin by traversing the list to find our desired position. This time, we stop at the actual position rather than the position before it. Once we arrive at our desired position, we store current_node.next_node and current_node.prev_node into their respective variables. To remove current_node, we simply need to point next_node.prev_node at prev_node and likewise point prev_node.next_node to next_node. Since there are no longer any references to current_node, it is garbage collected by the Python runtime.

fetch

Our final method is the fetch method, which let’s use retreive items from the Linked List.

def fetch(self, position):
    if 0 <= position < self.size():
        current_node = self.head.next_node
        current_pos = 0

        while current_pos < position:
             current_node = current_node.next_node
             current_pos += 1

        return current_node.element
    else:
        raise IndexError

By now readers should be familiar with how the list is traversed. We simply traverse the list to the desired position and return the Node.element to the caller.

Conclusion

Doubly linked list are a more advance form of linked list that supports bi-directional traversals. Bi-directional navigation is possible because each Node in the linked list stores a refrence to both the next and previous Node in the list.

Our linked list implementation only utilizes forward direction traversal to help keep the implementation simple. However, it would only require a small amount of work to make use of reverse traversals.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s