0

Basic operations on Singly Linked List

We will discuss basic operations on singly linked list. Operations like insert,delete and print.

1. Insert:

In singly linked list, last node stores next address value as null. So while inserting new node , linked list is traversed from start to end.

New node will be inserted at the end so last node’s next address will be pointed to new node.

As all nodes are visited while inserting new value, time complexity for this operation is O(n).

2. Insert at specific position:

Given a value and position where you want to insert. First traverse through linked list until we get node previous to desired position and then insert node at that position. In this problem we also need to check if given position is out of range of given linked list. For example, currently linked list contains only 4 nodes and for new value position is given as 10, which is incorrect.

In this case best case is insert value at start, for this time complexity will be O(1) and worst case is insert at last position or position is out of range, in this scenario all nodes of linked list will be traversed so time complexity will be O(n).

3. Delete node from at specific position:

Given position at which you want to delete a node . First traverse through linked list until we get node previous to desired position and then delete node at that position. In this problem we also need to check if given position is out of range of given linked list. For example, currently linked list contains only 4 nodes and position is given as 10, which is incorrect.

In this case best case is delete node at position 0 which is head of linked list , for this time complexity will be O(1) and worst case is delete  last node or position is out of range, in this scenario all nodes of linked list will be traversed so time complexity will be O(n).

4. Print all linked list values:

This is a simple operation on a linked list.

As all nodes are visited to print values, time complexity of this operation is O(n).

You can find solution to more problem on linked list here.