The Impact and Implementation of Linked Lists

The Linked List is a main component for most data structures: Queues, Stacks, Hash tables, and more. While queues and stacks can be built with arrays, there are problems with using arrays. Arrays have limits, so if too many nodes are added to a queue or stack array, you can result with a stack overflow, meaning that there are more nodes than there is space for. With this, it’s no surprise that it is one of the most important to master among all data structures. Today, we’ll be discussing the implementation of a Singly Linked List.

Let’s take a look at what exactly a singly linked list is,

At first glance, you might be wondering, why are there arrows? What is that “next” box? What is “None” at the end there? Linked Lists are made of class objects called Nodes. Each node has one attribute: next. Each node’s next points to the next node, which then points to another, and then another, eventually leading to the end of the Linked List, a.k.a, the tail. The linked list itself has two attributes, the head, which is the first node in the linked list, and the tail, which is the last node in the linked list. This last node points to null, or None. With these attributes, you simulate a list, but with more possibilities and methods. Let’s take a look at what methods we can make and how we can use them.

push

This one is simple, in order to change and manipulate linked lists, you simply change the “next” attribute of affected nodes. Here, to make the push method, you simply create a new node, assign the old head as the newer node’s next(since the new node will now be in front) and assign the head as the new node.

def push(self, new_node):
    new_node = Node(new_node)
    new_node.next = self.head
    self.head = new_node

Here is what the code above is doing visualized!

remove

Now, this one is a little more complicated than the last one. With remove, you can now remove a node that you previously pushed that you don’t want anymore! “Removing” a node isn’t actually getting rid of the node. You remove a node from a linked list by getting rid of all paths to the targeted node (node to be removed). You can do this by making the node ahead of the target node’s next as the target node’s next. You don’t have to touch the targeted node’s next.

def remove_song(self, target):
    current_node = self.head
    temp_node = None
    if self.head == target:
        self.head = self.head.next
        return
    while current_node != None:
        temp_node = current_node
        current_node = current_node.next
        if current_node == target:
            temp_node.next == current_node.next
            return True
    return False

Here is what the code above is doing visualized!

print_all

How could we forget testing and visualizing the actual linked list? With the print_all method, you can see exactly whats inside your linked list at its correct order. For this method, we will be creating a new array and appending the linked list’s items into it by traversing through the linked list. You can traverse through the linked list by assigning a tool node, in this case, we’ll call it current_node. With a while loop, the current_node will do whatever it needs to do and then change its value to whatever is after it until it hits the end of the linked list.

def print_all(self):
    temp = []
    if self.head:
        current_node = self.head
        while current_node = self.head
            temp.append(current_node.data)
            current_node = current_node.next
    print(temp)

Congratulations! You implemented the most basic and simple form of a singly linked list! You can now add your own methods and utilize it in many different ways.