Linked List is a linear data structure which consists of group of nodes in a sequence where each node holds its own data and the address of the next node thus forming a chain like structure. They can be used to construct trees, stacks or graphs.

Linked lists may be preferred over normal lists because:

• They allow Stacks and queues to be easily implemented executed
• They are a dynamic in nature thus only allocating memory when required
• They reduces the access time

However, they also require extra memory to store pointers, are difficult to traverse in reverse and it is not possible to access any element randomly thus for simple data it makes more sense to use simple lists.

There are three types of linked lists:

• Singly Linked List
• Doubly Linked List
• Circular Linked List

1. Singly Linked

Are the easiest kind of linked list to implement. A node only requires to have its data and the address of the next node

2. Doubly Linked

Each node here has its data and two addresses. One address points to the next node in the link while one address points to the previous node.

3. Circular Linked

Are similar to singly linked lists where each node holds its own data and the address of the next node except the last node that holds the address to the first node in the link thus forming a complete loop.

Linked list operations

Insert

Data can be inserted at the beginning of a linked list, after a node or at the end of the list.

• At the beginning

It is simple and only requires you to create a new node with the data you want to insert . The next variable of the new node is then pointed to the current head of the list. The head of the list is then changed to point to the newly created node.

def insert_at_beginning(self, new_data):
    #create new node
    new_node = Node(new_data)
    #point next of the new node to current head
    new_node.next = self.head
    #point head to the new_node
    self.head=new_node

• After a node

Requires two inputs: the previous node and the new data. First we check if the previous node exists and raise an exception if it doesn't exist. Then we create a new node with the new data and point its next to the next of the previous node. Last we point the next of the previous node to the new data

def insert_after(self,prev_node, new_data):
    #check if node exists
    if prev_node is Node:
        raise Exception('Previous node does not exist')
    #create new node
    new_node = Node(new_data)
    #point next of the new node to prev_node next
    new_node.next = prev_node.next
    #point next of prev_node to the new_node
    prev_node.next=new_node

• Insert at the end

This operation takes more steps than the previous two. This is because you have to traverse the entire list till you find a node that has no pointer to the next node (i.e last node in the list), then insert your new node there. First you create a new node then check if the list is empty. If it is empty make the new node the head node of the list. Otherwise traverse the list till you find the last node then point the next of the last node to the new node.

 # insert at the end of the list
    def insert_at_end(self, new_data):
        # create new node
        new_node = Node(new_data)
        # check if list is empty
        if self.head is None:
            self.head = new_node
            return
        # traverse list and add to last item on list
        last = self.head
        while last.next:
            last = last.next
        # append to end of list
        last.next = new_node

In the next article we look at the delete and delete method and how to print the entire list. The full code for this article can be found here