🧩 What is a Linked List?
A linked list is a fundamental linear data structure in computer science in which elements, called nodes, are connected using pointers (or references). Unlike arrays, where elements are stored in contiguous memory locations, linked list elements can be stored anywhere in memory, and each node stores the address of the next node in the sequence.
A typical node in a linked list consists of two parts:
- Data – stores the actual value
- Pointer/Reference – stores the address of the next node
In simple terms, a linked list looks like a chain:
[Data | Next] → [Data | Next] → [Data | Next] → NULL
🧠 Key Characteristics of Linked Lists
🔹 1. Dynamic Size
Linked lists can grow or shrink during runtime. You don’t need to define a fixed size beforehand.
🔹 2. Non-Contiguous Memory
Nodes are stored at random memory locations and connected using pointers.
🔹 3. Efficient Insertions/Deletions
Unlike arrays, inserting or deleting elements does not require shifting elements.
🔹 4. Sequential Access
Elements must be accessed sequentially (no direct indexing like arrays).
🧱 Structure of a Node
In most programming languages, a node is defined as:
Example in C:
struct Node {
int data;
struct Node* next;
};
Example in Python:
class Node:
def __init__(self, data):
self.data = data
self.next = None
🔗 Types of Linked Lists
🔹 1. Singly Linked List
Each node points to the next node.
Structure:
Head → Node1 → Node2 → Node3 → NULL
Features:
- Simple implementation
- Traversal in one direction only
🔹 2. Doubly Linked List
Each node contains:
- Pointer to next node
- Pointer to previous node
Structure:
NULL ← Node1 ⇄ Node2 ⇄ Node3 → NULL
Features:
- Traversal in both directions
- Extra memory required for previous pointer
🔹 3. Circular Linked List
Last node points back to the first node.
Structure:
Head → Node1 → Node2 → Node3 ↺
🔹 4. Circular Doubly Linked List
Combines circular and doubly linked features.
⚙️ Basic Operations on Linked Lists
🔹 1. Traversal
Accessing elements one by one.
current = head
while current:
print(current.data)
current = current.next
🔹 2. Insertion
Types:
- At beginning
- At end
- At specific position
🔹 3. Deletion
Removing nodes and updating pointers.
🔹 4. Searching
def search(head, key):
current = head
while current:
if current.data == key:
return True
current = current.next
return False
🔹 5. Reversal
Reversing direction of pointers.
🧮 Time Complexity of Operations
| Operation | Time Complexity |
|---|---|
| Access | O(n) |
| Search | O(n) |
| Insertion | O(1) (at head) |
| Deletion | O(1) (if pointer known) |
⚡ Advantages of Linked Lists
- Dynamic size
- Efficient insertions and deletions
- No memory wastage due to pre-allocation
- Flexible data structure
⚠️ Disadvantages of Linked Lists
- No random access
- Extra memory for pointers
- Complex implementation
- Cache inefficiency
🧑💻 Linked Lists in Different Languages
Python
class Node:
def __init__(self, data):
self.data = data
self.next = None
C++
class Node {
public:
int data;
Node* next;
};
Java
class Node {
int data;
Node next;
}
JavaScript
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
🧠 Advanced Concepts
🔹 1. Skip Lists
Improves search time using multiple levels.
🔹 2. XOR Linked Lists
Memory-efficient doubly linked list using XOR operations.
🔹 3. Self-Organizing Lists
Frequently accessed elements move to front.
🔬 Applications of Linked Lists
📚 1. Implementation of Stacks and Queues
Linked lists are widely used to implement stacks and queues.
🌐 2. Dynamic Memory Allocation
Used in memory management systems.
🧾 3. Polynomial Representation
Each node stores coefficient and power.
🎵 4. Music Playlist Systems
Songs linked sequentially.
🌍 5. Browser Navigation
Back/forward navigation uses doubly linked lists.
🔁 Linked List vs Array
| Feature | Linked List | Array |
|---|---|---|
| Memory | Non-contiguous | Contiguous |
| Size | Dynamic | Fixed |
| Access | Slow | Fast |
| Insert/Delete | Efficient | Costly |
🧪 Memory Representation
Each node contains:
- Data
- Pointer (address of next node)
Example:
[10 | 1000] → [20 | 2000] → [30 | NULL]
🚀 Real-World Importance
Linked lists are foundational for:
- Graph representations
- Hash tables (chaining)
- Operating systems
- File systems
- Networking
🧾 Conclusion
Linked lists are a powerful alternative to arrays when dynamic memory and efficient insertions/deletions are required. Although they lack direct access and may use extra memory, their flexibility makes them essential in many applications.
Understanding linked lists deeply helps in mastering advanced data structures like trees, graphs, and hash maps.
