Linked Lists Data Structures

Why Linked Lists

While arrays are a great way to store data, they require the programmer to know the size of the array upfront. This is because arrays are stored contiguously in memory. That means the first element of the array is stored at the first memory address. The computer reserves the required amount of memory when the array is created, and when we start storing data, it begins at the start of the reserved memory and continues sequentially from there.

But we are programmers—we don’t always know the exact array size ahead of time. Requirements change, and programmers must adapt. So, we invented linked lists. Each item in a linked list has a pointer to the next element. We don’t have to declare the size of a linked list at the beginning because the stored items can be located anywhere in memory. You only have to follow the pointer to the next element.

A Linked List under the hood

Every Linked List it consists of the following properties

• The Node: The node is the basic data structure of the linked list. Each node consists of the data and a pointer to the next node
• The head: This is the first element of the linked list. It points to the first node from where we begin traversing the linked list.
• The tail (optional): As we have always available the first node we must have always available the last node of the linked list.

Actions of a Linked List

• Traversal: The act of moving through the list until reaching the end.
• Insertion: Show the "pointer swap"—breaking a link and inserting a new node in between.
• Deletion: Skipping a node by pointing the "previous" node directly to the "next" node.

Example

The first thing we must do is to create the node. Each node must have a data and a pointer that will show the next node in the linked list. We also must create the basic data structure of a Linked List.

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

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

Now, we are ready to start adding actions of a Linked List. Let's start with traversing the linked list and printing its elements. The next methods must be part of the Linked List class we wrote before.

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

We can't have an empty Linked List. There is no point to it. So, we need a method that we can add a new node in the linked list. To make our life easier for the example we will only be able to add a new node at the beginning of the linked list. A good excersise for you would be to add a method that can add a new node at the end of the linked list or after a specific node.

def insert_at_beginning(self, new_data):
    new_node = Node(new_data)
    # Point new node to the current first node
    new_node.next = self.head
    # Make the new node the head
    self.head = new_node
                                            

Finally, we also need to be able to delete a node. To do that we need to find the node that holds the data we want to delete and point the previous node to the next node. We have to consider the case when the node we want to delete is the first node of the linked list or when Linked List is empty. Keep in mind that this method can be teach you how you can insert a new node after a specific node.

def delete_node(self, key):
    current = self.head

    # Case 1: If the head node itself holds the key
    if current is not None and current.data == key:
        self.head = current.next
        current = None
        return

    # Case 2: Search for the key, keep track of the previous node
    prev = None
    while current is not None and current.data != key:
        prev = current
        current = current.next

    # If the key was not found
    if current is None:
        return

    # Unlink the node from the linked list
    prev.next = current.next
    current = None
                                            

And here is the final code.

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

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

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

    def insert_at_beginning(self, new_data):
        new_node = Node(new_data)
        # Point new node to the current first node
        new_node.next = self.head
        # Make the new node the head
        self.head = new_node

    def delete_node(self, key):
        current = self.head

        # Case 1: If the head node itself holds the key
        if current is not None and current.data == key:
            self.head = current.next
            current = None
            return

        # Case 2: Search for the key, keep track of the previous node
        prev = None
        while current is not None and current.data != key:
            prev = current
            current = current.next

        # If the key was not found
        if current is None:
            return

        # Unlink the node from the linked list
        prev.next = current.next
        current = None
                                            

Now that we have all the methods we need, we can test our Linked List class.

llist = LinkedList()
llist.insert_at_beginning(10)
llist.insert_at_beginning(20)
llist.insert_at_beginning(30)

llist.print_list()    # Output: 30 -> 20 -> 10 -> None
llist.delete_node(20)
llist.print_list()    # Output: 30 -> 10 -> None
                                            

Conclusion and More to learn

Linked Lists are crucial in computer science and have many advantages and application. The most important advantage is that they are dynamic in size, and they can be easily extended or reduced in size as needed. But, everything has a price. Linked Lists are slower than arrays because they require more memory to store the data. When to use them? Linked Lists are a good choice when you need to store a large number of elements in a sequential order.

There are other variations of Linked Lists, such as Circular Linked Lists and Doubly Linked Lists. The main difference is that besides a next pointer have a previous pointer (Doubly Linked Lists) or the next pointer of the last node points to the first node (Circular Linked Lists).