Loading...
Dive deep into linked lists - the fundamental dynamic data structures that revolutionize how we store and manipulate data. From basic concepts to advanced implementations, master every aspect with interactive visualizations and comprehensive examples.
Watch how different linked list operations work in real-time. Select a type and see the magic happen!
Before diving into linked lists, you must understand pointers - variables that store memory addresses of other variables. Think of them as directions to where actual data is stored, like an address pointing to a house.
Declaring pointers to integers and Node structures
Assigning addresses to pointers
Accessing and modifying data through pointers
A linked list is a dynamic linear data structure where elements (called nodes) are stored in sequence, but unlike arrays, they are not stored in contiguous memory locations. Each node contains two essential components:
Stores the actual information - could be integers, strings, objects, or any data type.
Contains the memory address of the next node in the sequence, creating the "link".
Size can change during runtime - no need to declare fixed size upfront
O(1) insertion and deletion at the beginning, no shifting required
Allocates memory as needed, no unused allocated space
Cannot directly access element by index like arrays[i]
Each node requires additional memory for storing pointer
Must traverse from beginning to reach any element
struct Node {
int data; // Data field
Node* next; // Pointer to next node
};struct DoublyNode {
int data; // Data field
DoublyNode* next; // Next node pointer
DoublyNode* prev; // Previous node pointer
};*If node reference available
// Circular condition
if (current->next == head) {
// We've completed the circle
break;
}void insertAtHead(int data) {
Node* newNode = new Node(data);
newNode->next = head;
head = newNode;
size++;
}void insertAtTail(int data) {
Node* newNode = new Node(data);
if (!head) {
head = newNode;
return;
}
Node* temp = head;
while (temp->next) {
temp = temp->next;
}
temp->next = newNode;
size++;
}void insertAtPosition(int data, int pos) {
if (pos < 0 || pos > size) return;
if (pos == 0) {
insertAtHead(data);
return;
}
Node* newNode = new Node(data);
Node* temp = head;
for (int i = 0; i < pos - 1; i++) {
temp = temp->next;
}
newNode->next = temp->next;
temp->next = newNode;
size++;
}bool deleteFromHead() {
if (!head) return false;
Node* nodeToDelete = head;
head = head->next;
delete nodeToDelete;
size--;
return true;
}bool deleteByValue(int value) {
if (!head) return false;
if (head->data == value) {
return deleteFromHead();
}
Node* current = head;
while (current->next &&
current->next->data != value) {
current = current->next;
}
if (current->next) {
Node* nodeToDelete = current->next;
current->next = nodeToDelete->next;
delete nodeToDelete;
size--;
return true;
}
return false;
}void traverse() {
Node* current = head;
while (current != nullptr) {
cout << current->data << " -> ";
current = current->next;
}
cout << "NULL" << endl;
}int search(int value) {
Node* current = head;
int position = 0;
while (current != nullptr) {
if (current->data == value) {
return position;
}
current = current->next;
position++;
}
return -1; // Not found
}| Operation | Singly LL | Doubly LL | Circular LL | Array (Compare) |
|---|---|---|---|---|
| Insert at Beginning | O(1) | O(1) | O(1) | O(n) |
| Insert at End | O(n) | O(1)* | O(n) | O(1)** |
| Insert at Position | O(n) | O(n) | O(n) | O(n) |
| Delete from Beginning | O(1) | O(1) | O(1) | O(n) |
| Delete from End | O(n) | O(1)* | O(n) | O(1) |
| Delete by Value | O(n) | O(n) | O(n) | O(n) |
| Search/Access | O(n) | O(n) | O(n) | O(1)*** |
| Traversal | O(n) | O(n) | O(n) | O(n) |
* With tail pointer maintained
** Amortized time for dynamic arrays
*** For random access by index
class ListNode {
constructor(data) {
this.data = data;
this.next = null;
}
}
// Doubly Linked List Node
class DoublyListNode {
constructor(data) {
this.data = data;
this.next = null;
this.prev = null;
}
}class ListNode:
def __init__(self, data):
self.data = data
self.next = None
# Doubly Linked List Node
class DoublyListNode:
def __init__(self, data):
self.data = data
self.next = None
self.prev = Noneclass SinglyLinkedList {
constructor() {
this.head = null;
this.size = 0;
}
// Insert at beginning - O(1)
insertAtBeginning(data) {
const newNode = new ListNode(data);
newNode.next = this.head;
this.head = newNode;
this.size++;
}
// Insert at end - O(n)
insertAtEnd(data) {
const newNode = new ListNode(data);
if (!this.head) {
this.head = newNode;
} else {
let current = this.head;
while (current.next) {
current = current.next;
}
current.next = newNode;
}
this.size++;
}
// Insert at specific position - O(n)
insertAtPosition(data, position) {
if (position < 0 || position > this.size) {
throw new Error('Position out of bounds');
}
if (position === 0) {
this.insertAtBeginning(data);
return;
}
const newNode = new ListNode(data);
let current = this.head;
for (let i = 0; i < position - 1; i++) {
current = current.next;
}
newNode.next = current.next;
current.next = newNode;
this.size++;
}
// Delete by value - O(n)
deleteByValue(value) {
if (!this.head) return false;
if (this.head.data === value) {
this.head = this.head.next;
this.size--;
return true;
}
let current = this.head;
while (current.next && current.next.data !== value) {
current = current.next;
}
if (current.next) {
current.next = current.next.next;
this.size--;
return true;
}
return false;
}
// Search - O(n)
search(value) {
let current = this.head;
let position = 0;
while (current) {
if (current.data === value) {
return position;
}
current = current.next;
position++;
}
return -1;
}
// Display list
display() {
const elements = [];
let current = this.head;
while (current) {
elements.push(current.data);
current = current.next;
}
return elements.join(' -> ') + ' -> null';
}
}class DoublyLinkedList {
constructor() {
this.head = null;
this.tail = null;
this.size = 0;
}
// Insert at beginning - O(1)
insertAtBeginning(data) {
const newNode = new DoublyListNode(data);
if (!this.head) {
this.head = this.tail = newNode;
} else {
newNode.next = this.head;
this.head.prev = newNode;
this.head = newNode;
}
this.size++;
}
// Insert at end - O(1) with tail pointer
insertAtEnd(data) {
const newNode = new DoublyListNode(data);
if (!this.tail) {
this.head = this.tail = newNode;
} else {
this.tail.next = newNode;
newNode.prev = this.tail;
this.tail = newNode;
}
this.size++;
}
// Delete node - O(1) if node reference available
deleteNode(node) {
if (!node) return;
if (node.prev) {
node.prev.next = node.next;
} else {
this.head = node.next;
}
if (node.next) {
node.next.prev = node.prev;
} else {
this.tail = node.prev;
}
this.size--;
}
// Reverse traversal - O(n)
displayReverse() {
const elements = [];
let current = this.tail;
while (current) {
elements.push(current.data);
current = current.prev;
}
return elements.join(' <- ') + ' <- null';
}
}Browser history navigation using doubly linked lists for forward/back functionality.
Playlist management with next/previous song navigation and shuffle features.
Text editors and IDEs use linked lists to implement undo/redo functionality.
Operating systems use circular linked lists for round-robin scheduling.
Friend suggestions and social graphs using linked list structures.
Dynamic memory allocation systems use linked lists to track free memory blocks.
Web browsers use doubly linked lists to implement forward/back navigation history.
Music and video players use circular linked lists for playlist management and continuous play.
Text editors and IDEs implement undo/redo using doubly linked lists of command states.
OS process scheduling uses circular linked lists for round-robin algorithm implementation.
Friend connections, news feeds, and social graphs implemented using linked structures.
Dynamic memory allocators use linked lists to track free and allocated memory blocks.