Table of Contents

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.