# Understanding Applications Of Linked Lists, With Examples

Along witharrays,linked listsare a very common kind of lineardata structure. These are similar to an array, but there are differences in how the data is stored and accessed. In addition, linked lists’ uses differ from those of arrays. We will quickly define linked lists in this post before delving into how they are used in both computer science and everyday life.

Although linked lists and arrays both store elements sequentially, arrays do not. 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.

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

def __init__(self):

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

def display(self):
else:
while current:
print(current.data, end=" -> ")
current = current.next
print("None")

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.

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

def __init__(self):

def is_empty(self):

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

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

def display(self):
if self.is_empty():
else:
while current:
print(current.data, end=" ")
current = current.next
print()

def display_reverse(self):
if self.is_empty():
else:
while current.next:
current = current.next
while current:
print(current.data, end=" ")
current = current.prev
print()

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

def __init__(self):

def is_empty(self):

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

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

def display(self):
if self.is_empty():
else:
while True:
print(current.data, end=" ")
current = current.next
break
print()

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

def __init__(self):

def is_empty(self):

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

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

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

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 forlogarithmic time complexitybecause 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.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.level:
for i in range(self.level + 1, new_level + 1):
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

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

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

def insert(self, value):
return

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

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.

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