Home

›

Articles

›

Understanding Applications Of Linked Lists, With Examples

# Understanding Applications Of Linked Lists, With Examples

Along with arrays, linked lists are a very common kind of linear data structure. These are similar to an array, but there are differences in how the data is stored and accessed. As well as this, the applications of linked lists differ from those of arrays. In this article, we’re going to quickly explain what linked lists are, and then delve into their applications, both in computer science and day-to-day life.

## What Are Linked Lists?

Linked lists are similar to arrays, but they don’t store elements contiguously. Instead, they contain each element within a node, with each node being associated with a “next” pointer. These pointers point to the next node, making a linked list have a direction. Pointers are also used to access each element, instead of indexing. An advantage of this is that linked lists can be modified dynamically, meaning we can add and remove elements whenever we wish.

## What Are the Different Types of Linked Lists?

While the basic structure, known as the singly-linked list, is rather simple, there are some more elaborate versions of the structure. These include the doubly-linked, circular, doubly-circular, skip, unrolled, and self-adjusting linked lists. These will be described next, along with their applications.

### Singly-Linked List

As mentioned before, a singly-linked list contains continuous nodes, linked to each other through pointers. This makes it easy to add and remove elements without having to reorganize the entire list. Even though the structure is fairly basic, there are many situations where singly-linked lists are appropriate. These include:

• Implementing dynamic data structures, and hash tables. When we need a dynamic structure, such as a stack or queue, linked lists are one of the simplest ways to implement this. They can also be used to implement hash tables, to prevent collisions between elements with the same index.
• Undo/redo – because we can store the state of the application as we go, we can use linked lists to undo and redo operations that were previously done.
• GPS systems – in a similar way, linked lists can be used to store landmarks and directions. If these are represented by nodes, we can use them to navigate our way.
• Organizing files – these linked lists can also be used to organize a structure of files within a directory. Both files and directories can be represented by a node and can point to a related file or directory.
• Polynomial manipulation – we use each node to represent a polynomial, which is an expression containing variables and coefficients, i.e. 3x2 + 2x – 1. We can modify these efficiently with a linked list.
• Representing graphs – by using nodes as vertices, we can represent graph structures using a linked list.

#### Example

Here’s an example implementation of a singly-linked list in Python:

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

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

def append(self, data):
new_node = Node(data)
if self.head is None:
self.head = new_node
else:
current = self.head
while current.next:
current = current.next
current.next = new_node

def display(self):
if self.head is None:
print("Linked list is empty.")
else:
current = self.head
while current:
print(current.data, end=" -> ")
current = current.next
print("None")

my_list = LinkedList()
my_list.append(10)
my_list.append(20)
my_list.append(30)

my_list.display()

We define the “Node” and “LinkedList” classes, and the “append()” method, which is used for adding elements to the list. If the list is empty, the new node becomes the head node. Otherwise, the head node points to the next node. 3 elements are added, and the list is displayed as seen in the image.

### Doubly-Linked List

Whereas a singly-linked list only has one direction, enabled by next pointers, doubly-linked lists are bidirectional. This is achieved by using an additional “previous” pointer, which points to the previous node in the list. This allows us to traverse the list in both the forward and backward direction, which is more appropriate in particular applications. The applications of a doubly-linked list include:

• Inserting and removing elements at both ends of the list.
• Implementing data structures, such as double-ended queues and lists.
• Undo/redo – this is more effective with a doubly-linked list because we must use a stack structure to keep track of changes when using a singly-linked list. This isn’t required with a doubly-linked list, because we can traverse in both directions.
• Browsers – because both directions can be traversed, we can use a doubly-linked list to allow a user to go backward and forward in their webpage history.
• Slideshows – representing each image as a node, we can move between images easily.
• Managing caches – By keeping recently viewed items near the head, we can remove older items once the cache is full up.
• Word processing – we can represent some sections of text as a node, such as one line, and use this structure to edit our text.
• Playing music – When using playlists, we often use doubly-linked lists to allow the user to change the song.
• Process scheduling – operating systems will often use this structure to manage active processes.

#### Example

For a simple implementation of a doubly-linked list, consider this code:

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

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

def is_empty(self):
return self.head is None

def insert_at_beginning(self, data):
new_node = Node(data)
if self.is_empty():
self.head = new_node
else:
new_node.next = self.head
self.head.prev = new_node
self.head = new_node

def insert_at_end(self, data):
new_node = Node(data)
if self.is_empty():
self.head = new_node
else:
current = self.head
while current.next:
current = current.next
current.next = new_node
new_node.prev = current

def display(self):
if self.is_empty():
print("Doubly linked list is empty.")
else:
current = self.head
while current:
print(current.data, end=" ")
current = current.next
print()

def display_reverse(self):
if self.is_empty():
print("Doubly linked list is empty.")
else:
current = self.head
while current.next:
current = current.next
while current:
print(current.data, end=" ")
current = current.prev
print()

dll = DoublyLinkedList()
dll.insert_at_beginning(10)
dll.insert_at_beginning(20)
dll.insert_at_end(30)
dll.insert_at_end(40)
dll.display()
dll.display_reverse()

We define the node and linked list classes as before but with a previous pointer included as well. We also have different code depending on where we’re adding an element. If it’s added at the start, the next pointer is set to the head node, and the head node’s previous pointer is set to the new node, with the new node becoming the head node. If we add the element to the end, we update the next pointer of the tail node to the new node and the previous pointer of the new node to the tail node. We then print the list in the forward direction as well as the reverse, as seen in the image.

### Circular List

These lists don’t have a defined start and end, as the end node wraps around to the beginning node. As such, they’re used when we require cyclic behavior. Circular list applications include:

• Implementing circular queues – the structure of the list naturally lends itself to circular queues, where the element that has been there for the longest will be removed first.
• Round-robin – this is a type of scheduling, where each process is assigned a fixed time. In this way, each process is given equal opportunity to be executed, and are cycled through evenly.
• Multiplayer gaming – circular lists can be used for many things here, such as maintaining player rotation, sending messages, syncing players and matching up players when joining a session.
• Buffering – circular lists can be used to manage the data in a buffer, as data can be removed without having to rearrange the other elements.

#### Example

Here is how to implement a simple circular linked list in Python.

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

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

def is_empty(self):
return self.head is None

def insert_at_beginning(self, data):
new_node = Node(data)
if self.is_empty():
new_node.next = new_node
self.head = new_node
else:
current = self.head
while current.next != self.head:
current = current.next
current.next = new_node
new_node.next = self.head
self.head = new_node

def insert_at_end(self, data):
new_node = Node(data)
if self.is_empty():
new_node.next = new_node
self.head = new_node
else:
current = self.head
while current.next != self.head:
current = current.next
current.next = new_node
new_node.next = self.head

def display(self):
if self.is_empty():
print("Circular linked list is empty.")
else:
current = self.head
while True:
print(current.data, end=" ")
current = current.next
if current == self.head:
break
print()

cll = CircularLinkedList()
cll.insert_at_beginning(10)
cll.insert_at_beginning(20)
cll.insert_at_end(30)
cll.insert_at_end(40)
cll.display()

### Doubly-Circular List

As you may have guessed by now, doubly-circular lists are those which are both circular and bidirectional. These have many of the same applications as the previously discussed linked lists, including music players, undo/redo operations, browser history, task scheduling, slideshows, and text editors. Doubly-circular lists generally offer more advantages in these scenarios. They also have some unique applications, such as:

• Image processing – we can use these lists for more efficient image processing since we can use information from neighboring pixels.
• Managing windows – where we need to cycle through windows or reorder them, this type of list is useful.
• Linked hash tables – A linked hash table combines a hash table with the features of a linked list. Doubly-circular linked lists are often used here so we can have flexible operations.

#### Example

An example of using a doubly-circular list is below.

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

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

def is_empty(self):
return self.head is None

def insert_at_beginning(self, data):
new_node = Node(data)
if self.is_empty():
new_node.next = new_node
new_node.prev = new_node
self.head = new_node
else:
new_node.next = self.head
new_node.prev = self.head.prev
self.head.prev.next = new_node
self.head.prev = new_node
self.head = new_node

def insert_at_end(self, data):
new_node = Node(data)
if self.is_empty():
new_node.next = new_node
new_node.prev = new_node
self.head = new_node
else:
new_node.next = self.head
new_node.prev = self.head.prev
self.head.prev.next = new_node
self.head.prev = new_node

def display(self):
if self.is_empty():
print("List is empty.")
return
current = self.head
while True:
print(current.data, end=" ")
current = current.next
if current == self.head:
break
print()

dllist = DoublyCircularLinkedList()

dllist.insert_at_beginning(3)
dllist.insert_at_beginning(7)
dllist.insert_at_beginning(1)

dllist.display()

dllist.insert_at_end(9)
dllist.insert_at_end(5)

dllist.display()

As a sort of combination of the doubly-linked and circular lists, the process is similar. When adding another element to the front, the next pointer of the new node points to the head, the previous pointer is set to where the head node was pointing to, the next node of the head node points to the new node, and the new node becomes the head.

To add an element to the end, the next pointer of the new node is set to the head. The previous pointer is then set to the previous node of the head node, the next node of the previous node pointed to the new node and the previous pointer of the head node pointed to the new node. This can be seen in the image.

### Skip List

A more complicated type of linked list is the skip list. This is a hierarchical structure, consisting of multiple linked lists. Typically, we have 1 list with sorted elements and a selection of other lists that contain some of these elements. These are chosen at random, with some elements being “skipped” over, hence the name. The main advantage is in more efficient operations. The structure allows for logarithmic time complexity because the chances are that we won’t need to search all of the elements in the list. Because of this, skip lists are used to index databases, implement dictionaries, manage caches, and for key-value pairs.

#### Example

This is a fairly complex list to implement, but a relatively simple example is here:

import random

class Node:
def __init__(self, key, level):
self.key = key
self.next_nodes = [None] * (level + 1)

class CustomSkipList:
def __init__(self, max_level, probability):
self.max_level = max_level
self.probability = probability
self.header = self.create_node(self.max_level, -1)
self.level = 0

def create_node(self, level, key):
new_node = Node(key, level)
return new_node

def random_level(self):
level = 0
while random.random() < self.probability and level < self.max_level:
level += 1
return level

def insert_element(self, key):
update_nodes = [None] * (self.max_level + 1)
current_node = self.header

for i in range(self.level, -1, -1):
while current_node.next_nodes[i] and current_node.next_nodes[i].key < key:
current_node = current_node.next_nodes[i]
update_nodes[i] = current_node

current_node = current_node.next_nodes[0]

if current_node is None or current_node.key != key:
new_level = self.random_level()

if new_level > self.level:
for i in range(self.level + 1, new_level + 1):
update_nodes[i] = self.header
self.level = new_level

new_node = self.create_node(new_level, key)

for i in range(new_level + 1):
new_node.next_nodes[i] = update_nodes[i].next_nodes[i]
update_nodes[i].next_nodes[i] = new_node

print("Successfully inserted key: {}".format(key))

def display_list(self):
print("\n***** Custom Skip List ******")
current_level = self.level
header_node = self.header

for level in range(current_level + 1):
print("Level {}: ".format(level), end="")
node = header_node.next_nodes[level]

while node is not None:
print(node.key, end=" ")
node = node.next_nodes[level]

print("")

def main():
custom_list = CustomSkipList(3, 0.5)
custom_list.insert_element(5)
custom_list.insert_element(2)
custom_list.insert_element(8)
custom_list.insert_element(3)
custom_list.display_list()

main()

### Unrolled List

This is a type of list where we store several elements within a single node. This is generally done to make the information more local, potentially speeding up operations like accessing data sequentially and querying ranges. Certain operations, such as inserting and deleting elements, can be less efficient, however, because we may have to split nodes as well as rearrange them. Unrolled lists can be advantageous, but usually only if the superior cache performance and reduced memory usage outweigh the slowing down of complex operations. As such, they’re used more thoughtfully than other types.

#### Example

To see how an unrolled list works, consider this code block:

class UnrolledListNode:
def __init__(self, capacity):
self.capacity = capacity
self.elements = [None] * capacity
self.next = None

class UnrolledList:
def __init__(self, node_capacity):
self.node_capacity = node_capacity
self.head = None

def insert(self, value):
if self.head is None:
self.head = UnrolledListNode(self.node_capacity)
self.head.elements[0] = value
return

current = self.head
while current.next is not None:
current = current.next

if None in current.elements:
index = current.elements.index(None)
current.elements[index] = value
elif len(current.elements) < current.capacity:
current.elements.append(value)
else:
new_node = UnrolledListNode(self.node_capacity)
new_node.elements[0] = value
current.next = new_node

def display(self):
current = self.head
while current is not None:
print(current.elements)
current = current.next

ulist = UnrolledList(3)
ulist.insert(5)
ulist.insert(2)
ulist.insert(8)
ulist.insert(3)
ulist.display()

This code is a little similar to the singly-linked list. But we have an additional attribute, “capacity”. We also check the value of the last element when adding a new element. If any value is set to “None”, this is updated with the new value. Otherwise, a new node is made, and we assign the value here. An example usage is in the image.

### Self-Adjusting List

This type is also known as a move-to-front list because elements are rearranged depending on when they’re accessed. After being accessed, they’re moved to the front of the list. This can improve efficiency since the most frequently used elements remain near the start of the list. While this won’t be useful when we need to maintain an order of elements, it can help speed up operations, such as web caching, file systems and even search algorithms.

#### Example

This code gives a short example of a self-adjusting list.

class SelfAdjustingList:
def __init__(self):
self.items = []

def insert(self, item):
if item in self.items:
self.items.remove(item)
self.items.append(item)

def search(self, item):
if item in self.items:
self.items.remove(item)
self.items.append(item)
return True
return False

def remove(self, item):
if item in self.items:
self.items.remove(item)

def display(self):
print(self.items)

sa_list = SelfAdjustingList()

sa_list.insert(5)
sa_list.insert(2)
sa_list.insert(8)
sa_list.insert(3)

sa_list.display()

print(sa_list.search(5))

sa_list.display()
sa_list.remove(2)
sa_list.display()

When searching for an element, the position is changed to the back of the list to maintain the self-adjusting behavior. We’ve added some items to the list, searched for an element, and removed an element. You can see the output in the image.

## Wrapping Up

Linked lists are one of the most versatile data structures, with many applications. They’re mostly used to manage databases, webpages, caches, and file systems. But they’re also used in traffic light systems, music players, data buffering and to implement various complex data structures. Whenever we’re dealing with elaborate datasets where we need dynamic behavior, it’s likely that some form of linked list will help us access and modify data more efficiently. While some operations can have extra overheads, when used thoughtfully, linked lists can improve performance.

## Understanding Applications Of Linked Lists, With Examples FAQs (Frequently Asked Questions)

What are linked lists used for?

Linked lists can be used for many things, including but not restricted to implementing data structures, managing caches, web history, file systems, GPS systems, and databases, or even managing music players and data buffering.

Are linked lists dynamic?

Yes, linked lists are dynamic structures, meaning they can grow or shrink as needed, when elements are inserted or deleted. This helps to make memory usage more efficient.

What different types of linked list are there?

There are many kinds of linked list, but the most common are singly-linked, doubly-linked, circular, and doubly-circular.

What are the advantages of linked lists?

The main advantages of linked lists are their dynamic behavior, memory management, efficient operations, low memory overheads and their flexibility.

What are the disadvantages of linked lists?

Disadvantages of linked lists compared to arrays are that they’re inefficient for small elements as well as random access and insertion and deletion operations. They also don’t have the constant-time complexity of list size retrieval, like arrays do.

#### Duncan Dodsworth, Author for History-Computer

Duncan Dodsworth is a writer at History Computer. If you find yourself reading an article about games, tech, or coding, you might see his name there. He majored in chemistry but realized he's much more comfortable behind a keyboard than a conical flask. When he's not tapping away, he's probably listening to music or reading a book about half as often as he says.

Read articles by Duncan Dodsworth