Singly Linked List: Introduction and Operations

This is part 2 of the Linked List series. If you haven’t checked out the part 1, then follow this link here. In this post we will see what is a singly Linked List, what is the cost of insertion and deletion in it and its advantage over an array. So without further ado, let’s start!

In Singly Linked Lists, each node is connected to the next node using a single link or pointer. The node class will then be –

Insertion

There are 3 different places where we can insert a node in a linked list. They are –

• At Head
• At Tail
• After some node x

Head

We can insert a new node at the head of the Linked List in 2 steps given below.

Step 1: Initialize the new node with the desired value. Then link this node to the current Head.

Step 2: Now mark this new node as the new Head.

Tail

Steps are quite similar to the first case.

Step 1: Initialize the New node. Then link the Tail node to this new node.

Step 2: Now simply mark this New node as the current Tail.

After some given node

So the steps for inserting a node after some given node prev will be a combination of the first two cases of insertion at head and at tail, as here we have both prev as well as next nodes.

Step 1: Initialize the new node with value 5.

Step 2: Link this new node ‘5’ to the next node ‘2’.

Step 3: Link the prev node ’15’ to the new node ‘5’.

Now let’s calculate the time and space complexity for this general scenario.

Time Complexity: As we are already given the reference to prev node, we just need constant time O(1) to change the links and hence insert the new node.

This is a huge improvement over an array, wherein we require O(N) time to insert an element because we need to shift all the elements past the inserted element.

Space Complexity: As we are just changing the links between the nodes, we don’t require any additional space, which translates to a constant space complexity of O(1).

Deletion

Similar to insertion, we can delete three different types of node in linked list based on their locations:

• Head
• Tail
• Some given node cur

Head

Let’s say we have a Head Node ‘5’ for the given Linked List.

To delete this node, we can just mark the next node ’10’ as our Head Node. Easy right?

Tail

We cannot directly delete the Tail node as we require the prev node before tail node and set this as our new tail node. So it will take us 2 steps for the deletion.

Step 1: Traverse the Linked List and store the node just before the Tail node as prev node with value 2.

Step 2: Mark the next pointer of prev as Null. Mark prev as our new Tail node

Some given node

Let’s try to delete a cur node 10 from the given singly linked list.

Step 1: First traverse the linked list to find the prev node 5 just before node 10.

Step 2: Link prev node 5 to the next node 2.

Now let’s calculate the time and space complexity for this general scenario like we did for insertion.

Time complexity: As we are traversing the linked list once to find the prev node before the cur node that is to be deleted, it costs us O(n) time to do so.

Space Complexity: As we don’t require any additional space other than a reference to prev node, the space complexity comes out to be O(1).

Summary

Singly linked, thus, is just a linked list with a single pointer between any two nodes.

Insertion: Both the time and space complexities of insertion in singly linked list is O(1).

Deletion: The time complexity of deleting a node in the singly linked list is O(N) as we need to traverse the list once to find the prev node just before the node to be deleted. The space complexity is still O(1).

We gain an advantage over arrays, because we require just O(1) time for inserting a node in the Singly Linked List.

Do let me know in the comments below what you liked or didn’t like in this post. Till next time, Happy coding!