Introduction to Doubly Linked List
A doubly linked list is a data structure that consists of a sequence of elements, where each element points to both its previous and next elements in the sequence. Unlike a singly linked list, where elements only point to the next element, doubly linked lists allow for easy traversal in both forward and backward directions.
Structure of Doubly Linked List
The basic building block of a doubly linked list is a node. Each node contains three fields:
- Data: Holds the actual data or value of the node.
- Next: Points to the next node in the sequence.
- Previous: Points to the previous node in the sequence.
Operations on Doubly Linked List
Doubly linked lists support various operations:
- Insertion: Adding a new node to the list.
- Deletion: Removing a node from the list.
- Traversal: Iterating through the list in both forward and backward directions.
- Search: Finding a specific element in the list.
- Update: Modifying the value of a node.
Advantages of Doubly Linked List
- Efficient traversal in both directions.
- Easy insertion and deletion operations at both ends.
- Supports bidirectional iteration.
Disadvantages of Doubly Linked List
- Increased memory usage due to storing both previous and next pointers.
- Complexity in implementation compared to singly linked lists.
Implementation Example
// Sample code demonstrating doubly linked list implementation
// (Implementation details may vary based on the programming language)
class Node {
constructor(data) {
this.data = data;
this.next = null;
this.prev = null;
}
}
class DoublyLinkedList {
constructor() {
this.head = null;
this.tail = null;
}
// Methods for insertion, deletion, traversal, search, and update
// ...
}
This is a basic example, and the actual implementation may involve additional features and error handling.
Conclusion
In conclusion, a doubly linked list provides efficient bidirectional traversal but comes with increased complexity in implementation and higher memory usage. Understanding its structure and operations is essential for effectively utilizing this data structure in various applications.
// Doubly Linked List Node Structure
struct Node {
data
prev
next
}
// Doubly Linked List Initialization
function initializeDoublyLinkedList() {
head = null
tail = null
}
// Doubly Linked List Node Insertion at the Beginning
function insertAtBeginning(data) {
newNode = createNode(data)
if (isEmpty()) {
head = newNode
tail = newNode
} else {
newNode.next = head
head.prev = newNode
head = newNode
}
}
// Doubly Linked List Node Insertion at the End
function insertAtEnd(data) {
newNode = createNode(data)
if (isEmpty()) {
head = newNode
tail = newNode
} else {
newNode.prev = tail
tail.next = newNode
tail = newNode
}
}
// Doubly Linked List Node Insertion after a Given Node
function insertAfterNode(prevNode, data) {
if (prevNode == null) {
return // Error: Previous node cannot be null
}
newNode = createNode(data)
newNode.next = prevNode.next
newNode.prev = prevNode
if (prevNode.next != null) {
prevNode.next.prev = newNode
}
prevNode.next = newNode
}
// Doubly Linked List Node Deletion from the Beginning
function deleteFromBeginning() {
if (isEmpty()) {
return // Error: List is empty
}
if (head == tail) {
head = null
tail = null
} else {
head = head.next
head.prev = null
}
}
// Doubly Linked List Node Deletion from the End
function deleteFromEnd() {
if (isEmpty()) {
return // Error: List is empty
}
if (head == tail) {
head = null
tail = null
} else {
tail = tail.prev
tail.next = null
}
}
// Doubly Linked List Node Deletion by Node Reference
function deleteNode(nodeToDelete) {
if (nodeToDelete == null) {
return // Error: Node to delete cannot be null
}
if (nodeToDelete == head) {
deleteFromBeginning()
} else if (nodeToDelete == tail) {
deleteFromEnd()
} else {
nodeToDelete.prev.next = nodeToDelete.next
nodeToDelete.next.prev = nodeToDelete.prev
}
}
// Doubly Linked List Search by Data
function search(data) {
current = head
while (current != null) {
if (current.data == data) {
return current
}
current = current.next
}
return null // Node with given data not found
}
// Doubly Linked List Display Forward
function displayForward() {
current = head
while (current != null) {
print(current.data)
current = current.next
}
}
// Doubly Linked List Display Backward
function displayBackward() {
current = tail
while (current != null) {
print(current.data)
current = current.prev
}
}
// Doubly Linked List Helper Function to Check if Empty
function isEmpty() {
return head == null
}
// Helper Function to Create a New Node
function createNode(data) {
newNode = new Node()
newNode.data = data
newNode.prev = null
newNode.next = null
return newNode
}
// Example Usage
initializeDoublyLinkedList()
insertAtBeginning(1)
insertAtEnd(2)
insertAfterNode(head, 3)
displayForward()
displayBackward()
// Circular Doubly Linked List Node Structure
struct Node {
value
prev
next
}
// Circular Doubly Linked List Initialization
function initializeCircularDoublyLinkedList() {
lastNode = null
}
// Traversing the List Forwards
function traverseForwards(someNode) {
node = someNode
do {
// Do something with node.value
node = node.next
} while (node ≠ someNode)
}
// Traversing the List Backwards
function traverseBackwards(someNode) {
node = someNode
do {
// Do something with node.value
node = node.prev
} while (node ≠ someNode)
}
// Inserting a Node After a Given Node
function insertAfter(node, newNode) {
newNode.next = node.next
newNode.prev = node
node.next.prev = newNode
node.next = newNode
}
// Inserting an Element at the End
function insertEnd(list, node) {
if (list.lastNode == null) {
node.prev = node
node.next = node
} else {
insertAfter(list.lastNode, node)
}
list.lastNode = node
}
// Removing a Node
function remove(list, node) {
if (node.next == node) {
list.lastNode = null
} else {
node.next.prev = node.prev
node.prev.next = node.next
if (node == list.lastNode) {
list.lastNode = node.prev
}
}
destroy node
}
// Advanced Concepts: Asymmetric Doubly Linked List
// Inserting a Node Before Another Node
function insertBefore(node, newNode) {
if (node.prev == null) {
error("The node is not in a list")
}
newNode.prev = node.prev
atAddress(newNode.prev) = newNode
newNode.next = node
node.prev = addressOf(newNode.next)
}
// Inserting a Node After Another Node
function insertAfter(node, newNode) {
newNode.next = node.next
if (newNode.next != null) {
newNode.next.prev = addressOf(newNode.next)
}
node.next = newNode
newNode.prev = addressOf(node.next)
}
// Removing a Node in an Asymmetric Doubly Linked List
function remove(node) {
atAddress(node.prev) = node.next
if (node.next != null) {
node.next.prev = node.prev
}
destroy node
}
// Example Usage
initializeCircularDoublyLinkedList()
node1 = createNode(1)
insertEnd(node1)
node2 = createNode(2)
insertEnd(node2)
insertAfter(node1, createNode(3))
traverseForwards(node1)
remove(node1)
traverseBackwards(node2)