AlgoDocs

Doubly Linked List

A bidirectional linear data structure

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

  1. Insertion At Beginning

  2. Insertion At Position

  3. Insertion At Tail

Deletion

  1. Deletion At Beginning

  2. Deletion At Position

  3. Deletion At Tail

Traversal

Forward Traversal

  1. Star Initialize a pointer (current) to the head of the list.

  2. While (current!=null)

  3. Process the data of the current node.

  4. 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

  1. Star Initialize a pointer (current) to the tail of the list.

  2. While (current!=null)

  3. Process the data of the current node.

  4. 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

  1. Start from the head of the linked list.
  2. Check if the current node's data matches the target value:
    • If a match is found, return true.
  3. Move to the next node.
  4. 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");

How is this guide?