Linked List Operations
The basic operations that we can do in the lists are:
Let's discuss each operation in detail.
Inserting a new node in the list is a big task. As we learned, the lists are sequential and each node contains the address to the next node, now to insert a new node in the list, the addresses of the nodes to its immediate left and right need to change as well.
Example: Let us assume that we need to add the node “B” in between the node A and C.
Now Before adding B the node of A holds the address to C. When we insert B, the address node of A should now point to B and the address node of B should take us to C.
Step1: Create a new node which is to be inserted and determine the place where it needs to be inserted. Refer to the diagram.
In this diagram, "New NODE" is to be inserted in the above-linked list.
Step2: To insert the "New NODE" we will point the "Next" of the new node towards the data item of the node ahead of it. Refer to the diagram:
Step3: In the final step, we will point the next of the node preceding the "New NODE" to the data item of the new node. It will look like this:
Step4: The node will be successfully inserted and will become part of the linked list.
Deleting an element from the list also will be done in more than one step. Take the similar example, Now suppose the three elements A, B, and C are linked together and we want to remove B. On removing B, the link between the element A and C has to be formed directly.
Step1: To delete the node from the linked list, we need to first determine our target node.
Step2: After we know our target node, we need to make sure the next of the previous node points towards the data item of the node ahead of the target node.
Step3: We will now remove the link of the target node that was pointing towards the next node.
Step4: The node is deleted from the list.
In this operation, first we traverse through the entire list till we find the null element, Now the address node of this element is reversed to the previous one and the list is reversed in a similar manner till we reach the first element.
Step1: Reversing is a thorough process. We need to reverse the linked list in such a way that the last node is pointed by the head and the first node then becomes the last node.
Step2: We will now reverse the end of the last node. The next here should not be pointing to null. We will make the next of the previous node point towards null.
Step3: Now as we will break the link of the first node that points towards the last node, we need to make sure the last node doesn't appear to be lost. So we will create a temporary node that will point towards the last node.
Step4: reverse all the links, make sure all the successors are now pointing towards their predecessors.
Step5: The reversed node will look like: