Think of a linked list like a treasure hunt. In a treasure hunt, each clue tells you where to find the next clue. Similarly, in a linked list, each piece of data (called a “node”) contains two things:
- The actual data (like a number or name)
- A pointer/reference to where the next piece of data is located
Real-world analogy: Imagine a train where each car (node) carries passengers (data) and is connected to the next car (pointer).
1. Singly Linked List #
What is it? #
A singly linked list is like a one-way street. You can only move forward from one node to the next.
Structure: #
[Data|Next] -> [Data|Next] -> [Data|Next] -> NULL
Real-world Example: Music Playlist #
Imagine your music playlist where:
- Each song (node) contains the song name (data)
- Each song knows which song plays next (pointer)
- You can only skip forward, not backward
Example Playlist:
"Bohemian Rhapsody" -> "Stairway to Heaven" -> "Hotel California" -> END
Simple Code Example (Python): #
class Node:
def __init__(self, data):
self.data = data
self.next = None
class SinglyLinkedList:
def __init__(self):
self.head = None
def add_song(self, song_name):
new_node = Node(song_name)
if not self.head:
self.head = new_node
else:
current = self.head
while current.next:
current = current.next
current.next = new_node
def play_playlist(self):
current = self.head
while current:
print(f"Now playing: {current.data}")
current = current.next
# Usage
playlist = SinglyLinkedList()
playlist.add_song("Bohemian Rhapsody")
playlist.add_song("Stairway to Heaven")
playlist.add_song("Hotel California")
playlist.play_playlist()
Advantages: #
- Uses less memory than arrays (no need to declare size beforehand)
- Easy to add/remove elements at the beginning
- Dynamic size
Disadvantages: #
- Can’t go backward
- No random access (can’t jump to middle directly)
- Uses extra memory for pointers
2. Doubly Linked List #
What is it? #
A doubly linked list is like a two-way street. You can move forward AND backward.
Structure: #
NULL <- [Prev|Data|Next] <-> [Prev|Data|Next] <-> [Prev|Data|Next] -> NULL
Real-world Example: Web Browser History #
Think of your web browser’s back and forward buttons:
- Each webpage (node) remembers the previous page and next page
- You can go back to the previous page or forward to the next page
Example Browser History:
Google <- YouTube <-> Facebook <-> Twitter -> (end)
Simple Code Example (Python): #
class DoublyNode:
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
class DoublyLinkedList:
def __init__(self):
self.head = None
self.tail = None
def visit_page(self, page_name):
new_node = DoublyNode(page_name)
if not self.head:
self.head = self.tail = new_node
else:
new_node.prev = self.tail
self.tail.next = new_node
self.tail = new_node
def go_back(self, current_page):
# Find current page and go to previous
current = self.head
while current and current.data != current_page:
current = current.next
if current and current.prev:
return current.prev.data
return "No previous page"
def go_forward(self, current_page):
# Find current page and go to next
current = self.head
while current and current.data != current_page:
current = current.next
if current and current.next:
return current.next.data
return "No next page"
# Usage
browser = DoublyLinkedList()
browser.visit_page("Google")
browser.visit_page("YouTube")
browser.visit_page("Facebook")
print(browser.go_back("Facebook")) # Output: YouTube
print(browser.go_forward("YouTube")) # Output: Facebook
Advantages: #
- Can traverse in both directions
- Easy to delete a node (if you have reference to it)
- Better for implementing undo/redo functionality
Disadvantages: #
- Uses more memory (extra pointer for previous)
- More complex to implement
- Takes more time to insert/delete (need to update two pointers)
3. Circular Linked List #
What is it? #
A circular linked list is like a race track – it goes in a circle with no beginning or end. The last node points back to the first node.
Structure (Singly Circular): #
[Data|Next] -> [Data|Next] -> [Data|Next] -> (back to first node)
^ |
|____________________________________________|
Real-world Example: Round-Robin Game #
Think of a card game where players take turns in a circle:
- Player 1 -> Player 2 -> Player 3 -> Player 4 -> back to Player 1
- The game continues forever until someone wins
Example Game:
Alice -> Bob -> Charlie -> Dave -> (back to Alice)
Simple Code Example (Python): #
class CircularNode:
def __init__(self, data):
self.data = data
self.next = None
class CircularLinkedList:
def __init__(self):
self.head = None
def add_player(self, player_name):
new_node = CircularNode(player_name)
if not self.head:
self.head = new_node
new_node.next = new_node # Points to itself
else:
# Find the last node
current = self.head
while current.next != self.head:
current = current.next
# Insert new node
current.next = new_node
new_node.next = self.head
def play_round_robin(self, rounds):
if not self.head:
return
current = self.head
for i in range(rounds):
print(f"Round {i+1}: {current.data}'s turn")
current = current.next
# Usage
game = CircularLinkedList()
game.add_player("Alice")
game.add_player("Bob")
game.add_player("Charlie")
game.add_player("Dave")
game.play_round_robin(8) # Play 8 rounds
Advantages: #
- Great for round-robin scheduling
- Any node can be a starting point
- Useful for circular buffers
Disadvantages: #
- Easy to create infinite loops if not careful
- More complex to detect the end
- Difficult to find the “last” node
Real-World Use Cases #
1. Music Applications #
- Singly Linked: Basic playlist (next song only)
- Doubly Linked: Advanced playlist (previous/next song)
- Circular: Repeat playlist mode
2. Web Browsers #
- Doubly Linked: Browser history (back/forward buttons)
- Singly Linked: Bookmarks list
3. Operating Systems #
- Circular: CPU task scheduling (round-robin)
- Doubly Linked: Process management (easy insertion/deletion)
4. Image Viewers #
- Doubly Linked: Navigate between photos (previous/next)
- Circular: Slideshow mode (loops back to first image)
5. Undo/Redo Functionality #
- Doubly Linked: Text editors, image editors
- Can go back (undo) or forward (redo)
6. Gaming #
- Circular: Turn-based games (players take turns in order)
- Singly Linked: Inventory systems
7. Social Media #
- Singly Linked: News feed (scroll down to see more)
- Doubly Linked: Chat messages (scroll up/down)
When to Use Each Type #
Use Singly Linked List When: #
- You only need to move in one direction
- Memory is limited
- Simple implementation is preferred
- Example: Basic todo list, simple queue
Use Doubly Linked List When: #
- You need to move in both directions
- Frequent deletion operations
- Implementing undo/redo features
- Example: Text editor, browser history
Use Circular Linked List When: #
- You need to cycle through elements repeatedly
- Implementing round-robin algorithms
- Creating circular buffers
- Example: Game turns, CPU scheduling
Summary #
Linked lists are like different types of transportation systems:
- Singly Linked: One-way street (can only go forward)
- Doubly Linked: Two-way street (can go forward and backward)
- Circular: Race track (goes in a continuous loop)
Each type has its own strengths and is perfect for different situations. Choose the one that best fits your specific needs!
