Linked lists are a fundamental linear data structure where elements (nodes) are not stored contiguously in memory. Each node contains data and a reference (pointer) to the next node in the list, forming a chain-like structure. This dynamic allocation offers advantages over arrays (fixed size) when frequent insertions or deletions are necessary.
Singly Linked List: Nodes with a Single Forward Arrow
In a Singly Linked List, each node contains two essential components:
- Data Field: Stores the actual value associated with the node (e.g., an integer, string, object).
- Next Pointer: A reference (link) pointing to the next node in the sequence. It’s visually depicted as a single arrow pointing forward, indicating the direction of traversal.
The next pointer of the last node points to None, signifying the end of the list. This establishes a chain-like structure where nodes are connected through these pointers, enabling efficient insertions and deletions from any position without the need to shift subsequent elements in memory (unlike arrays).
head -> [data | next] -> [data | next] -> [data | next] -> None
For example, a singly linked list with elements 1, 2, and 3:
head -> [1 | next] -> [2 | next] -> [3 | next] -> NoneDoubly Linked List: Nodes with Two Arrows
A Doubly Linked List introduces an additional prev pointer in each node. This pointer references the node preceding the current node in the linked list, creating a two-way traversal capability. It’s visually represented as an arrow pointing backwards:
- Data Field: Similar to the singly linked list.
- Next Pointer: Maintains the forward reference.
- Prev Pointer: References the previous node.
The prev pointer in the head node points to None as there’s no preceding node. Similarly, the next pointer in the tail node points to None. This bidirectional navigation allows for efficient traversal in both forward and backward directions, which can be beneficial in certain use cases.
head <-> [prev | data | next] <-> [prev | data | next] <-> [prev | data | next] <-> None
For example, a doubly linked list with elements 1, 2, and 3:
head <-> [None | 1 | next] <-> [prev | 2 | next] <-> [prev | 3 | None]Circular Linked List: The Circle Completes
A Circular Linked List takes the concept of a Singly Linked List one step further. Instead of the last node pointing to None, its next pointer points back to the first node, forming a circular loop. This is visually depicted by the last node’s arrow curving back to the first node:
- Data Field: Same as previous list types.
- Next Pointer: In the last node, it points back to the head, creating the circular structure.
While insertions and deletions require some additional considerations to handle the circular nature, this list type can be useful in scenarios where you want to continuously iterate without reaching an end (e.g., implementing a round-robin scheduler).
head -> [data | next] -> [data | next] -> [data | next] --+
^ |
| v
+-----------------------------------------------+
For example, a circular singly linked list with elements 1, 2, and 3:
head -> [1 | next] -> [2 | next] -> [3 | next] --+
^ |
| v
+--------------------------------------+
head
|
v
[prev | 1 | next] <-> [prev | 2 | next] <-> [prev | 3 | next] <-> head
Singly Linked List Implementation
record Node
{
data; // The data being stored in the node
Node next // A reference to the next node, null for last node
}
record List
{
Node firstNode // points to first node of list; null for empty list
}
Traversal of a singly linked list is simple, beginning at the first node and following each next link until we come to the end:
node := list.firstNode
while node not null
(do something with node.data)
node := node.next
The following code inserts a node after an existing node in a singly linked list. The diagram shows how it works. Inserting a node before an existing one cannot be done directly; instead, one must keep track of the previous node and insert a node after it.
function insertAfter(Node node, Node newNode) // insert newNode after node
newNode.next := node.next
node.next := newNode
Inserting at the beginning of the list requires a separate function. This requires updating firstNode.
function insertBeginning(List list, Node newNode) // insert node before current first node
newNode.next := list.firstNode
list.firstNode := newNode
Similarly, we have functions for removing the node after a given node, and for removing a node from the beginning of the list. The diagram demonstrates the former. To find and remove a particular node, one must again keep track of the previous element.
function removeAfter(Node node) // remove node past this one
obsoleteNode := node.next
node.next := node.next.next
destroy obsoleteNode
function removeBeginning(List list) // remove first node
obsoleteNode := list.firstNode
list.firstNode := list.firstNode.next // point past deleted node
destroy obsoleteNodeNode Class
class Node:
def __init__(self, data):
self.data = data
self.next = None
Singly Linked List Class
class SinglyLinkedList:
def __init__(self):
self.head = None
def traverse(self):
current = self.head
while current:
print(current.data, end=" -> ")
current = current.next
print("None")
def insert_at_beginning(self, data):
new_node = Node(data)
new_node.next = self.head
self.head = new_node
def insert_at_end(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
return
last_node = self.head
while last_node.next:
last_node = last_node.next
last_node.next = new_node
def insert_after_node(self, prev_node_data, data):
current = self.head
while current and current.data != prev_node_data:
current = current.next
if current is None:
print(f"Node with data {prev_node_data} not found.")
return
new_node = Node(data)
new_node.next = current.next
current.next = new_node
def delete_node(self, key):
current = self.head
if current and current.data == key:
self.head = current.next
current = None
return
prev = None
while current and current.data != key:
prev = current
current = current.next
if current is None:
print(f"Node with data {key} not found.")
return
prev.next = current.next
current = None
# Example usage:
sll = SinglyLinkedList()
sll.insert_at_end(1)
sll.insert_at_end(2)
sll.insert_at_end(3)
sll.insert_at_beginning(0)
sll.traverse() # Output: 0 -> 1 -> 2 -> 3 -> None
sll.insert_after_node(1, 1.5)
sll.traverse() # Output: 0 -> 1 -> 1.5 -> 2 -> 3 -> None
sll.delete_node(1.5)
sll.traverse() # Output: 0 -> 1 -> 2 -> 3 -> None
Doubly Linked List Implementation
Node Class
class DoublyNode:
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
Doubly Linked List Class
class DoublyLinkedList:
def __init__(self):
self.head = None
def traverse(self):
current = self.head
while current:
print(current.data, end=" <-> ")
current = current.next
print("None")
def insert_at_beginning(self, data):
new_node = DoublyNode(data)
if self.head is None:
self.head = new_node
return
new_node.next = self.head
self.head.prev = new_node
self.head = new_node
def insert_at_end(self, data):
new_node = DoublyNode(data)
if self.head is None:
self.head = new_node
return
last_node = self.head
while last_node.next:
last_node = last_node.next
last_node.next = new_node
new_node.prev = last_node
def insert_after_node(self, prev_node_data, data):
current = self.head
while current and current.data != prev_node_data:
current = current.next
if current is None:
print(f"Node with data {prev_node_data} not found.")
return
new_node = DoublyNode(data)
new_node.next = current.next
new_node.prev = current
if current.next:
current.next.prev = new_node
current.next = new_node
def delete_node(self, key):
current = self.head
if current and current.data == key:
if current.next:
current.next.prev = None
self.head = current.next
current = None
return
while current and current.data != key:
current = current.next
if current is None:
print(f"Node with data {key} not found.")
return
if current.next:
current.next.prev = current.prev
if current.prev:
current.prev.next = current.next
current = None
# Example usage:
dll = DoublyLinkedList()
dll.insert_at_end(1)
dll.insert_at_end(2)
dll.insert_at_end(3)
dll.insert_at_beginning(0)
dll.traverse() # Output: 0 <-> 1 <-> 2 <-> 3 <-> None
dll.insert_after_node(1, 1.5)
dll.traverse() # Output: 0 <-> 1 <-> 1.5 <-> 2 <-> 3 <-> None
dll.delete_node(1.5)
dll.traverse() # Output: 0 <-> 1 <-> 2 <-> 3 <-> None
Circular Linked List Implementation
Node Class
class CircularNode:
def __init__(self, data):
self.data = data
self.next = None
Circular Linked List Class
class CircularLinkedList:
def __init__(self):
self.head = None
def traverse(self):
if not self.head:
return
current = self.head
while True:
print(current.data, end=" -> ")
current = current.next
if current == self.head:
break
print("Head")
def insert_at_beginning(self, data):
new_node = CircularNode(data)
if not self.head:
self.head = new_node
self.head.next = self.head
return
new_node.next = self.head
current = self.head
while current.next != self.head:
current = current.next
current.next = new_node
self.head = new_node
def insert_at_end(self, data):
new_node = CircularNode(data)
if not self.head:
self.head = new_node
self.head.next = self.head
return
current = self.head
while current.next != self.head:
current = current.next
current.next = new_node
new_node.next = self.head
def delete_node(self, key):
if not self.head:
return
if self.head.data == key:
if self.head.next == self.head:
self.head = None
return
current = self.head
while current.next != self.head:
current = current.next
current.next = self.head.next
self.head = self.head.next
return
prev = None
current = self.head
while current.next != self.head:
prev = current
current = current.next
if current.data == key:
prev.next = current.next
current = None
return
if current.data == key:
prev.next = current.next
current = None
# Example usage:
cll = CircularLinkedList()
cll.insert_at_end(1)
cll.insert_at_end(2)
cll.insert_at_end(3)
cll.insert_at_beginning(0)
cll.traverse() # Output: 0 -> 1 -> 2 -> 3 -> Head
cll.delete_node(2)
cll.traverse() # Output: 0 -> 1 -> 3 -> Head
Summary
- Singly Linked List: Each node points to the next node.
- Doubly Linked List: Each node points to both the next and previous nodes.
- Circular Linked List: The last node points back to the first node.
Linked lists are fundamental data structures used in various real-life applications and big projects. Here are a few examples of their usage, along with Python code implementations.
Real-Life Usage Examples
- Implementing a Queue:
- Queues are used in scheduling processes in operating systems, handling requests in web servers, and managing print jobs.
- Undo/Redo Functionality in Text Editors:
- Linked lists can be used to implement stacks for the undo and redo functionality in text editors.
- Dynamic Memory Allocation:
- Linked lists are used in memory management systems to keep track of free and used memory blocks.
- Graph Representation:
- Adjacency lists, which are used to represent graphs, can be implemented using linked lists.
- Browser History Management:
- The back and forward navigation in web browsers can be implemented using doubly linked lists.
- Music Playlists:
- Circular linked lists can be used to manage playlists where the last song links back to the first song.
Coding Examples in Python
1. Implementing a Queue Using Singly Linked List
class Node:
def __init__(self, data):
self.data = data
self.next = None
class Queue:
def __init__(self):
self.front = None
self.rear = None
def is_empty(self):
return self.front is None
def enqueue(self, data):
new_node = Node(data)
if self.rear is None:
self.front = self.rear = new_node
return
self.rear.next = new_node
self.rear = new_node
def dequeue(self):
if self.is_empty():
print("Queue is empty")
return
temp = self.front
self.front = temp.next
if self.front is None:
self.rear = None
return temp.data
def peek(self):
if self.is_empty():
print("Queue is empty")
return
return self.front.data
def traverse(self):
current = self.front
while current:
print(current.data, end=" -> ")
current = current.next
print("None")
# Example usage:
queue = Queue()
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
queue.traverse() # Output: 1 -> 2 -> 3 -> None
print(queue.dequeue()) # Output: 1
queue.traverse() # Output: 2 -> 3 -> None
print(queue.peek()) # Output: 2
2. Undo/Redo Functionality Using Doubly Linked List
class Node:
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
class TextEditor:
def __init__(self):
self.head = None
self.current = None
def write(self, data):
new_node = Node(data)
if self.head is None:
self.head = self.current = new_node
else:
new_node.prev = self.current
self.current.next = new_node
self.current = new_node
def undo(self):
if self.current and self.current.prev:
self.current = self.current.prev
def redo(self):
if self.current and self.current.next:
self.current = self.current.next
def show_current_state(self):
if self.current:
print(self.current.data)
else:
print("No text")
# Example usage:
editor = TextEditor()
editor.write("Hello")
editor.write("Hello, World")
editor.write("Hello, World!")
editor.show_current_state() # Output: Hello, World!
editor.undo()
editor.show_current_state() # Output: Hello, World
editor.undo()
editor.show_current_state() # Output: Hello
editor.redo()
editor.show_current_state() # Output: Hello, World
3. Memory Management Using Singly Linked List
class Node:
def __init__(self, start, size):
self.start = start
self.size = size
self.next = None
class MemoryManager:
def __init__(self, total_size):
self.head = Node(0, total_size)
def allocate(self, size):
current = self.head
prev = None
while current:
if current.size >= size:
allocated_start = current.start
current.start += size
current.size -= size
if current.size == 0:
if prev:
prev.next = current.next
else:
self.head = current.next
return allocated_start
prev = current
current = current.next
raise MemoryError("Not enough memory")
def deallocate(self, start, size):
new_node = Node(start, size)
if not self.head or start < self.head.start:
new_node.next = self.head
self.head = new_node
return
current = self.head
while current.next and current.next.start < start:
current = current.next
new_node.next = current.next
current.next = new_node
def show_memory(self):
current = self.head
while current:
print(f"Start: {current.start}, Size: {current.size}")
current = current.next
# Example usage:
manager = MemoryManager(1000)
print("Initial memory:")
manager.show_memory()
ptr1 = manager.allocate(100)
ptr2 = manager.allocate(200)
print("nMemory after allocation:")
manager.show_memory()
manager.deallocate(ptr1, 100)
print("nMemory after deallocation:")
manager.show_memory()
4.Implementing a Circular Linked List for a Music Playlist
In a music playlist, we often want to loop through the songs continuously. A circular linked list is a perfect fit for this use case as it allows the playlist to wrap around when the end is reached, seamlessly continuing from the start.
Node Class
Each node in the linked list represents a song in the playlist.
class Node:
def __init__(self, data):
self.data = data # Song data (e.g., song title)
self.next = None # Reference to the next node
Circular Linked List Class
This class will manage the circular linked list for the music playlist.
class CircularLinkedList:
def __init__(self):
self.head = None
def is_empty(self):
return self.head is None
def add_song(self, data):
new_node = Node(data)
if self.is_empty():
self.head = new_node
self.head.next = self.head
else:
current = self.head
while current.next != self.head:
current = current.next
current.next = new_node
new_node.next = self.head
def remove_song(self, key):
if self.is_empty():
print("Playlist is empty")
return
current = self.head
prev = None
while True:
if current.data == key:
if prev is None:
if current.next == self.head:
self.head = None
else:
temp = self.head
while temp.next != self.head:
temp = temp.next
temp.next = current.next
self.head = current.next
else:
prev.next = current.next
return
prev = current
current = current.next
if current == self.head:
break
print(f"Song '{key}' not found in the playlist")
def display_playlist(self):
if self.is_empty():
print("Playlist is empty")
return
current = self.head
while True:
print(current.data, end=" -> ")
current = current.next
if current == self.head:
break
print("Head")
def play(self):
if self.is_empty():
print("Playlist is empty")
return
current = self.head
while True:
print(f"Playing: {current.data}")
current = current.next
if current == self.head:
break
# Example usage:
playlist = CircularLinkedList()
playlist.add_song("Song 1")
playlist.add_song("Song 2")
playlist.add_song("Song 3")
playlist.display_playlist() # Output: Song 1 -> Song 2 -> Song 3 -> Head
print("nPlaying playlist:")
playlist.play()
# Output:
# Playing: Song 1
# Playing: Song 2
# Playing: Song 3
playlist.remove_song("Song 2")
playlist.display_playlist() # Output: Song 1 -> Song 3 -> Head
Explanation
- Node Class:
- Represents a song in the playlist with
datastoring the song information andnextpointing to the next node.
- Represents a song in the playlist with
- CircularLinkedList Class:
is_empty: Checks if the playlist is empty.add_song: Adds a new song to the playlist. If the playlist is empty, it initializes the head. Otherwise, it adds the song at the end and links it back to the head.remove_song: Removes a song from the playlist by its name. It handles cases where the song is at the head, in the middle, or not found.display_playlist: Displays the playlist by traversing the nodes and printing their data.play: Simulates playing the songs in the playlist continuously.
Summary
Using a circular linked list for managing a music playlist provides a seamless way to loop through the songs continuously. The provided implementation allows adding, removing, displaying, and playing songs in the playlist efficiently.
Leave a Reply