Application of Linked List in Data Structure

A linked list is a fundamental data structure used in computer science, offering dynamic memory allocation, and efficient insertion, and deletion operations. It consists of nodes where each node contains data and a reference to the next node in the sequence. Linked lists come in different forms, including singly linked lists, doubly linked lists, and circular linked lists, each offering distinct advantages depending on the application. This article delves into the various applications of linked lists, highlighting their real-world significance and use in data structures and algorithms.

Types of Linked Lists

Before exploring the applications, it’s essential to understand the different types of linked lists, as their structures influence their practical applications:

• Singly Linked List: Each node contains data and a reference to the next node. It only allows traversal in one direction.
• Doubly Linked List: Each node contains data, a reference to the next node, and a reference to the previous node. This structure allows traversal in both directions.
• Circular Linked List: In this type of linked list, the last node points back to the first node, creating a circular structure. It can be singly or doubly linked.

Applications of Linked List in Data Structures

1. Dynamic Memory Allocation

Linked lists are widely used in applications where dynamic memory allocation is crucial. Unlike arrays, which require predefined memory space, linked lists can efficiently manage memory at runtime. This makes them ideal for scenarios where the size of the data structure is not known in advance or varies significantly during execution.

• Example: Operating systems utilize linked lists to manage free memory blocks (known as the free list). As processes allocate and release memory, the system dynamically adjusts the list of available memory blocks.

2. Implementation of Stacks and Queues

Stacks and queues are fundamental data structures used in various applications. Linked lists are an efficient way to implement both structures, overcoming the limitations of array-based implementations, such as fixed size.

• Stack: Using a singly linked list, a stack can be implemented where elements are pushed or popped from the head of the list.
• Queue: A queue can be implemented using a singly linked list where elements are enqueued at the tail and dequeued from the head.

Code Example: Stack Implementation Using Singly Linked List

class Stack:
    def __init__(self):
        self.head = None

    class Node:
        def __init__(self, data):
            self.data = data
            self.next = None

    def push(self, data):
        new_node = self.Node(data)
        new_node.next = self.head
        self.head = new_node

    def pop(self):
        if not self.head:
            return None
        popped = self.head.data
        self.head = self.head.next
        return popped

    def peek(self):
        if not self.head:
            return None
        return self.head.data

# Example
stack = Stack()
stack.push(10)
stack.push(20)
print(stack.pop())  # Outputs: 20

This implementation uses a singly linked list to mimic the "Last-In-First-Out" (LIFO) nature of a stack, allowing elements to be pushed or popped from the head.

Flow of Stack Operations:

Initially:    [ 10 | None ]
After push:   [ 20 | next ] -> [ 10 | None ]
After pop:    [ 10 | None ]

New elements are added to the head, and removed from the head when popped.

3. Application of Circular Linked List in Resource Scheduling

Circular linked lists find widespread application in resource scheduling tasks, where the processes need to be executed in a circular manner, ensuring that no process is starved for resources.

• Round Robin Scheduling: In operating systems, a circular linked list is used in the Round Robin scheduling algorithm. Processes are placed in a circular queue, and the CPU allocates time to each process in a cyclic manner.

Code Example: Circular Linked List for Round Robin Scheduling

class ProcessNode:
    def __init__(self, pid):
        self.pid = pid
        self.next = None

class CircularQueue:
    def __init__(self):
        self.head = None

    def add_process(self, pid):
        new_process = ProcessNode(pid)
        if not self.head:
            self.head = new_process
            new_process.next = self.head
        else:
            temp = self.head
            while temp.next != self.head:
                temp = temp.next
            temp.next = new_process
            new_process.next = self.head

    def display_processes(self):
        temp = self.head
        if self.head is not None:
            while True:
                print(f"Process {temp.pid}", end=" -> ")
                temp = temp.next
                if temp == self.head:
                    break
        print("Head")

# Example
queue = CircularQueue()
queue.add_process(1)
queue.add_process(2)
queue.add_process(3)
queue.display_processes()

A circular linked list is used to simulate Round Robin scheduling, where processes are executed in a cyclic order without starvation.

Flow of  Circular Queue

[ Process 1 -> Process 2 -> Process 3 -> Head ]

New processes are inserted into the circular list, and the CPU time is allocated in a circular manner.

4. Real-Time Traffic Control

Real-time applications, such as traffic control systems, use circular linked lists to ensure that traffic signals operate in a cyclic order, with each signal being activated for a certain duration before moving to the next. The circular structure allows for continuous and seamless switching between traffic lights.

5. Polynomial Manipulation

In mathematics and computer science, linked lists can represent polynomial expressions efficiently. Each node in the linked list can store the coefficient and exponent of a term in the polynomial. Operations such as addition and multiplication of polynomials become easier to implement using a linked list.

• Example: A polynomial like 3x^2 + 4x + 5 can be represented as a linked list where each node contains the coefficient and exponent.

Code Example: Polynomial Representation Using Singly Linked List

class PolynomialNode:
    def __init__(self, coefficient, exponent):
        self.coefficient = coefficient
        self.exponent = exponent
        self.next = None

class PolynomialLinkedList:
    def __init__(self):
        self.head = None

    def insert_term(self, coefficient, exponent):
        new_node = PolynomialNode(coefficient, exponent)
        if not self.head:
            self.head = new_node
        else:
            temp = self.head
            while temp.next:
                temp = temp.next
            temp.next = new_node

    def display_polynomial(self):
        temp = self.head
        while temp:
            print(f"{temp.coefficient}x^{temp.exponent}", end=" + " if temp.next else "")
            temp = temp.next
        print()

# Example
poly = PolynomialLinkedList()
poly.insert_term(3, 2)  # 3x^2
poly.insert_term(4, 1)  # 4x
poly.insert_term(5, 0)  # 5
poly.display_polynomial()  # Outputs: 3x^2 + 4x^1 + 5

A singly linked list represents each term of a polynomial, making it easy to perform operations like addition and multiplication.

Flow of Polynomial Representation

[ 3x^2 -> 4x^1 -> 5 ]

Each node contains a term (coefficient and exponent), and traversing the list prints the entire polynomial expression.

6. Application of Doubly Linked List in Browser Navigation

A doubly linked list is perfect for applications requiring bidirectional navigation. One common real-world example is in web browsers, where users can navigate forward and backward through their browsing history.

• Browser History: Each webpage visited is stored as a node in a doubly linked list. The back button navigates to the previous node, while the forward button navigates to the next node, enabling seamless transitions between visited pages.

Code Example: Browser History Using Doubly Linked List

class Page:
    def __init__(self, url):
        self.url = url
        self.prev = None
        self.next = None

class BrowserHistory:
    def __init__(self):
        self.head = None
        self.tail = None
        self.current = None

    def visit_page(self, url):
        new_page = Page(url)
        if not self.head:
            self.head = new_page
            self.tail = new_page
            self.current = new_page
        else:
            new_page.prev = self.tail
            self.tail.next = new_page
            self.tail = new_page
            self.current = new_page

    def back(self):
        if self.current and self.current.prev:
            self.current = self.current.prev
            return self.current.url
        return None

    def forward(self):
        if self.current and self.current.next:
            self.current = self.current.next
            return self.current.url
        return None

# Example usage
history = BrowserHistory()
history.visit_page("google.com")
history.visit_page("github.com")
history.visit_page("stackoverflow.com")
print(history.back())  # Outputs: github.com
print(history.forward())  # Outputs: stackoverflow.com

A doubly linked list tracks forward and backward navigation between visited web pages, allowing seamless transitions using the back and forward buttons.

Flow of  Browser History

[ google.com <-> github.com <-> stackoverflow.com ]

Nodes represent visited pages, and navigation occurs bidirectionally by moving between previous and next nodes.

7. Music and Video Playlists

Applications like music players and video streaming services often use circular or doubly linked lists to manage playlists. The circular linked list ensures that when a playlist reaches the end, it loops back to the beginning, creating a seamless, continuous experience for the user.

Code Example: Circular Linked List for Music Playlist

class Song:
    def __init__(self, title):
        self.title = title
        self.next = None

class Playlist:
    def __init__(self):
        self.head = None

    def add_song(self, title):
        new_song = Song(title)
        if not self.head:
            self.head = new_song
            new_song.next = self.head
        else:
            temp = self.head
            while temp.next != self.head:
                temp = temp.next
            temp.next = new_song
            new_song.next = self.head

    def display_playlist(self):
        temp = self.head
        if self.head is not None:
            while True:
                print(f"Playing: {temp.title}", end=" -> ")
                temp = temp.next
                if temp == self.head:
                    break
        print("Repeat")

# Example
playlist = Playlist()
playlist.add_song("Song 1")
playlist.add_song("Song 2")
playlist.add_song("Song 3")
playlist.display_playlist()

A circular linked list is used to manage a playlist of songs or videos, ensuring continuous playback by looping back to the start after the last item.

Flow of Circular Playlist

[ Song 1 -> Song 2 -> Song 3 -> Repeat ]

The playlist loops in a circle, where the last song's next points back to the first song.

8. Undo and Redo Operations in Text Editors

Text editors, graphic design tools, and many other software applications use doubly linked lists to implement undo and redo functionalities. Every action (such as typing a letter or deleting content) is stored in a node. The undo action moves to the previous node, while the redo action moves to the next.

Code Example: Undo-Redo Using Doubly Linked List

class Action:
    def __init__(self, description):
        self.description = description
        self.prev = None
        self.next = None

class UndoRedoManager:
    def __init__(self):
        self.current = None

    def perform_action(self, description):
        new_action = Action(description)
        if not self.current:
            self.current = new_action
        else:
            new_action.prev = self.current
            self.current.next = new_action
            self.current = new_action

    def undo(self):
        if self.current and self.current.prev:
            self.current = self.current.prev
            return f"Undo: {self.current.description}"
        return "Nothing to undo"

    def redo(self):
        if self.current and self.current.next:
            self.current = self.current.next
            return f"Redo: {self.current.description}"
        return "Nothing to redo"

# Example usage
undo_redo = UndoRedoManager()
undo_redo.perform_action("Type A")
undo_redo.perform_action("Type B")
print(undo_redo.undo())  # Outputs: Undo: Type A
print(undo_redo.redo())  # Outputs: Redo: Type B

A doubly linked list stores user actions in a text editor, enabling navigation between previous (undo) and next (redo) actions.

Flow of Undo-Redo

[ Type A <-> Type B ]

Actions are linked forward and backward, allowing the user to undo or redo commands by traversing the list.

9. Graph and Tree Implementations

Linked lists are extensively used in graph and tree implementations, particularly when the number of vertices and edges is not known beforehand.

• Adjacency List in Graphs: Graphs are represented using an adjacency list, where each node corresponds to a vertex, and its adjacent vertices are stored in a linked list. This structure is efficient in terms of both time and space, especially for sparse graphs.
• Binary Trees: Binary trees, especially binary search trees (BSTs), use a variation of linked lists where each node has two pointers, one for the left child and one for the right child. Doubly linked lists are also useful in threaded binary trees.

10. Application of Singly Linked List in Hashing

In hashing, singly linked lists are employed to handle collisions using chaining. When two or more elements hash to the same index, a linked list is created at that index to store the colliding elements. This ensures efficient management of collisions and helps maintain the overall performance of the hash table.

11. Linked List Applications in Real Life

Linked lists have numerous practical applications in everyday software development and systems.

• File Allocation in Operating Systems: Operating systems use linked lists to manage file storage on disk. For example, the File Allocation Table (FAT) system uses a linked list to keep track of the blocks of a file, ensuring that the file can be stored across non-contiguous blocks on the disk.
• Job Scheduling: In certain job scheduling algorithms, a linked list is used to maintain a list of jobs to be executed in a specific order. Each job can be dynamically added or removed as required by the system.

Check out our latest articles DSA Cheat Sheet, Application of Stack in Data Structure and Reverse a Linked List

Conclusion

Linked lists offer a flexible and dynamic approach to storing and managing data, making them ideal for numerous applications. From dynamic memory allocation to implementing complex systems like operating systems, circular scheduling, and undo-redo mechanisms, linked lists are indispensable in computer science and real-world applications. Understanding the various types of linked lists and their respective use cases is crucial for designing efficient data structures and solving real-world problems in computing.

Enroll in our Data Science online course and Masters in Data Science program to enhance your skills and master the fundamentals of this evolving field.