Linked List Basics
What is a Linked List?
A linked list is a linear data structure consisting of a series of nodes, where each node contains:
- Data Field: Stores the data element
- Pointer Field: Stores a reference to the next node (in a singly linked list)
Unlike arrays, elements in a linked list are not stored contiguously in memory but are linked together through pointers.
Types of Linked Lists
- Singly Linked List:
- Each node has a single pointer pointing to the next node
- The last node’s pointer points to
null
- Doubly Linked List:
- Each node has two pointers, one to the previous node and one to the next node
- The first node’s previous pointer is
null, and the last node’s next pointer isnull
- Circular Linked List:
- The last node in a singly or doubly linked list points to the first node, forming a circular structure
Linked List vs Array
| Feature | Linked List | Array |
|---|---|---|
| Memory Allocation | Dynamic, non-contiguous storage | Contiguous memory block |
| Size | Dynamic growth | Fixed size (static array) or dynamic expansion (dynamic array) |
| Access Time | O(n) (requires traversal) | O(1) (direct access via index) |
| Insertion/Deletion | O(1) (when position is known) | O(n) (may require moving elements) |
| Memory Overhead | Extra storage for pointers per node | No extra pointer storage |
Implementation of Singly Linked List
Node Class Definition
class Node {
constructor(data) {
this.data = data; // Data field
this.next = null; // Pointer field, initialized to null
}
}
Linked List Class Implementation
class LinkedList {
constructor() {
this.head = null; // Head node of the list
this.tail = null; // Tail node of the list (optional, improves tail operation efficiency)
this.length = 0; // Length of the list
}
// Add a node to the end of the list
append(data) {
const newNode = new Node(data);
if (!this.head) {
this.head = newNode;
this.tail = newNode;
} else {
this.tail.next = newNode;
this.tail = newNode;
}
this.length++;
return this;
}
// Add a node to the beginning of the list
prepend(data) {
const newNode = new Node(data);
newNode.next = this.head;
this.head = newNode;
if (!this.tail) { // If the list is empty
this.tail = newNode;
}
this.length++;
return this;
}
// Insert a node at the specified position
insert(index, data) {
if (index < 0 || index > this.length) return false;
if (index === 0) {
this.prepend(data);
return true;
}
if (index === this.length) {
this.append(data);
return true;
}
const newNode = new Node(data);
const leader = this.getNodeAt(index - 1);
newNode.next = leader.next;
leader.next = newNode;
this.length++;
return true;
}
// Get the node at the specified position
getNodeAt(index) {
if (index < 0 || index >= this.length) return null;
let currentNode = this.head;
let counter = 0;
while (counter < index) {
currentNode = currentNode.next;
counter++;
}
return currentNode;
}
// Get the length of the list
size() {
return this.length;
}
// Check if the list is empty
isEmpty() {
return this.length === 0;
}
// Get the element at the specified position
get(index) {
const node = this.getNodeAt(index);
return node ? node.data : undefined;
}
// Remove the node at the specified position
remove(index) {
if (index < 0 || index >= this.length) return undefined;
if (index === 0) {
const removedNode = this.head;
this.head = this.head.next;
this.length--;
if (this.length === 0) {
this.tail = null;
}
return removedNode.data;
}
const leader = this.getNodeAt(index - 1);
const removedNode = leader.next;
leader.next = removedNode.next;
if (index === this.length - 1) {
this.tail = leader;
}
this.length--;
return removedNode.data;
}
// Remove the head node
removeHead() {
return this.remove(0);
}
// Remove the tail node
removeTail() {
return this.remove(this.length - 1);
}
// Check if an element exists
contains(data) {
let currentNode = this.head;
while (currentNode) {
if (currentNode.data === data) {
return true;
}
currentNode = currentNode.next;
}
return false;
}
// Find the index of an element
indexOf(data) {
let currentNode = this.head;
let index = 0;
while (currentNode) {
if (currentNode.data === data) {
return index;
}
currentNode = currentNode.next;
index++;
}
return -1;
}
// Clear the list
clear() {
this.head = null;
this.tail = null;
this.length = 0;
}
// Convert the list to an array
toArray() {
const array = [];
let currentNode = this.head;
while (currentNode) {
array.push(currentNode.data);
currentNode = currentNode.next;
}
return array;
}
// Print the list content
print() {
console.log(this.toArray().join(' -> '));
}
}
Usage Example
const list = new LinkedList();
list.append(10);
list.append(20);
list.append(30);
list.prepend(5);
console.log(list.toArray()); // [5, 10, 20, 30]
list.insert(2, 15);
console.log(list.toArray()); // [5, 10, 15, 20, 30]
list.remove(2);
console.log(list.toArray()); // [5, 10, 20, 30]
console.log(list.get(1)); // 10
console.log(list.contains(20)); // true
console.log(list.indexOf(30)); // 3
list.removeTail();
console.log(list.toArray()); // [5, 10, 20]
list.removeHead();
console.log(list.toArray()); // [10, 20]
list.clear();
console.log(list.isEmpty()); // true
Implementation of Doubly Linked List
Node Class Definition
class DoublyNode {
constructor(data) {
this.data = data;
this.next = null;
this.prev = null; // Added previous pointer
}
}
Doubly Linked List Class Implementation
class DoublyLinkedList {
constructor() {
this.head = null;
this.tail = null;
this.length = 0;
}
append(data) {
const newNode = new DoublyNode(data);
if (!this.head) {
this.head = newNode;
this.tail = newNode;
} else {
newNode.prev = this.tail;
this.tail.next = newNode;
this.tail = newNode;
}
this.length++;
return this;
}
prepend(data) {
const newNode = new DoublyNode(data);
if (!this.head) {
this.head = newNode;
this.tail = newNode;
} else {
newNode.next = this.head;
this.head.prev = newNode;
this.head = newNode;
}
this.length++;
return this;
}
insert(index, data) {
if (index < 0 || index > this.length) return false;
if (index === 0) {
this.prepend(data);
return true;
}
if (index === this.length) {
this.append(data);
return true;
}
const newNode = new DoublyNode(data);
const leader = this.getNodeAt(index - 1);
const follower = leader.next;
leader.next = newNode;
newNode.prev = leader;
newNode.next = follower;
follower.prev = newNode;
this.length++;
return true;
}
// Other methods similar to singly linked list but need to handle prev pointer
// ...
}
Applications of Linked Lists
1. Implementing a Stack
class Stack {
constructor() {
this.linkedList = new LinkedList();
}
push(data) {
this.linkedList.prepend(data);
}
pop() {
return this.linkedList.removeHead();
}
peek() {
return this.linkedList.head ? this.linkedList.head.data : undefined;
}
isEmpty() {
return this.linkedList.isEmpty();
}
size() {
return this.linkedList.size();
}
}
2. Implementing a Queue
class Queue {
constructor() {
this.linkedList = new LinkedList();
}
enqueue(data) {
this.linkedList.append(data);
}
dequeue() {
return this.linkedList.removeHead();
}
peek() {
return this.linkedList.head ? this.linkedList.head.data : undefined;
}
isEmpty() {
return this.linkedList.isEmpty();
}
size() {
return this.linkedList.size();
}
}
3. Implementing an LRU Cache
class LRUCache {
constructor(capacity) {
this.capacity = capacity;
this.cache = new Map(); // Use Map to maintain access order
}
get(key) {
if (!this.cache.has(key)) return -1;
// Retrieve value and reinsert to update order
const value = this.cache.get(key);
this.cache.delete(key);
this.cache.set(key, value);
return value;
}
put(key, value) {
if (this.cache.has(key)) {
this.cache.delete(key);
} else if (this.cache.size >= this.capacity) {
// Remove the least recently used item (first item in Map)
const oldestKey = this.cache.keys().next().value;
this.cache.delete(oldestKey);
}
this.cache.set(key, value);
}
}
Note: The above LRU implementation uses JavaScript’s Map to maintain order, as Map maintains key-value pairs in insertion order. For more precise control, a doubly linked list can be used.
4. Linked List Reversal
class LinkedList {
// ... Other methods ...
reverse() {
let prev = null;
let current = this.head;
let next = null;
while (current) {
next = current.next; // Save the next node
current.next = prev; // Reverse the pointer
prev = current; // Move prev forward
current = next; // Move current forward
}
// Swap head and tail
[this.head, this.tail] = [this.tail, this.head];
return this;
}
}
5. Cycle Detection (Floyd’s Cycle-Finding Algorithm)
class LinkedList {
// ... Other methods ...
hasCycle() {
if (!this.head) return false;
let slow = this.head;
let fast = this.head;
while (fast && fast.next) {
slow = slow.next; // Slow pointer moves one step
fast = fast.next.next; // Fast pointer moves two steps
if (slow === fast) { // If they meet, there is a cycle
return true;
}
}
return false; // Fast pointer reaches the end, no cycle
}
}
Performance Analysis
| Operation | Singly Linked List Time Complexity | Doubly Linked List Time Complexity |
|---|---|---|
| Access Element | O(n) | O(n) |
| Insert at Head | O(1) | O(1) |
| Insert at Tail | O(n) | O(1) (with tail pointer) |
| Insert in Middle | O(n) | O(n) |
| Delete Head Element | O(1) | O(1) |
| Delete Tail Element | O(n) | O(1) (with tail pointer) |
| Delete Specified Element | O(n) | O(n) |
Advantages and Disadvantages
Advantages:
- Dynamic Size: No need to pre-allocate memory
- Efficient Insertion/Deletion: Simple operations when the position is known
- High Memory Utilization: Only stores actual data
Disadvantages:
- Low Access Efficiency: Must traverse from the head
- Extra Space for Pointers
- Complex Implementation: Requires handling pointer operations
Practical Application Scenarios
- Browser History: Use a doubly linked list to implement forward and backward navigation
- Music Playlist: Dynamically add/remove songs
- LRU Cache: Combine hash table and doubly linked list for efficient caching
- Blockchain: Each block links to the previous block
- Memory Management: Managing free memory blocks in operating systems
Linked lists are a fundamental yet powerful data structure, more efficient than arrays in specific scenarios. Understanding the implementation principles and operations of linked lists is crucial for deepening knowledge in computer science and solving practical problems.
