Doubly Linked List

    The doubly linked list is an extension of the linked list in which we have two pointer variables so that we can traverse in back-and-forth directions. It contains two pointers conventionally named next and prev . In next , we store the address or object of the next element or node, and in prev, we store the address of the previous object.

    Like a simple linked list, the doubly linked list also stores its element sequentially, so if we want to visit the last element, first, we would have to traverse through all other nodes.

    Some important terminologies of doubly linked lists are:

    • Node: A node is a collection of data values and two pointers next and prev.
    • Next: Next is a pointer that will hold the address or object of the sequential next node.
    • Prev: Prev is a pointer that holds the address or object of the previous node.

    Doubly Linked List (DLL) Representation

    • The first node of the doubly linked list is a head node, and the prev pointer will hold the Null value.
    • Each node of the doubly linked list will contain a data value and two pointers.
    • The next pointer will hold the address of the next node.
    • The last node’s prev variable will contain a Null value.

    DLL Basic Operations

    Here are some operations which we can apply on a Doubly linked list:

    • Insertion
    • Deletion
    • Insert Last
    • Delete last
    • Insert After
    • Forward Traversing
    • Backward Traversing

    Advantages and Disadvantages of DLL

    Advantages

    • With the doubly linked list, we can transverse back and forth directions.
    • The insertion and deletion operations on the doubly linked list are easier. Unlike a simple linked list, here, we do not need to traverse to the predecessor node and store its reference. Rather, in a doubly-linked list, the reference of the predecessor node can be retrieved from the node that we want to delete.

    Disadvantages

    • Each node requires two variables, which require more memory.
    • We have to manage both pointers to make an effective doubly-linked list data structure.

    Doubly-Linked-List Implementation

    Python

    class Node:
        def __init__(self, next=None, prev=None, data=None):
            self.next = next
            self.prev = prev
            self.data = data
    class DoublyLinkedList:
        def __init__(self):
            self.head = None 
        def Inset_at_Beginning(self, data):
            new_node = Node(data = data)
            new_node.next = self.head
            new_node.prev = None 
            if self.head is not None:
                self.head.prev = new_node
            self.head = new_node 
        def Insert_at_Middle(self, prev, data):  
            if prev is None:
                print("No such node")
                return
            new_node = Node(data = data)  
            new_node.next = prev.next
            prev.next = new_node
            new_node.prev = prev
            if new_node.next is not None:
                new_node.next.prev = new_node
        def Insert_at_End(self, data):
            new_node = Node(data = data)
            last = self.head
            new_node.next = None
            if self.head is None:
                new_node.prev = None
                self.head = new_node
                return
            while (last.next is not None):
                last = last.next
            last.next = new_node
            new_node.prev = last
        def delete_list_element (self, data):
            if self.head is None:
                print("list has no element to delete")
                return
            if self.head.next is None:
                if self.head.item == data:
                    self.head = None
                else:
                    print("Item not found")
                return
            if self.head.data == data:
                self.head = self.head.next
                self.head.prev = None
                return
            n = self.head
            while n.next is not None:
                if n.data ==data:
                    break;
                n = n.next
            if n.next is not None:
                n.prev.next = n.next
                n.next.prev = n.prev
            else:
                if n.data == data:
                    n.prev.next = None
                else:
                    print("Element not found")
        def Traverse_complete_llist(self):
            if self.head is None:
                print("List has no element")
                return
            else:
                n = self.head
                while n is not None:
                    print(n.data , " ")
                    n = n.next

    Conclusion

    Unlike a singly linked list, a doubly linked list allows both directions to traverse, which offers efficient operations for both forward and backward navigation. It ensures efficiency and functionality for programmers.

    We hope that the above-mentioned information regarding doubly linked lists, their representation, and their advantages and disadvantages are clear to you.

    Good luck!

    People are also reading: