Linked List

• A Linked List is a collection of objects called nodes that are randomly stored in the memory.
• Each node contains two fields that hold a particular address where data is stored and the pointer which contains the address of the next node in the memory.

Singly-Linked List

• A Singly-linked list can be defined as the collection of an ordered set of elements.
• Nodes in the singly linked list consist of two parts such as the data part and link part.
• The data part of the node stores actual information that is to be represented by the node while the linked part of the node stores the address of its immediate successor.
• In a single linked list, the address of the first node is always stored in a reference node known as front. Sometimes it is also known as head
• Always the last node of the list contains a pointer to the null.
• In the Singly linked list data navigation happened in the forwarding direction only.
• Basic operations supported by a list are insertion, deletion, display, and search.
• Here we see Insertion and Deletion in detail.

Insertion Operation

The insertion into a singly linked list can be performed at different positions. Based on the position of the new node being inserted, the insertion is categorized into the following categories.

Insertion at the beginning -

It involves inserting an element at the front of the list. It needs to make the new node the head of the list.

• Step 1 - Create a newNode with given value.
• Step 2 - Check whether list is Empty (head == NULL)
• Step 3 - If it is Empty then, set newNode→next = NULL and head = newNode.
• Step 4 - If it is Not Empty then, set newNode→next = head and head = newNode.

Insertion at end of the list -

It involves insertion at the last of the linked list. The new node can be inserted as the only node in the list or it can be inserted as the last one. Different logics are implemented in each scenario.

• Step 1 - Create a newNode with a given value and newNode → next as NULL.
• Step 2 - Check whether list is Empty (head == NULL).
• Step 3 - If it is Empty then, set head = newNode.
• Step 4 - If it is Not Empty then, define a node pointer temp and initialize with head.
• Step 5 - Keep moving the temp to its next node until it reaches the last node in the list (until temp → next is equal to NULL).
• Step 6 - Set temp → next = newNode.

Insertion after the specified node -

It involves insertion after the specified node of the linked list. It needs to skip the desired number of nodes to reach the node after which the new node will be inserted.

• Step 1 - Create a newNode with the given value.
• Step 2 - Check whether list is Empty (head == NULL)
• Step 3 - If it is Empty then, set newNode → next = NULL and head = newNode.
• Step 4 - If it is Not Empty then, define a node pointer temp and initialize with head.
• Step 5 - Keep moving the temp to its next node until it reaches the node after which we want to insert the newNode (until temp1 → data is equal to location, here location is the node value after which we want to insert the newNode).
• Step 6 - Every time check whether temp is reached to the last node or not. If it is reached to the last node then display 'Given node is not found in the list!!! Insertion not possible!!!' and terminate the function. Otherwise, move the temp to the next node.
• Step 7 - Finally, Set 'newNode → next = temp → next' and 'temp → next = newNode'

Deletion Operation

The Deletion of a node from a singly linked list can be performed at different positions same as in insertion. Based on the position of the node being deleted, the operation is categorized into the following categories.

Deletion at the beginning -

It involves the deletion of a node from the beginning of the list. This is the simplest operation of all. It just needs a few adjustments in the node pointers.

• Step 1 - Check whether the list is Empty (head == NULL)
• Step 2 - If it is Empty then, display 'List is Empty!!! Deletion is not possible' and terminates the function.
• Step 3 - If it is Not Empty then, define a Node pointer 'temp' and initialize with head.
• Step 4 - Check whether the list is having only one node (temp → next == NULL)
• Step 5 - If it is TRUE then set head = NULL and delete temp (Setting Empty list conditions)
• Step 6 - If it is FALSE then set head = temp → next, and delete temp.

Deletion at the end of the list -

It involves deleting the last node of the list. The list can either be empty or full. A different logic is implemented for the different scenarios.

• Step 1 - Check whether list is Empty (head == NULL)
• Step 2 - If it is Empty then, display 'List is Empty!!! Deletion is not possible' and terminates the function.
• Step 3 - If it is Not Empty then, define two Node pointers 'temp1' and 'temp2', and initialize 'temp1' with head.
• Step 4 - Check whether the list has only one Node (temp1 → next == NULL)
• Step 5 - If it is TRUE. Then, set head = NULL and delete temp1. And terminate the function. (Setting Empty list condition)
• Step 6 - If it is FALSE. Then, set 'temp2 = temp1 ' and move temp1 to its next node. Repeat the same until it reaches the last node in the list. (until temp1 → next == NULL)
• Step 7 - Finally, Set temp2 → next = NULL and delete temp1.

Deletion after the specified node -

It involves deleting the node after the specified node in the list. It needs to skip the desired number of nodes to reach the node after which the node will be deleted. This requires traversing through the list.

• Step 1 - Check whether list is Empty (head == NULL)
• Step 2 - If it is Empty then, display 'List is Empty!!! Deletion is not possible' and terminates the function.
• Step 3 - If it is Not Empty then, define two Node pointers 'temp1' and 'temp2', and initialize 'temp1' with head.
• Step 4 - Keep moving the temp1 until it reaches the exact node to be deleted or to the last node. And every time set 'temp2 = temp1' before moving the 'temp1' to its next node.
• Step 5 - If it is reached to the last node then display 'Given node not found in the list! Deletion not possible!!!'. And terminate the function.
• Step 6 - If it is reached to the exact node which we want to delete, then check whether the list is having only one node or not
• Step 7 - If the list has only one node and that is the node to be deleted, then set head = NULL and delete temp1 (free(temp1)).
• Step 8 - If the list contains multiple nodes, then check whether temp1 is the first node in the list (temp1 == head).
• Step 9 - If temp1 is the first node then move the head to the next node (head = head → next) and delete temp1.
• Step 10 - If temp1 is not the first node then check whether it is the last node in the list (temp1 → next == NULL).
• Step 11 - If temp1 is last node then set temp2 → next = NULL and delete temp1 (free(temp1)).
• Step 12 - If temp1 is not first node and not last node then set temp2 → next = temp1 → next and delete temp1 (free(temp1)).