Linked List Explained

9 min readMay 24, 2023

Hello there! I’d like to take a moment to introduce you to one of the fundamental data structures in computer science: the linked list. In this article, we will explore what a linked list is, discuss scenarios where it is commonly used, analyze its time and space complexity, and present its pros and cons.

Overview

A linked list is a linear data structure consisting of nodes, where each node contains data and a reference (or pointer) to the next node in the sequence. Unlike arrays, which use contiguous memory, linked lists use dynamic memory allocation. This allows for efficient memory utilization and provides flexibility in adding, removing, or modifying elements within the list.

To put it more simply, a Linked List is a linear data structure, where elements are stored at non-contiguous locations. A Linked List is like a chain made of nodes and the links are pointers.

Pointers are connections that hold the pieces of linked structures together.
Pointers represent the addresses of a location in memory.

A node is a fundamental building block that stores both data and a reference (or pointer) to the next node in the sequence. Each node can be thought of as a container that holds a piece of information or data.

Depending on the type of linked list, nodes can have both a nextand previouspointer allowing list bi-directional traversal or only have a nextpointer which allows uni-directional traversing (i.e., you can only go forward, rather than both forwards and backwards).

Let’s break down the components of a node:

Data: The data component of a node represents the actual information that the node is intended to store. It can be any type of data, such as integers, strings, objects, or even complex data structures.
Next Pointer: The next pointer is a reference or address that points to the next node in the linked list. It establishes the connection between nodes and enables traversal from one node to another. In a singly linked list, the next pointer points to the succeeding node, while in a doubly linked list, there can be additional pointers for the previous node as well.

In Python, the node class is defined as such:

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

In this example, the Node class has two attributes: data to store the actual data and next to hold the reference to the next node. The next attribute is initialized to None as the node is not initially connected to any other node.

To create a linked list, multiple nodes are linked together by updating the next pointer of each node to point to the next node in the sequence. The last node in the list typically has its next pointer set to None to indicate the end of the list.

Nodes serve as the building blocks of linked lists, allowing for efficient traversal, insertion, and deletion operations within the list. They encapsulate both data and the connectivity information necessary to form a linked structure.

There are many different types of linked lists

Singly Linked List: consists of a list of nodes, each with next pointers, allowing uni-directional travel
Doubly Linked List: each node has two pointers, this allows you to traverse bi-directionally, backwards and forwards, rather uni-directionally for a linked list
Circularly Linked List: the tail node points to the head node, can be either singly linked or doubly linked

Why use a Linked List?

Linked Lists can be used to implement other common abstract data types, including lists, stacks, & queues.
Preferred data structures over arrays because elements can be easily inserted or removed without reallocation or reorganization of the entire structure

Advantages

Dynamic Size (there is no need to ever resize a linked list)
Quick insertion / deletion of nodes because you can change the pointers for each node

Disadvantages

Very slow when it comes to access and search; we have to sequentially iterate over each element starting at the head. Unlike an array, you don't have the option of random access.
Extra space for the pointer
More memory is required than compared to an array or list data structure due to the fact that linked lists require pointers

Big-O Analysis

The time and space complexity for a linked list with n elements are as follows:

Time Complexity

Accessing an element: O(n) - In a singly linked list, accessing an element requires traversing the list from the head node to the desired position, which takes linear time proportional to the number of elements n.
Insertion/Deletion at the beginning: O(1) - Inserting or deleting a node at the beginning of a linked list can be done in constant time as it involves updating the head pointer.
Insertion/Deletion at the end: O(n)
Inserting or deleting a node at the end of a linked list requires traversing the entire list, which takes linear time.
Insertion/Deletion at a specific position: O(n)- Inserting or deleting a node at a specific position in the linked list requires traversing the list to reach that position, which takes linear time.
Searching for an element: O(n) - Searching for an element in a linked list requires traversing the list until the element is found or the end of the list is reached, resulting in a time complexity of O(n).

Space Complexity

The space complexity of a linked list is O(n) as it requires memory to store n nodes. Each node contains data and a reference to the next node, which contributes to the overall space complexity linearly with the number of elements.

It’s important to note that these time and space complexities are general for a standard singly linked list implementation. However, specific optimizations or additional data structures within the linked list implementation might affect the complexity.

Fig. **Big-O Visualized**: Lines made with the very excellent **Desmos** graph calculator. You can play with this graph here.

Linked List Code Implementation

class Node:
  # Node constructor for a Singly Linked List
    def __init__(self, data=None):
        self.data = data
        self.next = None

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

    # Insert new node into list
    def insert_node(self, data):
       # Create a new node from given data
        new_node = Node(data)
         # Check if the list is empty
        if self.head is None:
          # If so, set the new node to be the head
            self.head = new_node
        else:
           # Otherwise, start at the head of the list
            current = self.head
            while current.next is not None:
                # update the current node to point to the next node
                current = current.next
             # update the next node to be the current node
            current.next = new_node

    # delete a node from the list
    def delete_node(self, data):
        # Check if the list is empty first to avoid bugs
        if self.head is None:
            return
        # Check if the node we are looking for is at the head
        if self.head.data == data:
            # if so, remove it by assigning it to the next value
            self.head = self.head.next
            return
        current = self.head

        # Loop to the end of the list
        while current.next is not None:
            # start searching for the matching node
            if current.next.data == data:
                # when a match is found, update the pointers to skip over it
                current.next = current.next.next
                return
            # clean up
            current = current.next

    # search for a node in the list
    def search_list(self, data):
        # Start at the head of the list
        current = self.head
        # Loop to the end of the list
        while current is not None:
          # start searching for the matching node
            if current.data == data:
                # match found
                return True
            current = current.next
        # match NOT found
        return False

    # access a given node out of the list
    def access_node(self, index):
        # Start at the head of the list with a count size of zero
        current = self.head
        count = 0
        # Loop to the end of the list
        while current is not None:
            # check if we find a match
            if count == index:
                return current.data
            # update the count and move onto the next node
            count += 1
            current = current.next
        return None

    # display the values in the list
    def display(self):
      # Create a new node from given data
        current = self.head
        # Loop to the end of the list
        while current is not None:
            # print every value with a space
            print(current.data, end=" ")
            current = current.next
        print()

# Example usage:
my_list = LinkedList()
my_list.insert_node(5)
my_list.insert_node(10)
my_list.insert_node(15)
my_list.insert_node(20)
my_list.display()  # Output: 5 10 15 20

print(my_list.search_list(15))  # Output: True
print(my_list.search_list(25))  # Output: False

print(my_list.access_node(2))  # Output: 15
print(my_list.access_node(5))  # Output: None

my_list.delete_node(10)
my_list.display()  # Output: 5 15 20

Let’s run through an example

Let’s go over a problem together to better understand linked Lists. Today we will attempt LeetCode problem 206 Reverse Linked List. In this problem, we are given the head of a singly linked list and are asked to return the list in reversed order.

For example, we are given a linked list with the input value of head = [1, 2, 3, 4, 5]. The desired output should be [5, 4, 3, 2, 1].

So, how do we achieve this?

Let’s use the Two Pointer technique. Note that because we are given a singly linked list we do NOT have previous pointers, thus we are unable to simply refer back to a previous node.

Pseudocode

To reverse a singly linked list using two pointers, you can use the following approach:

Initialize three pointers: previous to keep track of the previous node, current to keep track of the current node, and next_node to keep track of the next node.
Start with previous and current pointing to None and head (the first node of the list), respectively.
Iterate through the list using a loop until the current pointer becomes None:

Update next_node to the next node of current.
Reverse the link of current by pointing it to the previous node.
Move previous and current one step forward by assigning current to previous and next_node to current.

Finally, update the head pointer to previous, which will now be pointing to the new first node of the reversed list.

Code Implementation

# Using the two pointer technique
def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        # Initialize prev pointer as NULL
        prev = None
        # Initialize the cur pointer as the head
        cur = head
        # Run a loop util cur points to NULL
        while cur:
            # Initialize next pointer as the next pointer of cur
            next = cur.next
            # Now assign the prev pointer to cur’s next pointer
            cur.next = prev
            # Assign cur to prev, next to cur
            prev = cur
            cur = next
        # Return the prev pointer to get the reverse
        return prev

When to Use a Linked List

A linked list is a good choice in the following situations:

Unknown number of items: If you don’t know how many items will be in the list, a linked list is convenient because it allows for easy addition of items.
No need for random access: If you don’t need to access elements at specific indexes in the list, unlike with an array, a linked list can be used.
Insertion in the middle: If you need to insert items in the middle of the list, a linked list is suitable for this task.
Efficient insertion and deletion: If you require fast insertion and deletion operations without the need to shift other elements, a linked list performs these operations in constant time.