Linked Lists

Lists are fundamental data structures that store collections of elements. There are two main types of lists: Array Lists and Linked Lists.

Array Lists

Array Lists (or Dynamic Arrays) provide constant-time access to elements and dynamic resizing capabilities.

Key Operations

• Access: O(1)
• Search: O(n)
• Insertion: O(n)
• Deletion: O(n)

Linked Lists

A linked list is a linear data structure where elements are stored in nodes, with each node containing both data and a reference (or link) to the next node in the sequence.

Singly Linked Lists

In a singly linked list, each node points to the next node in the sequence. The first node is called the head, and the last node (which points to null) is called the tail.

Structure

class Node {
	constructor(val) {
		this.val = val;
		this.next = null;
	}
}

class SinglyLinkedList {
	constructor() {
		this.length = 0;
		this.head = null;
		this.tail = null;
	}
}

Advantages

• Dynamic size
• Efficient insertion and deletion at the beginning
• Flexible memory allocation
• Easy to grow and shrink

Disadvantages

• No random access to elements (must traverse from head)
• Extra memory for storing node references
• Not cache-friendly due to non-contiguous memory storage

Common Operations

1. Push - Add to end
2. Pop - Remove from end
3. Shift - Remove from beginning
4. Unshift - Add to beginning
5. Get - Retrieve node at index
6. Set - Change value at index
7. Insert - Add at specific position
8. Remove - Delete at specific position
9. Reverse - Reverse the list

Time Complexities

Operation	Time Complexity
Access	O(n)
Search	O(n)
Insertion	O(1)*
Deletion	O(1)*

* When inserting/deleting at a known position. If you need to search first, it becomes O(n).

Implementation Example

Here's a complete implementation of a Singly Linked List with all common operations:

class Node {
	constructor(val) {
		this.val = val;
		this.next = null;
	}
}

class SinglyLinkedList {
	constructor() {
		this.length = 0;
		this.head = null;
		this.tail = null;
	}

	// Add to end
	push(val) {
		let newNode = new Node(val);
		if (!this.head) {
			this.head = newNode;
			this.tail = newNode;
		} else {
			this.tail.next = newNode;
			this.tail = newNode;
		}
		this.length++;
		return this;
	}

	// Remove from end
	pop() {
		if (!this.head) return undefined;

		let current = this.head;
		let newTail = current;
		while (current.next) {
			newTail = current;
			current = current.next;
		}

		this.tail = newTail;
		this.tail.next = null;
		this.length--;

		if (this.length === 0) {
			this.head = null;
			this.tail = null;
		}
		return current;
	}

	// Remove from beginning
	shift() {
		if (!this.head) return undefined;

		let oldHead = this.head;
		this.head = oldHead.next;
		this.length--;

		if (this.length === 0) {
			this.tail = null;
		}
		return oldHead;
	}

	// Add to beginning
	unshift(val) {
		let newNode = new Node(val);
		if (!this.head) {
			this.head = newNode;
			this.tail = newNode;
		} else {
			newNode.next = this.head;
			this.head = newNode;
		}
		this.length++;
		return this;
	}

	// Get node at index
	get(index) {
		if (index < 0 || index >= this.length) return null;
		let counter = 0;
		let current = this.head;
		while (counter !== index) {
			current = current.next;
			counter++;
		}
		return current;
	}

	// Change value at index
	set(index, val) {
		let foundNode = this.get(index);
		if (foundNode) {
			foundNode.val = val;
			return true;
		}
		return false;
	}

	// Insert at specific position
	insert(index, val) {
		if (index < 0 || index > this.length) return false;
		if (index === this.length) return !!this.push(val);
		if (index === 0) return !!this.unshift(val);

		let newNode = new Node(val);
		let prev = this.get(index - 1);
		let temp = prev.next;
		prev.next = newNode;
		newNode.next = temp;
		this.length++;
		return true;
	}

	// Remove at specific position
	remove(index) {
		if (index < 0 || index >= this.length) return undefined;
		if (index === 0) return this.shift();
		if (index === this.length - 1) return this.pop();

		let previousNode = this.get(index - 1);
		let removed = previousNode.next;
		previousNode.next = removed.next;
		this.length--;
		return removed;
	}

	// Reverse the list
	reverse() {
		let node = this.head;
		this.head = this.tail;
		this.tail = node;
		let next;
		let prev = null;

		for (let i = 0; i < this.length; i++) {
			next = node.next;
			node.next = prev;
			prev = node;
			node = next;
		}
		return this;
	}
}

Visual Representation

A singly linked list can be visualized as a chain of nodes:

Head -> [Data|Next] -> [Data|Next] -> [Data|Next] -> [Data|null] <- Tail

Common Use Cases

1. Implementation of Other Data Structures

   • Stacks and Queues
   • Hash Tables (for handling collisions)
   • Adjacency Lists in Graphs

2. Memory Management

   • Managing memory blocks
   • File systems

3. Applications

   • Browser history navigation
   • Undo/Redo operations
   • Music playlists

Practice Problems

To master linked lists, try solving these common problems:

1. Detect a cycle in a linked list
2. Find the middle element
3. Reverse a linked list
4. Merge two sorted linked lists
5. Remove duplicates
6. Check if a linked list is a palindrome

Additional Resources

• Detailed Blog Post on Linked Lists
• Video Tutorial on Linked Lists

Comparison: Array Lists vs. Linked Lists

Array Lists

Pros:

• Constant-time access to elements
• Cache-friendly (contiguous memory)
• Less memory per element

Cons:

• Fixed size (needs resizing)
• Insertion/deletion requires shifting elements

Linked Lists

Pros:

• Dynamic size
• Easy insertion/deletion
• No resizing needed

Cons:

• Linear-time access to elements
• Extra memory for node references
• Not cache-friendly