Linked List is a linear and dynamic data structure that consists of series of nodes connected to each other.

The elements are not stored contiguously, but linked with pointers .

In linked list each node stores the data and the address of the next node. The head is the pointer that stores the address of the first node.

There are three types of linked list

• Singly Linked List

• Doubly Linked List

• Circular Linked List

The most common type of linked list is Singly Linked List. In this post we will cover all about Singly Linked List.

What is a Singly Linked List?

In Singly Linked List, each node has data and a next field that contains the address to the next node. The head is the pointer that stores the address of the first node. In singly linked list, we can traverse the linked list in only one direction. The next pointer of the last node in singly linked list, points to NULL.

Creating a Linked List

Each node in a linked list consists of two parts: 

• Data Item

• Pointer to next node

The first step before implementing a linked list is to create node since linked list is nothing but a series of nodes connected to each other.

In python we construct a node using Class. A class acts as a blueprint for creating a new objects. Objects are anything you want to manipulate or change while coding. We use __init__ method to declare the class and let the class initialize the object’s attributes. The self is the default argument that allows us to access variables, attributes, and methods of a defined class in Python.

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

# creating a node
f_node = node(3)
print(f_node.data,f_node.next)

Now that we have outline for creating nodes, we will now create our Linked List Class in which we will join multiple single nodes. We will also have a single head pointer pointing to a complete instance of a Linked List. Using the head pointer, we will be able to traverse the whole list, and even perform all kinds of list manipulations.

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

class linkedlist:
    def __init__(self):
        self.head = None

# creating node and making our head the first node
l_list = linkedlist()
l_list.head = node(5)
print(l_list.head.data,l_list.head.next)

Inserting elements in Linked List

To insert elements in our Linked List, we will first define a function called insert(self, data). We will also declare a variable new_node that will call the node class and hold our data input.

First, we will check if our list is empty i.e. if the head is None. If it is None, then this is our first node.

If the head is not None, it means we have nodes in the our linked list. So, the new node should be added at the end. To add our new node at the end, we will traverse the linked list till new_pointer.next points to None. After reaching our last node, we will come out if the loop and make the new_pointer.next point to the data input.

    def insert(self,data):
        new_node = node(data)
        if self.head == None:
            self.head = new_node
            return
        new_pointer = self.head
        while(new_pointer.next is not None):
            new_pointer = new_pointer.next
        new_pointer.next = new_node

The whole code for inserting the elements

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

class linkedlist:
    def __init__(self):
        self.head = None
    
    def insert(self,data):
        new_node = node(data)
        if self.head == None:
            self.head = new_node
            return
        new_pointer = self.head
        while(new_pointer.next):
            new_pointer = new_pointer.next
        new_pointer.next = new_node
        
new = linkedlist()
new.insert(3)
new.insert(5)
new.insert(7)

Time complexity: O(N)

Space Complexity: O(1)

Traversing a Linked List

We will first start from head , and keep traversing or printing the data till the we find the last node.

    def print_ll(self):
        print_pointer = self.head
        while(print_pointer is not None):
            print(print_pointer.data)
            print_pointer = print_pointer.next

The whole code for inserting and printing the elements.

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

class linkedlist:
    def __init__(self):
        self.head = None
    
    def insert(self,data):
        new_node = node(data)
        if self.head == None:
            self.head = new_node
            return
        new_pointer = self.head
        while(new_pointer.next is not None):
            new_pointer = new_pointer.next
        new_pointer.next = new_node
        
    def print_ll(self):
        print_pointer = self.head
        while(print_pointer is not None):
            print(print_pointer.data)
            print_pointer = print_pointer.next
        
new = linkedlist()
new.insert(3)
new.insert(5)
new.insert(7)
new.print_ll()

Time complexity: O(N)

Space Complexity: O(1)

Now that we know how to create a linked list, let’s know more about operations we can perform on our linked list.

Operations on Linked List

Get Length of the Linked List

To get the length of the linked list, we will have a count variable that we will increment as we traverse the linked list.

    def length(self):
        count = 0
        count_pointer = self.head
        while(count_pointer is not None):
            count += 1
            count_pointer = count_pointer.next
        print(count)

Sum of linked list nodes

To get the sum, we will have sum variable to which we will add the data of nodes while traversing the linked list.

    def sum(self):
        sum = 0
        sum_pointer = self.head
        while(sum_pointer is not None):
            sum = sum + sum_pointer.data
            sum_pointer = sum_pointer.next
        print(sum)

Find Maximum element of Linked List

To get the maximum element of linked list, we will have maxx variable equated to '-inf'. As we are traversing through the linked list we will compare the data of given node and maxx value to get the maximum.

    def max_val(self):
        maxx = float('-inf')
        maxx_pointer = self.head
        while(maxx_pointer is not None):
            maxx = max(maxx,maxx_pointer.data)
            maxx_pointer = maxx_pointer.next
        print(maxx)

Search an element in Linked list

To know if the element exists in the linked list, we will have a flag variable set to False. While traversing, if the node data is equal to the value we need to search, we will set the flag True and print the flag value.

    def search(self,value):
        s_pointer = self.head
        flag = False
        while(s_pointer is not None):
            if (s_pointer.data == value):
                flag = True
            s_pointer = s_pointer.next
        print(flag)

Delete a Node in a Linked list

We will first create a pointer del_pointer and equate it to head. Then we will check if the head = value that needs to be deleted. If it is, then we will equate the head to the next node. If the head!= value ,we will traverse till we find the value to be deleted. While traversing we will have a prev pointer that will store the previous node and the del_pointer that we store the current node. If del_pointer.data = value that needs to be deleted, we will come out of the loop and make the next of previous node to the node that comes after the the deleted value.

    def delete(self,value):
        del_pointer = self.head
        if del_pointer is not None and del_pointer.data == value:
            self.head = del_pointer.next
        else:
            while(del_pointer is not None and (del_pointer.data != value)):
                prev = del_pointer
                del_pointer = del_pointer.next
            
            if del_pointer is not None:
                prev.next = del_pointer.next