Blog

A singly linked list is one of the data structures in computer science. It serves as a building block for more complex structures such as stacks, queues, and graphs. In this post, we will explore the basics of a singly linked list, how it works, its operations, pro’s, con’s, and some use cases.

Basic concept of singly linked list

A singly linked list is a group of nodes where each node holds two fields:

The two fields are:

1. Data: The value or information contained in the node.
2. Next: A pointer (or reference) to the next node in the sequence.

In case of array , elements are stored in contiguous memory locations. Whereas in singly linked list elements are scattered in memory locations

How to create singly linked list in python?

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

In above code, class Node is created and constructor with default attributes as value and nextnode. The value represents data which we will be storing in Node whereas nextnode will be attribute which connects the next node to the Node. We can create n number of code and link them together.

#defining the Nodes 
one = Node(1)
two = Node(2)
three = Node(3)

here 3 nodes are created as example where one Node has data of value 1 and two will have data value as 2 and so on. We can link this 3 nodes using below code.

one.nextnode = two
two.nextnode = three

Now using nextnode attribute Node “one” is connected to Node “two ” and “Three” is connected “two”.

This is basic example of singly list nodes if we execute code we get the connection.

print(one.value)
print(one.nextnode.value)
print(two.nextnode.value)

The result will be printed as below

print(one.value)
print(one.nextnode.value)
print(two.nextnode.value)

Big O analysis

Operations	Linked List
Accessing elements	O(n)
Remove/Insert from start	O(1)
Remove / insert from end	O(n)
Remove/Insert from Middle	O(n)

Pro’s and Con’s

Pro’s of linked list	Con’s linked list
It has dynamic size , that means new node can be added dynamically as they do not have fix sizes.	We need to traverse the whole list if we need to delete or modify any elements from middle to end. if we need to delete it we need traverse from start to K.
We can insert and delete the nodes at the beginning or middle of the list with efficiency as no element shifting is required.	Extra memory is required since it stores head and link both for every element
If the number of elements in linked list is not predictable it can simply shrink or grow in size as required on the go.	If we want to perform operations like searching linear time O(n) is required to traverse the list and get the element we searching for.

Conclusion:

Singly linked list is used in scenarios where dynamic memory allocation is needed and performs well for insertion and deletion operations. However, its linear time complexity for access and search operations can be a drawback in some cases.