Home

Linked List

Photo by Sandy Millar

This post is part of the Data Structures series.

Introduction

A linked list is a collection of nodes that form a linear sequence. The difference between an array and a linked list is that the array has indexed elements, so we can get an element by constant time by just searching by its index. In the linked list, we need to go through the nodes to get the searched element and that takes linear time.

The advantages is that the linked lists can insert and remove items in constant time.

Concepts and Implementations

The Node

A Linked List is a sequence of nodes and each node has two attributes: the value it stores and the reference to the next node of the sequence.

The first and last nodes are called head and tail of the list, respectively. So to get to the tail of the last, we traverse the linked list by moving from one node to another using the each node's next reference.

The Linked List having the head and the tail as attributes helps adding new nodes to the start and the end of the list. But we can implement it with or without the tail attribute. We will dive in into the this implementation.

We can separate the linked list from its elements. Each element is a node and we can implement this representation with a Node class.

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

Basically it has a value and the reference to the next node. We add a default value (None) to the next parameter to make it more flexible to use when creating new nodes.

The simplest way to use it is:

new_node = Node(1)
new_node.value  # 1
new_node.next  # None

But with the flexibility of the next parameter, we can also use it by passing the next node reference.

next_node = Node(2)

new_node = Node(1, next_node)
new_node.value  # 1
new_node.next.value  # 2

Creating a base for the Linked List

For the linked list, the first step is to create a class representing it. For now we just want a head attribute when creating an empty list.

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

Simple as that. Just a class and initialize the head attribute with None for an empty list.

is_empty method

Let's implement the easier method: is_empty. How do we know when a list is empty? If the head is None, we didn't add any node to this list. This is the logic behind the is_empty method.

def is_empty(self):
    return self.head is None

Pretty simple, huh?

prepend method

Now the prepend method. We basically need to create a new node, points the next attribute from this new node to the head and assign this new node to be the new linked list head.

Remember we have a next parameter when creating a new node? We can use it to assign the previous head when creating the new node. Something like this:

Node(value, previous_head)

In the context of the linked list, we will have the self.head. So:

Node(value, self.head)

The last step is to assign this new node to the head and we will prepend it.

self.head = Node(value, self.head)

The complete method will be like:

def prepend(self, value):
    self.head = Node(value, self.head)

Just one line. Pretty good!

append method

For the append, it's a bit different, because, instead of add a new node to the head of the list, we need to add to the tail. So basically we need to iterate through the list to be in the last node and point it's next attribute to the new created node.

The question is: How do we iterate through the list?

The difference between the tail node and the rest is the next attribute. The tail has no next. It points to None. The rest always point to a different node.

To iterate through the list to get the last node, we get the next node until the node has no next attribute. Start with the first node: the head.

current_node = self.head

And the iterate.

while current_node.next is not None:
    current_node = current_node.next

We divide this code in two parts:

When the while loop breaks, we have the last node, so we just need to update the last node next attribute.

current_node.next = Node(value)

The complete code:

current_node = self.head

while current_node.next is not None:
    current_node = current_node.next

current_node.next = Node(value)

But this code will break if the linked list is empty, because the head is None, it can't have a next attribute.

In this case we just make a condition for emptiness. If it is empty, we just assign the new node to the head.

def append(self, value):
    if self.is_empty():
        self.head = Node(value)
        return

    current_node = self.head

    while current_node.next is not None:
        current_node = current_node.next

    current_node.next = Node(value)

size method

For the size method is straightforward. We basically need to iterate through the whole list and count each node.

To iterate is pretty simple. We just need to loop while the current node is not None.

while current_node is not None:
    current_node = current_node.next

And for each iteration, we need to increase our counter.

def size(self):
    list_length = 0
    current_node = self.head

    while current_node is not None:
        list_length += 1
        current_node = current_node.next

    return list_length

search method

For the search algorithm, we need to receive a value and return True or False if the this value is in the linked list.

So we basically need to iterate through the linked list searching for this value.

The iteration is simple:

while current_node is not None:
    current_node = current_node.next

Now, for each node, we see if the current node value is the same as the searched value.

while current_node is not None:
    if current_node.value == value:
        return True

    current_node = current_node.next

We can do this way to return True if the searched value is found. Or we can defined a found variable and use it to set it to True when find it and get out of the loop.

while not found and current_node is not None:
    found = current_node.value == value
    current_node = current_node.next

We define the found and current_node before iterating and return if we found the searched value or not.

def search(self, value):
    found = False
    current_node = self.head

    while not found and current_node is not None:
        found = current_node.value == value
        current_node = current_node.next

    return found

remove method

The last method to be implemented is the remove method. We can think about this method in separated cases:

For the empty case is pretty simple. We just check the list with our is_empty method.

if self.is_empty():
    return

We can also throw an error exception or just print "The list is empty", for example.

For the case when we want to remove the head node, we check it first and them remove it.

if self.head.value == value:
    self.head = self.head.next
    return

To remove it, we just need to point the head to the its next node.

The last case is when we want to remove a node in the middle or the last one. Let's draw it!

For this algorithm, what we want is to get the previous node of the node to be removed and point to the next node of the node to be removed. So we need to have the previous node in each iteration. This is the fundamental part of our algorithm.

while current_node.next is not None:
    if current_node.next.value == value:
        current_node.next = current_node.next.next
        return

    current_node = current_node.next

This is the algorithm.

We will iterate through the list while the current node's next is not a None value. Why? Because we want to compare the next node value. Not the current one.

if current_node.next.value == value:

This the logic we are searching for. Does the current node's next value is the value we want to remove?

If it is True, we basically remove the current node's next node by point the next to the next.next, and return the function.

If it is False, we keep iterating until we find the value we want or when we finish the entire list.

Joining all the parts, we have:

def remove(self, value):
    if self.is_empty():
        return

    if self.head.value == value:
        self.head = self.head.next
        return

    current_node = self.head

    while current_node.next is not None:
        if current_node.next.value == value:
            current_node.next = current_node.next.next
            return

        current_node = current_node.next

The Linked List class

Joining all the parts we talked and implemented, we have:

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


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

    def append(self, value):
        if self.is_empty():
            self.head = Node(value)
            return

        current_node = self.head

        while current_node.next is not None:
            current_node = current_node.next

        current_node.next = Node(value)

    def prepend(self, value):
        self.head = Node(value, self.head)

    def remove(self, value):
        if self.is_empty():
            return

        if self.head.value == value:
            self.head = self.head.next
            return

        current_node = self.head

        while current_node.next is not None:
            if current_node.next.value == value:
                current_node.next = current_node.next.next
                return

            current_node = current_node.next

    def search(self, value):
        found = False
        current_node = self.head

        while not found and current_node is not None:
            found = current_node.value == value
            current_node = current_node.next

        return found

    def is_empty(self):
        return self.head is None

    def size(self):
        list_length = 0
        current_node = self.head

        while current_node is not None:
            list_length += 1
            current_node = current_node.next

        return list_length

Let's test it!

I basically created three helper functions to help us to test our linked list.

def print_all(linked_list):
    print('All values:', end=' ')
    current_node = linked_list.head

    while current_node is not None:
        print(current_node.value, end=' ')
        current_node = current_node.next

    print()


def print_found(linked_list, value):
    found = linked_list.search(value)
    print('For value:', value, '-->', 'Found:', found, )


def print_size(linked_list):
    list_length = linked_list.size()
    print('Size:', list_length)

They will print all the value, the found value, and the size of the list. So first we instantiate our list:

linked_list = LinkedList()

Let's see what we get when we try to print all the values and its size:

print_all(linked_list)
print_size(linked_list)  # 0

Yes, no values and 0 elements.

We can append a node with value 1, print the values, and see its size.

linked_list.append(1)
print_all(linked_list)  # 1
print_size(linked_list)  # 1

If we try to remove 0, the 1 is still there. But if we remove 1, we have no nodes anymore. The first line is cool: it doesn't break if we try to remove an element that doesn't exist in the linked list.

linked_list.remove(0)
print_all(linked_list)  # 1
linked_list.remove(1)
print_all(linked_list)

Adding new nodes and printing them:

linked_list.append(2)
linked_list.append(3)
print_all(linked_list)  # 2 3
print_size(linked_list)  # 2

Let's try out found method:

print_found(linked_list, 1)  # False
print_found(linked_list, 2)  # True
print_found(linked_list, 3)  # True

That's cool! We really don't have the 1 node, but we have the 2 and the 3.

Now printing after removing each node:

linked_list.remove(1)
print_all(linked_list)  # 2 3
linked_list.remove(2)
print_all(linked_list)  # 3
linked_list.remove(3)
print_all(linked_list)

Let's try out prepend method:

linked_list.prepend(4)
linked_list.prepend(3)
linked_list.prepend(2)
linked_list.prepend(1)
print_all(linked_list)  # 1 2 3 4

And remove the 3.

linked_list.remove(3)
print_all(linked_list)  # 1 2 4

Works fine!

My Twitter and Github


Resources

Patreon Become a Patron Coffee icon Buy me a coffee