Home Python Doubly-linked Lists in Python

Doubly-linked Lists in Python

Doubly-linked lists are different from single-linked lists because travel is both ways. The key differentiating factors in a doubly-linked list are the first and last elements because they perform a critical role in this data structure’s function. Therefore, it is common to hear of data being carried from two connecting fields, which are previous and the next.

Also, note that the reference to next in the last element in a double-linked list points to null, which indicates the end of the list. Meanwhile, the previous node’s reference in the first node points to null.

So when looking at a double-linked list, look out for the following three key items:

1. The value of the given node.
2. The link to the previous node.
3. The link to the next node.

How to create a Double-Linked List

The process here is almost the same as that of a singly linked list. Except that here, both the next and previous pointers are essential in creating links for every node. The node has data.

First, lets create a generic node class as follows:

class Node:
  def __init__(self, data):
    self.data =data
    self.next =None
    self.prev =None
    

# creating a new element in a doubly linked list
def createNewElement(self, NewVal):
  NewNode = Node(NewVal)
  NewNode.next =self.head
  if self.head is not None:
    self.head.prev =NewNode
    self.head =NewNode

How to insert a new Node in a Doubly-Linked List

This involves putting a new element between two already existing elements in a linked list. In this case, you have to determine where you want to insert your new node.

#code to insert element (new_val) aftera specified node (prev_node)
def insertElement(self, prev_node, new_val):
    if prev_node is None:
        return
    NewNode =Node(new_val)
    NewNode.next =prev_node.next
    prev_node.next = NewNode
    if NewNode.next is not None:
        NewNode.next.prev =NewNode

How to insert a given element before a specific Node in a Doubly-Linked List

This method can be called when we want to insert our new element before a specified node in a given doubly-linked list.

Lets say we have a linked list with the following elements,

62, 8, 12

When we insert 99 before 8 the new linked list will have the following elements.

62, 99, 8, 12

The complete code for the method is as follows:

# insert an element before a given node
def insertElementBefore(self, head_ref, next_node, new_data):
    # check if the specified next_node is NULL
    if (next_node == None):
        print("the specified next node cannot be NULL")
        return

    # place the data in the new node
    new_node = Node(new_data)

    # make previous of the new node as previous of next node
    new_node.prev = next_node.prev

    # make the previous of the next node as the new node
    next_node.prev = new_node

    # make the next node as next of new node
    new_node.next = next_node

    # alter next of the new node's previous node
    if (new_node.prev != None):
        new_node.prev.next = new_node

    # make it the new head node if the previous of new node is NULL
    else:
        doubly_list.head = new_node

    return head_ref

Appending an element in a Doubly-Linked List

This involves adding a new element at the end of the linked lists. It involves keeping track of the last element in the doubly linked list as it is.

#code to append an item to a doubly linked list -adds element at the end
def appendElement (self, NewVal):
    NewNode =Node(NewVal)
    NewNode.next =None
    if self.head is None:
        NewNode.prev =None
        self.head =NewNode
        return
    last =self.head
    while (last.next is not None):
        last =last.next
    last.next =NewNode
    NewNode.prev =last
    return

How to get the size of a Doubly-Linked List

This section intends to find the size of the given doubly linked list. To do this, we need to traverse a doubly linked list from the head node to the tail node or what is sometimes called the last node.

# function to calculate the size of a doubly linked list
def sizeOfDoublyLinkedList(self,node):
    _size = 0
    while (node != None):
        _size = _size + 1
        node = node.next

    return _size

Traversing a Doubly-Linked List

Traversing a linked list means visiting every node in the entire linked list. Traversing is very common with singly-linked lists and doubly-linked lists. It encompasses moving from the node at the head to the tail’s node.

After visiting the node, some operation is usually carried out, for instance, comparing the data in the node with some search term, inserting a new element before or after the specified node, or even deleting the node entirely.

In this example, we will print the current node. Subsequently, we will check if the current node is the last. If it is not, then we move to the next node till we reach the last node in the linked list.

# traverse a doubly linked list
def traverseDoublyLinkedList(self, node):
    # check if there is a node first before performation the operations
    while (node is not None):
        print(node.data)
        node = node.next

Deleting a node at the beginning of a Doubly-Linked List

It is easy to delete an item in a doubly-linked list from the front. An important check before attempting any delete tricks is to verify any items in the list.

If the number of items in the list is only one, then all you have to do is set the first node to point to None.

However, if the number of items in the list exceeds one, then set the value of the previous reference the node at the starting point to None. But start by making sure to set the value of the starting node to the value of the next node.

# delete head node in a doubly linked list
def deleteElementFromStart(self):
    if self.head is None:
        print("The list is empty")
        return
    temp_val =self.head.next
    self.head = temp_val

How to delete a tail node in a Doubly-Linked List

Just like in deleting a head node, the first check is to ascertain if the list has more than one item, one item, or the list is empty. If the list is empty, we return. But if there is one item in the linked list, all we have to do is set the node to point to None.

In case there is more than one item, we traverse the linked list from the beginning to the end. Subsequently, we identify the previous node relative to the last node then sets its reference to the next node as None.

That’s all we have to do to remove the last item from the list.

# delete tail node in a doubly linked list
def deleteElementFromEnd(self, node):
    if node is None:
        print("The list is empty")
        return
    if node.next is None:
        self.head = None
        return
    new_next = self.head
    while new_next.next is not None:
        new_next = new_next.next
    new_next.prev.next = None

Delete any node from a Doubly-Linked List

Deleting a specific node involves passing the given node to the function. The function will then do several checks before deleting the given element. First, it will check if the linked lists have a head. If there is no head, it returns. Next is to check if there is a node. If the node passed to the function is None, the program returns. The other checks in the sequence include if the head is equivalent to the given node if there is a next node or a previous node relative to the given node. Below is the full implementation of the method.

# delete any node from a doubly linked list
def deleteAnyElement(self,node):
    if self.head is None:
        print("The list is empty")
        return
    if node is None:
        print("There is no node to delete")
        return
    if self.head == node:
        self.head = node.next

    # if the node to deleted is NOT the last node, then  only change next
    if node.next is not None:
        node.next.prev = node.prev

    # if node to be deleted is NOT the head node, then only change the prev
    if node.prev is not None:
        node.prev.next = node.next

Complete Implementation of a Doubly-Linked List

# creating a new element in a doubly linked list
def createNewElement(self, NewVal):
    NewNode = Node(NewVal)
    NewNode.next =self.head
    if self.head is not None:
        self.head.prev =NewNode
    self.head =NewNode

#code to insert element (new_val) between nodes
def insertElement(self, prev_node, new_val):
    if prev_node is None:
        return
    NewNode =Node(new_val)
    NewNode.next =prev_node.next
    prev_node.next = NewNode
    if NewNode.next is not None:
        NewNode.next.prev =NewNode

#code to append to a doubly linked list -adds element at the end
def appendElement (self, NewVal):
    NewNode =Node(NewVal)
    NewNode.next =None
    if self.head is None:
        NewNode.prev =None
        self.head =NewNode
        return
    last =self.head
    while (last.next is not None):
        last =last.next
    last.next =NewNode
    NewNode.prev =last
    return

# function to calculate the size of a doubly linked list
def sizeOfDoublyLinkedList(self,node):
    _size = 0
    while (node != None):
        _size = _size + 1
        node = node.next
    return _size

# insert an element before a given node
def insertElementBefore(self, head_ref, next_node, new_data):
    # check if the specified next_node is NULL
    if (next_node == None):
        print("the specified next node cannot be NULL")
        return

    # place the data in the new node
    new_node = Node(new_data)

    # make previous of the new node as previous of next node
    new_node.prev = next_node.prev

    # make the previous of the next node as the new node
    next_node.prev = new_node

    # make the next node as next of new node
    new_node.next = next_node

    # alter next of the new node's previous node
    if (new_node.prev != None):
        new_node.prev.next = new_node

    # make it the new head node if the previous of new node is NULL
    else:
        doubly_list.head = new_node

    return head_ref

# traverse a doubly linked list
def traverseDoublyLinkedList(self, node):
    # check if there is a node first before performation the operations
    while (node is not None):
        print(node.data)
        # last = node
        node = node.next

# delete head node in a doubly linked list
def deleteElementFromStart(self):
    if self.head is None:
        print("The list is empty")
        return
    temp_val =self.head.next
    self.head = temp_val

# delete tail node in a doubly linked list
def deleteElementFromEnd(self, node):
    if node is None:
        print("The list is empty")
        return
    if node.next is None:
        self.head = None
        return
    new_next = self.head
    while new_next.next is not None:
        new_next = new_next.next
    new_next.prev.next = None

# delete any node from a doubly linked list
def deleteAnyElement(self,node):
    if self.head is None:
        print("The list is empty")
        return
    if node is None:
        print("There is no node to delete")
        return
    if self.head == node:
        self.head = node.next

    # if the node to deleted is NOT the last node, then  only change next
    if node.next is not None:
        node.next.prev = node.prev

    # if node to be deleted is NOT the head node, then only change the prev
    if node.prev is not None:
        node.prev.next = node.next

Testing the Doubly-Linked List

The first step is to create an instance of the doubly_linked_list class. Then subsequently call the method to create the elements. Finally, we call the traverseDoublyLinkedList method that traverses through the entire linked list and prints all the elements.

doubly_list =doubly_linked_list()
doubly_list.createNewElement(12)
doubly_list.createNewElement(8)
doubly_list.createNewElement(62)
doubly_list.traverseDoublyLinkedList(doubly_list.head)

Advantages of a Doubly-Linked List

As opposed to a singly linked list, here, you do not need to store a reference to the previous node when performing operations such as insert and delete. This is because, from the current node, the user can get a reference to the previous node. As a result, there is no traversing to the previous node and storing its reference the way we do in singly-linked lists.

Doubly linked lists can be traversed both ways. The next node’s reference allows for traversing and searching a linked list in a forward direction. On the other hand, a reference to the previous node is needed to traverse the linked list in a backward direction.

Disadvantages of a Doubly-Linked List

Additional steps are needed to perform operations such as deletion and insertion.

In each node, there is an additional reference that needs to be stored. This adds up to the memory consumption when dealing with doubly-linked lists.

Conclusion

This article has been extensive about doubly-linked lists. We talked about implementing a linked list and how various operations are performed in a linked list. These comprised traversing a doubly-linked list, deletion, reversal, and insertion in a doubly-linked list.

Do not forget the advantages we mentioned concerning a doubly linked list over a singly linked list. Most critical is the ability to traverse without storing references to the previous node and the next node in a doubly-linked list.

Besides, this ability to traverse back and forth in a doubly-linked list makes it very easy to carry out operations such as deletion and insertion.

You may also like

Leave a Comment

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More