Data ScienceData Structures

Arunav Goswami

Data Science Consultant at almaBetter

Explore the key applications of linked lists in data structures, including their role in stacks, queues, memory allocation, browser history, text editors and more

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.

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.

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.

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.

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.

```
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.

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.

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.

```
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.

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.

```
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.

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.

```
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.

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.

```
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.

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.

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.

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*

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.

Related Articles

Top Tutorials

- Policies
- Privacy Statement
- Terms of Use

- Contact Us
- admissions@almabetter.com
- 08046008400

- Official Address
- 4th floor, 133/2, Janardhan Towers, Residency Road, Bengaluru, Karnataka, 560025

- Communication Address

- Follow Us

© 2024 AlmaBetter