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. 3x² + 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.

The image featured at the top of this post is ©Profit_Image/Shutterstock.com.