Doubly Linked List

Introduction

A Doubly Linked List is a linear data structure consisting of nodes where each node contains three components: a data field, a pointer to the next node, and a pointer to the previous node in the sequence. The first node's previous pointer is null, and the last node's next pointer is null, marking the boundaries of the list. It allows bidirectional traversal and supports efficient insertion and deletion operations at both ends or any position without the need to shift elements.

Structure of Doubly Linked List

Data: The value stored in the node.

Next Pointer: A reference to the next node in the list.

Previous Pointer: A reference to the previous node in the list

Representation of Doubly Linked List

Visualization of Structure of Doubly Linked List

Visualization of Doubly Linked List

//dllrepresetation.cpp
struct Node {
int data;
Node* prev;
Node* next;
Node(int d) {
   data = d;
   prev = next = NULL;      
}
};

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

//dllrepresetation.js
class Node {
 constructor(data) {
     this.data = data;
     this.prev = null;
     this.next = null;
 }
}

Operation on Doubly Linked List

Insertion

Deletion

Traversal

Forward Traversal

Star Initialize a pointer (current) to the head of the list.
While (current!=null)
Process the data of the current node.
Move the pointer to the next node (current = current->next).

// forwardtraversalondll.cpp
void forwardTraversal(Node* head) {
Node* curr = head;
while (curr != NULL) {
    cout << curr->data << " ";
    curr = curr->next;
}
}

#forwardtraversalondll.py
def forward_traversal(head):
 curr = head
 while curr is not None:
     print(curr.data, end=" ")
     curr = curr.next

console.log("We're Working");

Backward Traversal

Star Initialize a pointer (current) to the tail of the list.
While (current!=null)
Process the data of the current node.
Move the pointer to the previous node (current = current->prev).

// backwardtraversalondll.cpp
void backwardTraversal(Node* tail) {
Node* curr = tail;
while (curr != NULL) {
    cout << curr->data << " ";
    curr = curr->prev;
}
}

#backwardtraversalondll.py
def backward_traversal(tail):
 curr = tail
 while curr is not None:
     print(curr.data, end=" ")
     curr = curr.prev

console.log("We're Working");

Searching

Start from the head of the linked list.
Check if the current node's data matches the target value:
- If a match is found, return true.
Move to the next node.
Repeat steps 2 and 3 until:
- The target value is found (return true).
- The end of the list is reached (return false).

//searchingondll.cpp
bool searchLinkedList(struct Node* head, int target)
{
while (head != NULL) {
    if (head->data == target) {
        return true;
    }
    head = head->next;
}
return false;
}

#searchingondll.py
def search_linked_list(head, target):
 while head is not None:
     if head.data == target:
         return True  
     head = head.next
 return False

console.log("We're Working");

Doubly Linked List

On this page