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] -> None

Doubly 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 obsoleteNode

Node 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

1. Implementing a Queue:
   • Queues are used in scheduling processes in operating systems, handling requests in web servers, and managing print jobs.
2. Undo/Redo Functionality in Text Editors:
   • Linked lists can be used to implement stacks for the undo and redo functionality in text editors.
3. Dynamic Memory Allocation:
   • Linked lists are used in memory management systems to keep track of free and used memory blocks.
4. Graph Representation:
   • Adjacency lists, which are used to represent graphs, can be implemented using linked lists.
5. Browser History Management:
   • The back and forward navigation in web browsers can be implemented using doubly linked lists.
6. 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

1. Node Class:
   • Represents a song in the playlist with data storing the song information and next pointing to the next node.
2. 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.