Linked List and Why do we need them?

The linked list is one of the computer science and software data structures. The idea is that we can have a group of related data in one place similar to Arrays. But what is the difference between an array and a linked list? Why do we need two similar data structures?

Array

Arrays have two important characteristics:

• All members have the same data types (like an array of integers)
• The size of the array is fixed and pre-determined.

The above features are very useful and make the array data structure efficient. However, they also bring some limitations:

• When we are dealing with a group of data that are either not primitive (such as objects) or do not have the same type (like integers and strings)
• The size limitation demands that we know beforehand the size of our data, which is often unrealistic.

One might argue that the second limitation about array size is not true since we can always extend it. This is correct, but extending an array creates a new problem: run-time performance.

The reason is, when you extend an array, your system needs to allocate an entirely new array and copy all the array data to the new one. For example, let’s say our array size is three:

[1,2,3]

Now let’s say we want to add a new number (100). Here, OS creates a new empty array with the size of four: 

[‘’, ‘’, ‘’, ‘’]

And then copies all the previous numbers alongside the new number to it:

[1,2,3] → [1,2,3,100]

Linked List

To tackle the limitations of arrays, we can use a Linked List. A Linked List is a chained list of objects. Each member of a Linked List is an object with two properties:

• Value: The actual value
• Pointer: The address of the next list member in memory

Note: The Value in a Linked List can be anything. For simplicity, we assume it is an integer in this writing. 

Note: We only consider Single Linked List in this writing. There is another type name Double Linked List in which there is another pointer also to the previous list member. 

The point about Linked List members is that, unlike an array, they are not consecutively saved in the memory. Rather each member can be anywhere in the memory. The Pointer helps us to find the next member for each member. Now the question is: how can we know where is the first member?

To answer this challenge, Linked List has two extra pointers:

• Head: The address of the first list member
• Tail: The address of the last member

Why do we need the Tail? Because when we want to append a new member to the end of the Linked List, If we don’t have the Tail address, it would be inefficient [O(n)] to append a new member since each time we need to start from the Head. (remember there is no index for the direct access like an array).

Linked List Implementation in Python

To implement a Linked List in Python, the first step is to define a Node class. A node is a member in the linked list that have a value and a pointer to the next member.

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

After this, we define our Linked List class named SingleLinkedList. The class has four functions:

• __init__: Constructor method. It initiates the Head and Tail properties for the class.
• Print: prints the entire list.
• insert(value, location): insert a new value into the list at a certain location. Location is equivalent to an array index.
• delete(location): Remove a member on a certain location from the list.

The first step is to define the class and its initiation function. The Head and Tail values are set to None since the list is empty. We also write the print function. The idea for the print is that we start from the Head and print each value recursively until we reach the last element. The last element is the one with the next pointer None. 

class SingleLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
    
    
    def printList(self):
        node = self.head
        while node:
            print(node.value)
            node = node.next

To insert a node, we have three variants based on the location:

• Location 0: New node would be the new list Head.
• Location -1: New node would be the list Tail (end of list appending)
• Other Locations: Loop through the list until we reach the node with the Location. Then we change the node next pointer to the new node and set the new node next pointer to the location’s node next pointer.

def insert(self, value, location):
        node = Node(value)
        if not self.head:
            self.head = node
            self.tail = node
        elif location == 0:
            node.next = self.head
            self.head = node
        elif location == -1:
            #end of the linked list
            self.tail.next = node
            self.tail = node
        else:
            temp = self.head
            counter = 0
            while counter < location - 1:
                temp = temp.next
                counter += 1
            node.next = temp.next
            temp.next = node

Deleting a node is very similar to the insert. But we need to take care of one situation. When the Head and Tail are equal, means the list has only one member. If we delete that, the list becomes empty which means we need to set the Head and Tail to None. 

def delete(self, location):
        if not self.head:
            return False
        elif location == 0:
            if self.head == self.tail:
                self.head = None
                self.tail = None
            else:                
                self.head = self.head.next
        elif location == -1:
            if self.head == self.tail:
                self.head = None
                self.tail = None
            else:
                tempNode = self.head
                while tempNode:
                    if tempNode.next == self.tail:
                        break
                    tempNode = tempNode.next
                tempNode.next = None
                self.tail = tempNode
        else:
            tempNode = self.head
            counter = 0
            while counter < location - 1:                
                tempNode = tempNode.next
                counter += 1
            nextNode = tempNode.next
            tempNode.next = nextNode.next 

Better than Array?

Linked List does not have Array limitations in terms of size and members’ type restriction, however, it has a disadvantage compared to Array: Traversing time. In Array we can directly [O(1)]] access a member via the index. But in Link List, we need to traverse the list to reach a certain location that is linear [O(n)] complexity. Which one to use is very dependent on the problem you are dealing with. 

Here is the link to the entire code: https://github.com/Pooya-Oladazimi/Data-Structure-and-Algorithms/blob/master/Linked%20List/linked_list.ipynb

The End.