Linked List Operations

Linked lists are fundamental data structures that support a range of operations for managing collections of data. The basic operations of linked list are including:

• Insertion
• Deletion
• Traverse
• Searching

Insertion

This operation is performed to add an element to the list. There are various types of insertion on the basis of the position where the new node is going to be inserted:

• Add a node at the beginning of the linked list
• Add a node after a given node of the linked list
• Add a node at the end of the linked list

Insert a Node at the Front/Beginning of the Linked List

For inserting a new node at the beginning, we make a new node and its next pointer points to the current head of the linked list. After that, we update the head pointer to point to this new node. Insertion in the beginning is very efficient as it only requires the adjustment of a few pointers.

Output:

Before insertion, the linked list is: 
12 -> 13 -> 14 -> 15
After insertion, the updated linked list is: 
11 -> 12 -> 13 -> 14 -> 15

Insert a Node After a Given Node of the Linked List

For inserting a new node at the beginning, we make a new node and its next pointer points to the current head of the linked list. After that, we update the head pointer to point to this new node. Insertion in the beginning is very efficient as it only requires the adjustment of a few pointers.

Output:

Before insertion, the linked list is: 
12 -> 13 -> 15 -> 16

After insertion, the updated linked list is: 
12 -> 13 -> 14 -> 15 -> 16

Insert Node at the End of the Linked List

In order to insert a new node at the beginning, we first make a new node and its next pointer points to NULL. After that, we update the next pointer of the last node of the linked list to point to the new node. Insertion at the end is also very efficient, as it only requires the adjustment of the next pointer of the last node.

Output:

Before insertion, the linked list is: 
12 -> 13 -> 14 -> 15
After insertion, the updated linked list is: 
12 -> 13 -> 14 -> 15 -> 16

Deletion

This operation is performed to remove a node from the linked list. There are various types of insertion on the basis of the position where the new node is going to be inserted:

• Deleting the first node of the linked list
• Deleting a node at a specific position in the linked list
• Deleting the last node of the linked list

Deleting the First Node of the Linked List

For deleting the first node of the linked list, we put the head node in a temporary variable. After that, we shift the head node to point to the second node of the linked list. After that, we delete the node stored in the temporary variable and then return the head pointer.

Output:

Before deletion, the linked list is: 
12 -> 13 -> 14 -> 15 -> 16

After deletion, the updated linked list is: 
13 -> 14 -> 15 -> 16

Deleting a Node at a Specific Position in the Linked List

For deleting the node at a specific position in the linked list, we do the traversal of the linked list to reach the node, which is just before the given position. After that, we do the adjustment of the next of the previous node to point to the next node of the next nodes.

Output:

Before deletion, the linked list is: 
12 -> 13 -> 14 -> 15 -> 16

After deletion, the updated linked list is: 
12 -> 13 -> 15 -> 16

Deleting The Last Node of the Linked List

For deleting the last node of the linked list, we do the traversal of the linked list to reach the penultimate node, which is just before the last node. After that, we set the NULL value to the next pointer of the penultimate node.

Output:

Before deletion, the linked list is: 
12 -> 13 -> 14 -> 15 -> 16

After deletion, the updated linked list is: 
12 -> 13 -> 14 -> 15

Traversal of Linked List

This operation is performed to traverse the elements of the list.

Output:

The elements of the linked list are: 
12 -> 13 -> 14 -> 15 -> 16

Search in a Linked List

This operation is performed to search for an element in the list using the given key.

Key = 13 (element to be searched)

Output: The key 13 is found.

Output:

The elements of the linked list are: 
12 -> 13 -> 14 -> 15 -> 16
The key 13 is found. 

Complexity of Linked List

Now, let's see the time and space complexity of the linked list.

Linked List Operations MCQs

1. How many pointers are affected when we insert a node in the middle of the singly linked list?

1. 1
2. 2
3. 3
4. 4

2. What is the time complexity of deleting the last node of the linked list?

1. O(n)
2. O(n²)
3. O(n³)
4. O(1)

3. What is the time complexity of deleting the first node of the linked list?

1. O(n)
2. O(n²)
3. O(n³)
4. O(1)

4. How many pointers are affected when we delete a node in the middle of the singly linked list?

1. 4
2. 3
3. 2
4. 1

5. Which one of the following has O(n) time complexity?

1. Inserting a node at the middle of linked list
2. Deleting the node at the middle of linked list
3. Inserting a node at the end of the linked list
4. All of these