Dynamic data structure with nodes connected via pointers
3
Length
10
Head
30
Tail
O(n)
Search Time
Ready for linked list operations
Linked List Structure
HEAD
↓
10
Node 0
next →
Index 0
Head Node
→
next
20
Node 1
next →
Index 1
→
next
30
Node 2
next →
Index 2
Tail Node
→
NULL
Memory Layout Concept
0x1A2B
Address
→
Data | Next*
Node Structure
→
0x3C4D
Next Address
Each node stores data and a pointer to the next nodes memory address
Time Complexity Comparison
O(n)
Access/Search
O(1)
Insert at Head
O(n)
Insert at Tail
O(n)
Delete at Index
Linked List Operations:
Basic Operations:
Insert at Head: Add new node at beginning - O(1)
Insert at Tail: Add new node at end - O(n)
Insert at Index: Add node at specific position - O(n)
Delete: Remove node from list - O(n) for search + O(1) for removal
Search: Find node with specific value - O(n)
Traverse: Visit all nodes in sequence - O(n)
Characteristics:
Dynamic Size: Can grow/shrink during runtime
Memory Efficient: Allocates memory as needed
Non-contiguous: Nodes can be anywhere in memory
Sequential Access: Must traverse from head to reach elements
Extra Memory: Requires storage for pointers
Use Cases: Implementation of stacks, queues, graphs
vs Arrays: Linked lists excel at insertions/deletions but have slower random access. Arrays have faster access but expensive insertions/deletions in the middle.