Introduction to Linked Lists

What are Linked Lists?

A Linked List is can be considered as a linear store of data but may not be in contiguous memory location, ie, or at random memory locations. Linked Lists enables dynamic storage of values. You can image in a Linked List to be a series of nodes that contains a value called data and a pointer next that can be considered as a linker to the next node.

For each linked list, two nodes are taken as reference points:
-head: Which is used to reference the first node of the Linked List.
-Tail: Which is used to reference the last node of the Linked List.

There are two types of Linked Lists:
-Singly Linked List
-Doubly Linked List

Singly Linked List

In this type of list, for each node in the list, there are two values that are stored: data which is the value to be stored and next a pointer that points to the next node. In this type, the next of the tail node will be None or Null as it will not point to any location as it's the last node in the list. To create a node, we create a class node that can be used to create an object that contains the data and next as shown below:

class node:
    def __init__(self, data):
        self.data = data
        self.next = None

We now create a LinkedList class in which the nodes are stored. When we create an object of the class, we want the head and tail nodes to be automatically created we modify the __init__() to be as follows:

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

The Operations that can be performed are: Insert from front, Insert from rear, Delete, Display.
-insert_from_front: In this function, we read the value to be stored, then we create a node object and pass the values as a parameter to the constructor of the node class. We then point this new_node to the next of the head and then make the next of the head to point to the new_node. The function to demonstrate this is shown below

    def insert_from_front(self):
        data = int(input("\nEnter Value to be inserted"))
        new_node = Node(data)
        new_node.next = self.head.next
        self.head.next = new_node

-insert_from_rear: In this function, we read the value to be stored, then we create a node object and pass the values as a parameter to the constructor of the node class. We then iterate through the List from the head till we reach a ndoe that points to the tail node and then we make the current_node to point to the new_node and finally we make the new_node to point to the tail. The function to demonstrate this is shown below

    def insert_from_rear(self):
        data = int(input("\nEnter Value to be inserted"))
        new_node = Node(data)
        current_node = self.head
        while current_node.next != self.tail:
            current_node = current_node.next
        current_node.next = new_node
        new_node.next = self.tail

-delete: In this function, we iterate through the list till the node whose next points to a node that contains the value to be deleted is found. Next, we make the next of the current node point to the next of the node it's pointing to. The function that demonstrates this function is shown below:

    def delete(self):
        data = int(input("\nEnter value to be deleted"))
        current_node = self.head
        while current_node.next != self.tail:
            if current_node.next.data == data:
                current_node.next = current_node.next.next
                print("\nNode deleted")
                break
            current_node = current_node.next
        print("\nNo such value found")

-display: In this function, we iterate through the list till the we come across the tail node. The function is given below:

    def display(self):
        current_node = self.head.next  
        while current_node != self.tail:
            print(f"Value at current node: {current_node.data}")
            current_node = current_node.next

The complete code to demonstrate the functioning of the Singly Linked List is given below:

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

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

    def display(self):
        current_node = self.head.next  
        while current_node != self.tail:
            print(f"Value at current node: {current_node.data}")
            current_node = current_node.next

    def insert_from_front(self):
        data = int(input("\nEnter Value to be inserted"))
        new_node = Node(data)
        new_node.next = self.head.next
        self.head.next = new_node

    def insert_from_rear(self):
        data = int(input("\nEnter Value to be inserted"))
        new_node = Node(data)
        current_node = self.head
        while current_node.next != self.tail:
            current_node = current_node.next
        current_node.next = new_node
        new_node.next = self.tail

    def delete(self):
        data = int(input("\nEnter value to be deleted"))
        current_node = self.head
        while current_node.next != self.tail:
            if current_node.next.data == data:
                current_node.next = current_node.next.next
                print("\nNode deleted")
                break
            current_node = current_node.next
        print("\nNo such value found")


choice = 0
linked_list = LinkedList()
while choice != 5:
    print("\n************LINKED LIST************")
    print("\n1. Insert from Front\n2. Insert from Rear\n3. Delete\n4. Display\n5. Exit\nEnter choice:")
    choice = int(input())
    if choice == 1:
        linked_list.insert_from_front()
    elif choice == 2:
        linked_list.insert_from_rear()
    elif choice == 3:
        linked_list.delete()
    elif choice == 4:
        linked_list.display()
    elif choice == 5:
        break
    else:
        print("\nInvalid choice")

Doubly Linked List

In this type of list, for each node in the list, there are three values that are stored: data which is the value to be stored, next which is a pointer to the next node of the Linked List and a prev which is a pointer to the previous node of the list. In this type, the prev of the head will be None or Null as it's the first node in the list and there's no node before it. Similarly the next of the tail node will be Null or None as it's the last node in the list.

To create a node, we create a class node that can be used to create an object that contains the data, next, and prev as shown below:

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

We now create a LinkedList class in which the nodes are stored. When we create an object of the class, we want the head and tail nodes to be automatically created we modify the __init__() to be as follows:

class LinkedList:
    def __init__(self):
        self.head = Node(None)
        self.tail = Node(None)
        self.head.next = self.tail
        self.tail.prev = self.head

The Operations that can be performed are: Insert from front, Insert from rear, Delete, Display from Front, Display from Rear.

-insert_from_front: In this function, we create a node for the value to be inserted. We make the next of the new_node point to the next of the head and the prev of the new_node point to the head and finally we make the prev of the node after the head point to the new_node and we make the next of the head point to the new_node. The function is given below:

    def insert_from_front(self):
        data = int(input("\nEnter Value to be inserted"))
        new_node = Node(data)
        new_node.next = self.head.next
        new_node.prev = self.head
        self.head.next.prev = new_node
        self.head.next = new_node

-insert_from_rear: In this function, we create a node for the value to be inserted. We make the next of the new_node point to the tail, and the prev of the new_node point to the prev of the tail and finally we make the next of the node previous to the tail to point to the new_node and we then make the prev of the tail point to the new_node. The function is given below:

    def insert_from_rear(self):
        data = int(input("\nEnter Value to be inserted"))
        new_node = Node(data)
        new_node.next = self.tail
        new_node.prev = self.tail.prev
        self.tail.prev.next = new_node
        self.tail.prev = new_node

-delete: In this function, we iterate through the list from the node after the head. If the data is found in a node, the next of the node previous to the node to be deleted, will be pointed to the next of the current_node and the prev of the node of the next of the current_node will point to the prev of the current_node. The function is given below:

    def delete(self):
        data = int(input("\nEnter value to be deleted"))
        current_node = self.head.next
        while current_node != self.tail:
            if current_node.data == data:
                current_node.prev.next = current_node.next
                current_node.next.prev = current_node.prev
                print("\nNode deleted")
                break
            current_node = current_node.next
        else:
            print("\nNo such value found")

-display_from_rear: In this, we iterate from the penultimate node till the head, using the prev of each node. The function is given below:

    def display_from_rear(self):
        current_node = self.tail.prev
        while current_node != self.head:
            print(f"Value at current node: {current_node.data}")
            current_node = current_node.prev

-display_from_front: In this, we iterate from the node in-front of the head till the the tail node, using the next of each node. The function is given below:

    def display_from_front(self):
        current_node = self.head.next  
        while current_node != self.tail:
            print(f"Value at current node: {current_node.data}")
            current_node = current_node.next

The complete code to demonstrate the functioning of the Doubly Linked List is given below:

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

class LinkedList:
    def __init__(self):
        self.head = Node(None)
        self.tail = Node(None)
        self.head.next = self.tail
        self.tail.prev = self.head

    def display_from_front(self):
        current_node = self.head.next  
        while current_node != self.tail:
            print(f"Value at current node: {current_node.data}")
            current_node = current_node.next


    def display_from_rear(self):
        current_node = self.tail.prev
        while current_node != self.head:
            print(f"Value at current node: {current_node.data}")
            current_node = current_node.prev

    def insert_from_front(self):
        data = int(input("\nEnter Value to be inserted"))
        new_node = Node(data)
        new_node.next = self.head.next
        new_node.prev = self.head
        self.head.next.prev = new_node
        self.head.next = new_node

    def insert_from_rear(self):
        data = int(input("\nEnter Value to be inserted"))
        new_node = Node(data)
        new_node.next = self.tail
        new_node.prev = self.tail.prev
        self.tail.prev.next = new_node
        self.tail.prev = new_node

    def delete(self):
        data = int(input("\nEnter value to be deleted"))
        current_node = self.head.next
        while current_node != self.tail:
            if current_node.data == data:
                current_node.prev.next = current_node.next
                current_node.next.prev = current_node.prev
                print("\nNode deleted")
                break
            current_node = current_node.next
        else:
            print("\nInvalid Value")


choice = 0
linked_list = LinkedList()
while choice != 6:
    print("\n************LINKED LIST************")
    print("\n1. Insert from Front\n2. Insert from Rear\n3. Delete\n4. Display from Front\n5. Display from Rear\n6. Exit\nEnter choice:")
    choice = int(input())
    if choice == 1:
        linked_list.insert_from_front()
    elif choice == 2:
        linked_list.insert_from_rear()
    elif choice == 3:
        linked_list.delete()
    elif choice == 4:
        linked_list.display_from_front()
    elif choice == 5:
        linked_list.display_from_rear()
    elif choice == 6:
        break
    else:
        print("\nInvalid choice")