Linked list can be considered as list of nodes ,where each node consist of data to be stored as well as the address of the next node.
Example :
consider we have a linked-list as [data | addr_of_nxt_node] -> [data | addr_of_nxt_node] -> [data | addr_of_nxt_node] -> [data | NULL]
Last element of the linked list will always hold the addr of next node as NULL ,which will be the indication while traversing the list that linkedlist ends here
Linked-List operations :
- Insert node at begining.
- Insert node at position.
- Delete node from linkedlist.
- Search node in linkedlist.
- Sort linkedlist.
Demonstration :
Let's start Implementing the linkedlist
First we need to define the struct of a node
As we can see we will define the struct with help of struct where data will be the addr where we will store the values to be stored and next will be used to store the addr of the next ndoe adjacent to current node.
Since we have defined the structure of the node ,now lets start implementing methods to perform operations on LinkedList
Note : In Linked List we generally have a pointer name as HEAD which will always store the location of the first node of linkedlist.
(i) Insert at begining :
lets create a node 'tmp_node' and allocate memory to that node using 'malloc' then we will add the data in the node with help of this pointer as 'tmp_node->data' and simillarly we will store the position of next node as the node stored by HEAD ,and then point HEAD back to newly created Node 'tmp_node'. you will think what is there is no node in the linked list then ,still the code remain same because we initialize the HEAD with the NULL ,so automatically when we will store the addr of HEAD in the 'tmp_node' our new node will be pointing to NULL.
(ii) Insert at node at last :
Now lets understand how we can add the node at last position
so for this we will start traversing through the linkedlist until we dont encounter a node that holds the next as NULL ,which means that will be the last node .As you can see in the code this can be easily achieved with help of while loop and now we can move from one node to other with this line 'last_node = last_node->next'. means we are defining that the last_node is now pointing at the next adjacent node of current node .
Example :
Consider we have a LinkedList as LAST_NODE >> [1 | addr_of_nxt_node] -> [2 | addr_of_nxt_node] -> [3 | addr_of_nxt_node] -> [4 | NULL]
now as we can see we have a pointer pointing at node containing 1 as data ,so if we execute 'last_node = last_node->next' ,then as a result LAST_NODE will start pointing to node containing 2 as data.
SO once we reach at the last node then we will change the node's addr_of_nxt_node from NULL to the newly created node 'tmp_node'
(iii) delete node at n position :
Now lets understand how we can delete the node
First check if the HEAD is NULL which means no node in linkedlist ,then simply return since we dont have anything to delete.
now if linkedlist is not empty then we will check find node which needs to be removed ,we will check which node to be removed by comparing the data to be removed with the data stored in node, so if node contains the data which needs to be removed we will remove that node.
so if it is the let's say we find that node .by iterating over the linkedlist ,now you must be wondering why we have extra line as 'tmp_prev_node = tmp_head_node;' ,now the reason is simple let's undertand with example
[1 | addr_of_nxt_node] -> [2 | addr_of_nxt_node] -> [3 | addr_of_nxt_node] -> [4 | NULL]
if the node needs to be removed is node containing value '2' ,now we can not simply remove it becuase if we do so ,then hte node containg 1 will point to NULL and the nodes after 2 which are 3 and 4 will become unreachable .as follows:
[1 | NULL] [3 | addr_of_nxt_node] -> [4 | NULL]
now as you can see we dont have addr_of_nxt_node in the 1 ,so we can not move to the 3 and 4 .due to this we will keep on storing the address of node previous to current node ,
now let's tale same example , we want to remve the node 2, so we will iterate over the while loop ,once we find reach the node 2 then the
'tmp_prev_node' will be pointing to node containing value 1 ,which is previous to the node to be removed and 'tmp_head_node' will be pointing to the node containing value 2,which needs to be removed ,so before freeing the memory from the hold by tmp_head_node ,we will change the address of pervious node which is 1 ,to the addr_of_nxt_node which node 2 holds ,and then we will free the address.
now after removing the linkedlist will become.
[1 | addr_of_nxt_node]->[3 | addr_of_nxt_node] -> [4 | NULL]
Now as you can see all still all the nodes in linkedlist is reachable.
(iv) Search operation :
This search operation is as same as the way we find the node in the deletion operation ,we will iterate over the nodes and compare the value of to be find with the node's value. once found we can return 0 ,but if not found we can return some other value like -1 that data is not in linkedlist
(v) sort operation :
This is not diff from the sorting we normally do
we will iterate over the nodes one by one and then compare it with rest of the nodes in the 2nd while loop if we encounter the value less then the current node we will swap ,now it depends on the type of implementation whether we want to swap the complete nodes or we just want to swap the node's value. In below demonstration we are swapping the data rather then whole node ,becuase swapping complete node can be costly as compared to the swapping data which is easy.
Printing linkedlist is simple we as what we were doing till now in above operations ,we will iterate over each node one by one ,and will add the print statement in the while loop itself.
Since we are done with the defining/declaring methods we will implement a main method and perform these operations one by one
Note:
Linked are not restricted to this only ,we have other types of linkedlist as well like:
- doubly linkedlist : here we will have structure of node as [addr_of_prev_node | data | addr_of_nxt_node] ,node will hold the addr of previous adjacent node as well as next adjacent node.
- circular linkedlist : Here last node of the list will not hold nxt_addr_of_node as NULL ,rather it will point to the HEAD.
you can find the code of all types of linkedlist and its application in c and python in this repo : Linked List