Doubly Linked List

A doubly linked list is a variation of a linked list in which each node has a reference to both the previous node and the next node. This bidirectional linkage allows for efficient traversal in both directions.

Advantages over Singly Linked List

The main advantage of a doubly linked list over a singly linked list is the ability to traverse the list in both directions. This is useful in many scenarios, especially when you need to access elements in reverse order or when you need to perform operations that require backtracking.

Implementation

To implement a doubly linked list, we can define two classes: Node and DoublyLinkedList.

The Node class represents each individual node in the list. It has three properties: data to store the actual data, prev to store the reference to the previous node, and next to store the reference to the next node.

The DoublyLinkedList class represents the entire linked list. It has one property: head to store the reference to the first node in the list. It also has methods to append elements at the end of the list (append) and display the list (display).

Here is an example of a doubly linked list implementation in Python:

xxxxxxxxxx

linked_list.display()

## Doubly Linked List

​

class Node:

    def __init__(self, data):

        self.data = data

        self.prev = None

        self.next = None

​

​

class DoublyLinkedList:

    def __init__(self):

        self.head = None

​

    def append(self, data):

        new_node = Node(data)

        if not self.head:

            self.head = new_node

        else:

            current = self.head

            while current.next:

                current = current.next

            current.next = new_node

            new_node.prev = current

​

    def display(self):

        current = self.head

        while current:

            print(current.data)

            current = current.next