Introduction to Linked Lists
Linked lists are linear data structures where elements are stored in nodes, each containing data and a pointer to the next node. Unlike arrays, they provide dynamic sizing and efficient insertion/deletion.
What is a Linked List?
A linked list is a sequence of nodes where each node contains data and a reference (pointer) to the next node. Unlike arrays, they provide dynamic sizing and non-contiguous memory allocation.
Components
Node: Data + pointer • Head: First node • NULL: End marker
Time Complexity
Access: O(n) • Insert head: O(1) • Delete: O(1)*vs Arrays
Pros: Dynamic size • Cons: No random access • Use: Unknown size
Linked List Structure
Dynamic Memory: Nodes stored in non-contiguous locations
Sequential Access: Must traverse from head to reach elements
Types of Linked Lists
Singly Linked List
Each node points to the next node in sequence
Reverse Linked List Algorithm
Step 1 of 10
Initial State
Original linked list with nodes A → B → C → NULL
prev: nullcurr: Anext: B
Current Code:
ListNode prev = null; ListNode curr = head; ListNode next = null;
Common Operations
Traversal
O(n)Insert Head
O(1)Delete
O(1)Search
O(n)Reverse
O(n)Merge
O(m+n)Real-World Uses
Undo Ops
Editor history
Playlists
Music playback
Browser
Back/forward
Memory
OS allocation
Hash Tables
Collision chains
Queues
Task scheduling