When learning about data structures, one concept that often comes up is the Linked List. It is a fundamental structure that is not only essential for technical interviews but also plays a significant role in solving problems where flexibility in size and frequent insertions or deletions are necessary.

In this article, we will explore what a linked list is, how it works, and why it is used instead of arrays, Real-Life Situations Where Linked Lists Are Used.

 

What is a Linked List?

 

A Linked List is a linear data structure, similar to an array, but with a key difference: elements in a linked list are not stored at contiguous memory locations. Instead, each element, or node, contains a reference (or pointer) to the next node in the sequence.

A linked list has the following characteristics:

• Nodes: Each node contains two fields: data (the value) and a reference to the next node.
• Head: The first node in the list, which acts as an entry point to the list.
• Tail: The last node in the list, which typically points to null (or None in some languages), indicating the end of the list.

Here is a visual representation:

 

 

 

 

 

[Data|Next] -> [Data|Next] -> [Data|Next] -> null

 

Types of Linked Lists

 

Singly Linked List: Each node points to the next node in the sequence, and the last node points to null.

• Head -> [Data|Next] -> [Data|Next] -> null

Doubly Linked List: Each node has two pointers  one to the next node and one to the previous node. This allows for bidirectional traversal.

• null <- [Prev|Data|Next] <-> [Prev|Data|Next] <-> null

Circular Linked List: In this type, the last node points back to the head, forming a circular chai

• [Data|Next] -> [Data|Next] -> [Data|Next] -> (back to head)

 

Linked List vs. Arrays: Why Use Linked Lists?

At first glance, arrays and linked lists seem similar, but they differ significantly in memory structure and operation efficiency.

 

1. Memory Management:

• Array: In an array, elements are stored in contiguous memory locations. This makes accessing an element by index (e.g., array[2]) very fast, with constant time complexity O(1). However, the size of the array must be defined in advance. If the array fills up, resizing (usually involving copying the entire array to a new memory location) is required.
• Linked List: Elements in a linked list are stored in different memory locations, linked by pointers. You can add or remove nodes easily without worrying about resizing. Since linked lists dynamically allocate memory, the size is flexible, growing and shrinking as needed.

 

2. Insertions and Deletions:

• Array: Inserting or deleting elements in the middle of an array is inefficient because it requires shifting elements to maintain contiguous memory. This leads to a time complexity of O(n).
• Linked List: In a linked list, inserting or deleting nodes is much faster because it only involves changing pointers, making the time complexity for insertions and deletions O(1), assuming you already have a reference to the node before the one you are modifying.

 

3. Access Speed:

• Array: Arrays provide constant-time access (O(1)) to elements by index.
• Linked List: Linked lists require linear time (O(n)) to access an element, as you need to traverse the list from the head to the desired node.

 

Example:

Let us say you want to add an item to a list. In an array, you would need to move other elements to make space:

 

 

 

 

 

 

 

// Inserting at index 2 in an array
let array = [1, 2, 3, 4];
array.splice(2, 0, 99); // Inserts 99 at index 2
console.log(array); // [1, 2, 99, 3, 4]

 

In contrast, a linked list does not require shifting elements:

 

 

 

 

 

// Adding a node to a linked list
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}

class LinkedList {
constructor() {
this.head = null;
}
insertAtBeginning(data) {
const newNode = new Node(data);
newNode.next = this.head;
this.head = newNode;
}
printList() {
let temp = this.head;
while (temp) {
console.log(temp.data);
temp = temp.next;
}
}
}
const list = new LinkedList();
list.insertAtBeginning(10);
list.insertAtBeginning(20);
list.insertAtBeginning(30);
list.printList(); // 30 -> 20 -> 10

 

 

When Should You Use Linked Lists?

 

Linked lists are useful when:

 

1. Frequent Insertions/Deletions: If you frequently need to insert or delete items in the middle of the list, a linked list is preferable to an array.
2. Dynamic Size: If you do not know the size of the collection in advance, a linked list provides a flexible size without needing to resize or allocate memory in advance.
3. Memory Optimization: If memory is limited and resizing arrays is costly, linked lists allocate memory only when new nodes are added, which can be more efficient in certain scenarios.

 

However, keep in mind that linked lists are not always the best choice. If you need fast access to elements by index, arrays are better due to their O(1) access time.

 

Real-Life Situations Where Linked Lists Are Used

 

Linked lists, despite being a fundamental concept in computer science, have real-world applications, especially when managing dynamic data or implementing specific functionalities. Here are a few examples of where linked lists are commonly used:

 

1. Music or Video Playlists

When you are listening to music on a platform like Spotify or playing videos in a queue, the system needs to dynamically manage the list of tracks or videos. Each song or video can be represented as a node, and the system can easily add, remove, or rearrange tracks without needing to shift all the other tracks in memory.

• Problem: You want to add a song to the playlist or skip to the next track without shifting all songs.
• Solution: The current song points to the next one (the next node), making it easy to change or update without affecting the rest of the list.

A doubly linked list can be used here to navigate both forward and backward through the playlist:

 

 

 

 

 

 

[Song 1] <-> [Song 2] <-> [Song 3] <-> null

 

2. Undo/Redo Functionality in Text Editors

In applications like Microsoft Word or Google Docs, each change you make (typing, deleting, formatting) is stored as a new state. The system needs to keep track of these changes so that you can undo or redo actions.

• Problem: You need to store a sequence of actions with the ability to undo or redo.
• Solution: A doubly linked list is perfect for this since it allows you to go back to a previous state or move forward to the next state by navigating backward or forward through the nodes.

 

 

 

 

 

 

null <-> [State 1] <-> [State 2] <-> [State 3]

Each state is a node in the linked list, and you can easily navigate between them.

 

3. Web Browsers: Forward and Backward Navigation

When you browse the internet and use the back and forward buttons, the browser is essentially keeping track of your history as a linked list.

• Problem: You need to navigate between previous and next pages without loading the entire history into memory at once.
• Solution: Each page you visit is a node in a doubly linked list, allowing you to go back or forward.

 

 

 

 

 

 

null <- [Page 1] <-> [Page 2] <-> [Page 3] -> null

You can quickly go back to a previous page or forward again by traversing this linked list of pages.

 

4. Operating Systems: Task Scheduling

Operating systems use linked lists to manage processes or tasks in a queue, such as CPU task scheduling, where tasks need to be efficiently added, removed, or reordered based on their priority.

• Problem: The system needs to manage a dynamic list of processes, adding new ones or removing completed ones in real time.
• Solution: Each process can be represented as a node, and the scheduler can efficiently move processes around using a linked list without reallocating memory for every insertion or deletion.

 

 

 

 

 

 

[Task 1] -> [Task 2] -> [Task 3] -> null

 

5. Photo Viewer Applications

In photo viewer apps, users can navigate through photos by clicking Next or Previous. Each image can be represented as a node in a linked list.

• Problem: You want to browse photos in a forward or backward direction without having to reload or search through a collection each time.
• Solution: A doubly linked list is often used here to make navigation between the previous and next photos efficient.

 

 

 

 

 

 

null <- [Photo 1] <-> [Photo 2] <-> [Photo 3] -> null

 

6. Memory Management (Free Lists)

Operating systems often use linked lists to manage available or free memory. A free list is a linked list of unused blocks of memory, and when a program requests memory, the system searches the list for an available block.

• Problem: You need to track available blocks of memory that may be scattered across different locations.
• Solution: Each free block of memory can be represented as a node, allowing the system to easily add or remove blocks from the list as memory is allocated or freed.

 

 

 

 

 

 

[Free Block 1] -> [Free Block 2] -> [Free Block 3] -> null

 

7. Navigating Between Apps on a Mobile Device

Mobile operating systems often use linked lists to manage open applications and allow users to switch between them. Each open application is stored as a node in a linked list, allowing the system to efficiently manage background tasks and open apps.

 

Conclusion

Linked lists are an elegant data structure with significant advantages for dynamic memory management, frequent insertions, and deletions. Understanding when to use them over arrays or other structures can help you write more efficient and scalable code.

While linked lists may not be as commonly used in high-level programming as arrays, they remain an essential tool in computer science, especially when working with data that changes frequently or requires efficient insertions and deletions.

Linked lists are not just an abstract concept; they have many practical uses in real-life applications. From managing playlists in music apps to facilitating memory management in operating systems, linked lists provide flexibility and efficiency in managing dynamic data that changes frequently. Their ability to easily add, remove, and traverse elements makes them indispensable in scenarios where performance and adaptability are critical.