Simply Linked List

It is basically the list where elements contain the address or references of other nodes in the list. 

so in a linked list, the elements can be represented as nodes. these nodes have 2 parts that are values and pointer/(reference to the next node). so the values are assigned to the elements and then they store the the pointer that points towards the nest element in the list. pointer is basically the address of any element in the heap or stack. 

            let us consider a list containing 5 elements. list = {5,10,15,20,25} 

        so 5,10--,25 are the values in our list and [] would represent the pointer that would point toward the address of each element.

5,[] -> 10,[] -> 15,[] -> 20,[] -> 25,[] -> NULL

                 The last node would point towards the the NULL. the first node is called the head node. in singly linked list we can travel in forward direction only, not in backward direction. this is because we know the address of the next node. for example, if we are on the element-15 of our list. then we can only move forward as the current node only has the address of the next node that is 20, but it doesn't contain the address of previous node, which we came from. so the only direction we can go is forward.

                    For the search operation, we have to start from head node, so if want to find the element 20 in our list we have to check each and every element and start from the head node that is 5, we compare 5 to 20, now we move to the next node by the help of reference. now we compare 10 to 20 and move to next node.

 After 4 comparisons we found our element, so for n numbers of element in our list there would be n times comparisons so for the searching process the time complexity is O(n).        

For the insertion operation, if we want to insert any element in the starting of the list then simply it would require only one step of entering the value in the new node and passing the reference of the initial head node. in this case the time complexity is simply O(1). 

2,[] -> 5,[] -> 10,[] -> 15,[] -> 20,[] -> 25,[] -> NULL

            but if we want to add any any element in the middle of the list then we have to move to the middle(m) of the list and then create an new node, give it some value then change the reference of the (m-1)th node to the address of our new node and give the address of the (m)th node to our new node. so its time complexity would also be O(n).

 5,[] -> 10,[reference of new_node] -> new_value,[reference of node with value 15] -> 15,[] -> 20,[] -> 25,[] -> NULL

For the deletion operation, if we want to delete an element from the list then we would have to travel from the head node to the element we want to delete and the delete the element and remap the references from the previous node and the next node to the deleted element.

                 if want to delete 15 from our list then we would delete the element 15 from the list and remap the reference from element 10 to 20 in our linked list. so for calculating the time complexity, we have move from the head node to the deleting node, so the time complexity would be O(n).

for accessing a element, the time complexity would also be O(n) as we would have to move from the head node to any element in our list.

So this is all about the simply linked list you all have to know. Make sure to follow our Blog.