A doubly linked list is a sequence of nodes where each node contains references to both the next and the previous node, allowing traversal in both directions.
Insert: Enter a position and value, then click "Insert" to add a node at that position.
Remove Start: Click "Remove Start" to delete the first node (head) of the list.
Remove End: Click "Remove End" to delete the last node (tail) of the list.
Bidirectional Arrows: Notice the two-way arrows showing both next and prev pointers.
Visualization: Watch how both prev and next pointers update during insertions and deletions.
Insert: Add a node at a specified position
Remove: Delete nodes from the start or end
Traversal: Traverse forward and backward using next/prev pointers
Access by Index: O(n) - Traverse from head or tail (can optimize by choosing closer end).
Search: O(n) - Linear traversal in either direction.
Insert at Head/Tail: O(1) - Direct pointer manipulation with head/tail references.
Insert at Position: O(n) - Traverse to position, then O(1) pointer updates.
Delete with Node Reference: O(1) - Direct access to prev and next pointers.
Delete at Position: O(n) - Traverse to position, then O(1) removal.
Space Complexity: O(n) - Extra pointer per node compared to singly linked list.
vs Singly Linked List: DLL allows bidirectional traversal and O(1) deletion with node reference; uses more memory (two pointers per node).
vs Array: DLL has O(1) insertion/deletion at known positions; arrays have O(1) random access but O(n) middle insertion/deletion.
vs Deque: DLL can insert/delete anywhere; deque typically restricts to ends only but may use array for better cache performance.
vs Circular List: DLL has distinct head/tail; circular list connects tail to head, useful for round-robin scheduling.
Best Use Case: LRU caches, browser history (back/forward), undo/redo operations, and when bidirectional traversal is needed.
LRU Cache: Least Recently Used caches use doubly linked lists for O(1) access and reordering of recently accessed items.
Browser Navigation: Web browsers use DLL to implement back/forward buttons, enabling bidirectional history traversal.
Undo/Redo Systems: Applications maintain edit history as a DLL, allowing navigation both backward (undo) and forward (redo).
Text Editors: Cursor movement in text editors uses DLL-like structures for efficient character insertion and navigation.
Music Player: Media players implement previous/next track functionality using doubly linked playlists.
Thread Scheduler: Operating systems maintain ready queues as DLLs for efficient process addition, removal, and priority changes.
Memory Allocation: Free memory blocks are often managed in doubly linked lists for efficient allocation and coalescing.
Navigation Systems: GPS route planners use DLL-like structures to allow users to review previous and upcoming waypoints.
LRU Cache: Combine hash map with DLL for O(1) get/put; most recently used moves to head, evict from tail.
Flatten Multilevel List: Use prev/next and child pointers; DFS to flatten while maintaining connections.
Browser History: Navigate back/forward through pages using prev/next pointers with current position tracking.
Delete Node in O(1): Given node reference, copy next node's data and delete next (except for tail).
Reverse in Groups: Reverse k nodes at a time using prev pointers for efficient reconnection.
Design Text Editor: Use DLL for cursor operations; efficient insert/delete at cursor position with prev/next access.
All O(1) Data Structure: Combine hash maps with DLL to track min/max frequencies with O(1) operations.
/* Doubly linked list in C (conceptual) */
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node* prev;
struct Node* next;
} Node;
Node* create_node(int v) {
Node* n = malloc(sizeof(Node));
n->data = v; n->prev = n->next = NULL; return n;
}
void push_front(Node** head, int v) {
Node* n = create_node(v);
if (*head) { n->next = *head; (*head)->prev = n; }
*head = n;
}
void pop_front(Node** head) {
if (!*head) return;
Node* tmp = *head;
*head = (*head)->next;
if (*head) (*head)->prev = NULL;
free(tmp);
}
int main() {
Node* head = NULL;
push_front(&head, 1);
push_front(&head, 2);
pop_front(&head);
for (Node* cur = head; cur; cur = cur->next) printf("%d ", cur->data);
printf("
");
return 0;
}