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 =NewNodeHow 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 =NewNodeHow 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_refAppending 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
returnHow 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 _sizeTraversing 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.nextDeleting 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_valHow 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 = NoneDelete 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.nextComplete 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.
