Doubly Linked List Operations
*The animation illustrates only insertion in the middle. Once you understand this operation visually, it will be easy to understand all other operations explained below.
Overview
Insertion: - it can be done in different positions - at the start, at the end or anywhere in-between (mid).
Insertion at the beginning: Add a new node at the front (head) of the list. Connect the new node to the current head, and update the previous head's link to point back to the new node.
At the end: Add a new node at the end (tail) of the list. Connect the new node to the current tail, and update the previous tail's link to point forward to the new node.
In the middle: Insert a new node between two existing nodes. Adjust the links of the neighboring nodes to include the new node.
Deletion: - the opposite of insertion, respectively can be done in the same positions as insertion.
Deletion from the beginning: Remove the first node (head) from the list. Update the head link to point to the next node, and set the new head's previous link to null.
From the end: Remove the last node (tail) from the list. Update the tail link to point to the previous node, and set the new tail's next link to null.
From the middle: Remove a node from between two existing nodes. Adjust the links of the neighboring nodes to bypass the removed node.
Traversal:
Traverse forward: Begin from the head and visit each node by following the next links until you reach the tail.
Traverse backward: Start from the tail and visit each node by following the previous links until you reach the head.
Search:
Search for a specific value: Traverse the list either forward or backward, examining the data in each node until you find the desired value.
Doubly linked lists provide efficient backward traversal and allow easier insertion and deletion operations at both ends of the list compared to singly linked lists. However, they require more memory to store the additional previous links. Doubly linked lists are beneficial in scenarios where you need to navigate the list in both directions or frequently perform insertions and deletions at both ends.
Code
class Node:
def __init__(self, data):
self.data = data
self.prev = None
self.next = None
class DoublyLinkedList:
def __init__(self):
self.head = None
def insert(self, data):
new_node = Node(data)
if self.head is None:
self.head = new_node
else:
current = self.head
while current.next:
current = current.next
current.next = new_node
new_node.prev = current
def remove(self, data):
current = self.head
while current:
if current.data == data:
if current.prev:
current.prev.next = current.next
else:
self.head = current.next
if current.next:
current.next.prev = current.prev
break
current = current.next
class Node {
constructor(data) {
this.data = data;
this.prev = null;
this.next = null;
}
}
class DoublyLinkedList {
constructor() {
this.head = null;
}
insert(data) {
const new_node = new Node(data);
if (!this.head) {
this.head = new_node;
} else {
let current = this.head;
while (current.next) {
current = current.next;
}
current.next = new_node;
new_node.prev = current;
}
}
remove(data) {
let current = this.head;
while (current) {
if (current.data === data) {
if (current.prev) {
current.prev.next = current.next;
} else {
this.head = current.next;
}
if (current.next) {
current.next.prev = current.prev;
}
break;
}
current = current.next;
}
}
}
class Node {
int data;
Node prev;
Node next;
Node(int data) {
this.data = data;
this.prev = null;
this.next = null;
}
}
class DoublyLinkedList {
Node head;
void insert(int data) {
Node new_node = new Node(data);
if (head == null) {
head = new_node;
} else {
Node current = head;
while (current.next != null) {
current = current.next;
}
current.next = new_node;
new_node.prev = current;
}
}
void remove(int data) {
Node current = head;
while (current != null) {
if (current.data == data) {
if (current.prev != null) {
current.prev.next = current.next;
} else {
head = current.next;
}
if (current.next != null) {
current.next.prev = current.prev;
}
break;
}
current = current.next;
}
}
}
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* prev;
struct Node* next;
};
struct Node* head = NULL;
void insert(int data) {
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
new_node->data = data;
new_node->prev = NULL;
new_node->next = NULL;
if (head == NULL) {
head = new_node;
} else {
struct Node* current = head;
while (current->next != NULL) {
current = current->next;
}
current->next = new_node;
new_node->prev = current;
}
}
void remove(int data) {
struct Node* current = head;
while (current != NULL) {
if (current->data == data) {
if (current->prev != NULL) {
current->prev->next = current->next;
} else {
head = current->next;
}
if (current->next != NULL) {
current->next->prev = current->prev;
}
free(current);
break;
}
current = current->next;
}
}
class Node {
public $data;
public $prev;
public $next;
public function __construct($data) {
$this->data = $data;
$this->prev = null;
$this->next = null;
}
}
class DoublyLinkedList {
public $head;
public function __construct() {
$this->head = null;
}
public function insert($data) {
$new_node = new Node($data);
if ($this->head === null) {
$this->head = $new_node;
} else {
$current = $this->head;
while ($current->next !== null) {
$current = $current->next;
}
$current->next = $new_node;
$new_node->prev = $current;
}
}
public function remove($data) {
$current = $this->head;
while ($current !== null) {
if ($current->data === $data) {
if ($current->prev !== null) {
$current->prev->next = $current->next;
} else {
$this->head = $current->next;
}
if ($current->next !== null) {
$current->next->prev = $current->prev;
}
break;
}
$current = $current->next;
}
}
}