Linked List Data Structure Simplified
Tags: dsa, datastructures, linkedlist, python
Published: 2023-07-18 03:02:11

Many developers run away from data structures and algorithms because of how difficult it is perceived to be. In this article, I will try my best to make you understand one of the data structures called Linked List.

**Linked List** is a non-contiguous data structure, and a collection of nodes in which each node consists of a data and a reference or pointer to the next node. The first node is called Head while the last node is called Tail with its next node pointing to None.

There are not too many places where you can utilize a linked list, but as a good developer, it is important to get a good grasp of it to enable you understand how data structures are created along with the different operations that are performed on them.

In this article, we will be using the python programming language to create a Linked List with various operations that can be performed on it such as reading, modification, and deletion.

1. You need to create a Node class with a data and next_node properties.

```
# A Node class.
class Node:
    data = None
    next_node = None

    # Initializes this class with a data argument whenever an object is created
    def __init__(self, data):
        self.data = data

    # Provides a more readable string representation of the class object
    def __repr__(self):
        return "<Node Data: %s>" %self.data

```
The init method is python's built-in method called anytime an instance of the Node class is created. 
The repr method is a python built-in method that gives the liberty to produce a more readable representation of the Node class. You can test your code using the python interpreter.
To access the interpreter, you need to have python installed on your PC. You download it from [here](https://www.python.org/downloads/)
Open your terminal, and type in the below code and click enter.

```
python -i <the name of your file>
```
Make sure you are on the directory where your code file is located.
The interpreter will open, and you can go ahead to test your code, like the example below.
```
$ python -i linked_list.py 
>>> N1 = Node(20)
>>> N1
<Node Data: 20>
>>>
```
2. Create a LinkedList class and set head to None

```
# A Linked list class 
class LinkedList:
    # Initializes class whenever an instance is created
    def __init__(self):
        self.head = None
```
We will start creating the different operations that can be carried out on a Linked List. After the init method, let's start by creating an **add** method that will add a node to the beginning of the List.

```
    # Adds a node to the start of a list
    def add(self, data):
        new = Node(data)
        new.next_node = self.head
        self.head = new


    # Adds a node to the end of a list and returns its new size
    def addToEnd(self, data):
        current = self.head
        new = Node(data)
        count = 0
        added = False
        if current is None:
            self.head = new
        else:
            while current and not added:
                count += 1
                if current.next_node is None:
                    current.next_node = new
                    added = True
                else:
                    current = current.next_node
        return count + 1
```
implementation on python's interpreter
```
$ python -i linked_list.py
>>> l = LinkedList()
>>> l.add(2)
>>> l.add(5)
>>> l.add(3)
>>> l
[HEAD: 3]-->[5]-->[TAIL: 2]
>>> 
```
From the above example, you will notice a chain-like representation of the class instance. Like the Node class, it is created using the python's built-in repr method. see code below
```
    # Provides a more readable string representation of the class instance
    def __repr__(self):
        nodes = []
        current = self.head

        while current:
            if current is self.head:
                nodes.append("[HEAD: %s]" %current.data)
            elif current.next_node is None:
                nodes.append("[TAIL: %s]" %current.data)
            else:
                nodes.append("[%s]" %current.data)
            current = current.next_node
        return "-->".join(nodes)
```
Next, is an insert method which creates and inserts a node at a specified index argument.

```
    # Adds a node at a specified index in the list.
    def insert(self, data, index):
        current = self.head

        if index == 0:
            self.add(data)
        else:
            new = Node(data)
            while index > 1:
                index -= 1
                current = current.next_node
            prev = current
            next_node = current.next_node
            prev.next_node = new
            new.next_node = next_node
```
Testing with interpreter.
```
$ python -i linked_list.py
>>> l = LinkedList()
>>> l.add(2) 
>>> l.add(5)
>>> l.add(12)
>>> l.add(6)
>>> l
[HEAD: 6]-->[12]-->[5]-->[TAIL: 2]
>>> l.insert(88, 1)
>>> l
[HEAD: 6]-->[88]-->[12]-->[5]-->[TAIL: 2]
>>>
```
Now, let's add a method that will return the length of the list
```
# Counts and returns the total number of nodes in a list by traversing through it 
    def size(self):
        count = 0
        current = self.head

        while current:
            count += 1
            current = current.next_node

        return count
```
You can test it using the interpreter following the way we did earlier.
Next, let's add a method that deletes a node from the list
```
    # Traverses through the list and removes the first node which data corresponds to a given or specified argument.
    # It returns the removed node.
    def remove(self, key):
        current = self.head
        prev = None
        found = False

        while current and not found:
            if current.data == key and current is self.head:
                found =True
                self.head = current.next_node
            elif current.data == key:
                found = True
                prev.next_node = current.next_node
            else:
                prev = current
                current = current.next_node
        return current

    # Removes a node at a specified index from the list. It returns the removed node.
    def removeAtIndex(self, index):
        current = self.head
        prev = None

        if index == 0:
            self.head = current.next_node
        else:
            while index > 0:
                index -= 1
                prev = current
                current = current.next_node
            prev.next_node = current.next_node
        return current
```
Go back, study and practice the code as many times as you can so as to enable you get a good grasp of Linked List and its common operations.

Congratulations for adding the knowledge of Linked List to your skillset.

Happy coding...