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
//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
.
- If a match is found, return
- 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
).
- The target value is found (return
//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?