Data Structures — 1: Linked Lists

8 min readDec 11, 2023

One of the fundamental topics in computer science that must be understood is data structures. Even though data ultimately consists of 0 and 1, dealing with them is not as easy as it seems. Let’s examine one of these structures, linked lists.

Why Linked Lists?

The conditions and scenarios in which we will struggle with data are not always the same. Before we can determine the data structure we need, we have to determine what is very important to us and what we can sacrifice. Let’s imagine a situation:

We have no hardware memory shortage, we have plenty of space.
The data we need to keep will remain in the desired order, but it must remain distributed in memory.
We need to be able to dynamically add and remove data at runtime.
The list needs to be scalable.
We want to make it efficient to add or remove a new node between any two nodes of the list.
The size of our data is very variable. We cannot predict what kind of data will come.

We can think of linked lists for such situations.

What is a Linked List and How is it Linked?

We call each element in a linked list a node. A linked list node basically consists of three parts: Head, data, next.

Minimal Node Structure Diagram by Cagatay URESIN

Head

Every list has a first element, right? There are two ways to store data at the beginning:

The memory address of the first element of the list
True or false whether the current node is the head of the list

Keeping the memory address will take a little more space per element than the other option, but if there are a lot of elements, it is more advantageous to keep the memory address as it is harder to find the beginning of the list. In the scenario where the memory address is kept, changing the first element of the list requires updating the entire node, whereas in the other option it is much easier.

Data

The data part of the node is where the data itself is stored. Its size does not matter. The type of data inside does not matter at all.

It holds the address in memory of the next element in the list. This is what makes a linked list linked. Since the last element of the list will not be followed by the next element, that part will be null.

Index (optional)

Keeping the order of the elements in the list is advantageous when you need to insert new data. For example, when you need to insert new data between the 5th and 6th element of the list, or when you need to find, read, update or delete the desired data, it is useful to have the data’s own IDs.

Linked List Types

Singular/Singly Linked List

This is the base type that has been used as a basis for this part of the article. This list has two ends. It has a beginning and an end. The last node points to null instead of the next element.

Doubly Linked List

Each node holds the address of the next element as well as the address of the previous element.

Circular Linked List

This data has no end. The last element of the list indicates that the next node is the head.

Doubly Circular Linked List

This data type is both cyclic and double linked.

Linked List Algorithm and Python Example

The UML diagram of the linked list structure, which we will realize the example of in a moment, is as follows:

As seen in the diagram, the list will control the items to be created from the node class, but it only knows which node is the head and the length of the list. Because we will plan the operations according to the head node.

The node only knows its own data and the next node without keeping its index.

Let’s see it in action with Python.

Node Class

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

    def __str__(self) -> str:
        return f"{self.data}"

In simple form the node class will be as above. Each node is appended to the end by default, so there are no next. The constructor method creates the node instance by directly taking the data that the node class will receive. In Python, we override the str() method in the node class in order to use the str() built-in function, which allows us to see the data contained in the node instance in string type. The linked list class will manage the processing methods, so this is the structure of this class.

Linked List Class

The constructor method of the linked list class is as follows:

def __init__(self) ->None:
    self.head = None
    self.lenght = 0

As you can see, one of the two data that this class holds is the reference to the head node and the length of the list. Since the list does not hold any data at the time of creation, the constructor method will start with these two data as static variables.

Since we want to know the length of the list in Python, we also override the len() function in this class.

def __len__(self) -> int:
    return self.lenght

We also override the __str__(self): method of this class so that our list corresponds to the str() and print() methods, but this time with a little style.

def __str__(self) -> str:
    elements = []
    current_node = self.head
    while current_node:
        elements.append(str(current_node))
        current_node = current_node.next
    return " -> ".join(elements)

The output of this code will look like this:

0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9

Moreover, we will check if the list is empty with the following method:

def is_empty(self):
      return self.lenght == 0

Since we will need to constantly check if the requested index exists in our list, we add the following method as hidden.

def __index_suits(self, index: int) -> bool:
    if not self.is_empty() and 0 <= index < self.lenght:
        return True
    else:
        raise IndexError("Index out of bounds")

Let’s talk about CRUD operations.

Append:

Our flowchart for the append method, which is a must for every list, will be as follows:

First we check whether the list is empty or not. If the list is empty, the first element will be the head node of the list; if not, we find the last node of the list, write the new element to the next element of the last node and update the length of the list when the insertion is complete.

def append(self, data) -> None:
    new_node = Node(data)
    if self.is_empty():
        self.head = new_node
    else:
        last_node = self.head
        while last_node.next:
            last_node = last_node.next
        last_node.next = new_node
    self.lenght += 1

Prepend:

Prepend costs less. We simply put the head node after the new node, declare it the head node, update the length and finish.

def prepend(self, data) -> None:
    new_node = Node(data)
    new_node.next = self.head
    self.head = new_node
    self.lenght += 1

Get:

With the Get method, we will get the node with a certain index. This will make it easier for us to write the next methods.

def get(self, index: int) -> Node:
    self.__index_suits(index)
    current_node = self.head
    if index == 0:
        return current_node
    for _ in range(index):
        current_node = current_node.next
    return current_node

Insert:

The insert method is a bit more complicated, but since we have append and prepend, we will pass operations with index 0 and end to append and prepend.

Here we pull the previous node from the desired index. We add the address of the new node to the next node after the previous one and the address of the old one to our new node.

def insert(self, index: int, data) -> None:
    self.__index_suits(index)
    if index == 0:
        self.prepend(data)
    elif index == self.lenght - 1:
        self.append(data)
    else:
        new_node = Node(data)
        current_node = self.get(index-1)
        new_node.next = current_node.next
        current_node.next = new_node
        self.lenght += 1

Update:

We will have an extremely simple update method.

def update(self, index: int, data) -> None:
    self.__index_suits(index)
    current_node = self.get(index)
    current_node.data = data

Delete:

Without a doubt, this seems to be the most complicated operation, but in fact, when it comes to linked lists, it is possible to solve this by bypassing the element to be deleted in the chain. We just pretend we don’t know about that data.

def delete(self, index: int) -> None:
    node_to_delete = self.get(index)
    if index == 0:
        if node_to_delete.next:
            self.head = node_to_delete.next
        else:
            self.head = None
    else:
        prev_node = self.get(index - 1)
        prev_node.next = node_to_delete.next
    self.lenght -= 1

In the Delete method, we pay attention when deleting the head and end node. First of all, if the node to be deleted is the head node, the second thing to check is whether there is a node after the head node. If there is only one head node in the list, if we delete it, the list will be empty. If there is a node after it, we declare it the new head node and we are done.

If the node to be deleted is the last node, we delete the next to last node after capturing the previous node.

If it is not one of them, we bypass this node by writing the address of the node after the node to be deleted in the next part of the node before the node to be deleted.

We finish by updating the list length.

That’s how simple it is to implement a Singleton Linked List in Python. You can access the Github Repository for the full code.

Advantages and Disadvantages of Linked Lists

In computer science, there are no absolute advantages.

Advantages:

Dynamic memory management
Variable dimension status
Ease of addition and subtraction

Disadvantages:

Difficulty in random access
Transaction cost
More memory needed

Conclusion

One way or another, linked lists are part of computer science. Even if we never feel the need to use them, it is useful to know what they are. Stay in good health.