Linked List Part 3 || Operations on Simple Linked List in C language

What are these operations on linked list ? Let's see

In the last post we had discussed about Simple linked list and we created a linked list and traversed through it using C language.
In this post we will look at some basic operations that we can perform on linked list like insertion and deletion to make it a more useful data structure.
The operations can be : 
1. Insertion at head node
2. Insertion in between ( by index)
3. Insertion at the end
4. Deletion by known value in a node
5. Deletion at head node
6. Deletion by index 
7. Deletion at the end
We will make a separate function for each operation and call each function in the main function.
I will not be explaining here how to implement Simple Linked List un C. For that I suggest you to refer a post by clicking here if you are not familiar with the method to do it.
Explaining briefly we fist create structure with only two propertied "data" and "next node address pointer". We dynamically allocate memory in heap using malloc and then we print the whole linked list by passing address of head to the traversing function.

Coming back to the operations... 

Before we making the functions lets discuss logic for insertion and deletion :

To insert an element we need to create a new node for that element in heap...

Here we have shown an example of new node with value 12 in it.

In C we will do it like this : 

  struct Node *newNode = (struct Node*) malloc(sizeof(struct Node));
  newNode -> data = newData;

We will pass the value for newData in function call.

 Now, We have 3 cases in insertion :

    1. at start

    2. in between the nodes

    3. after last node

For insertion at the start :

>>> We simply point the newly created node to  previous "head". (Address of head will be taken in the function call)

>>> We assign head = newNode ; and return value of updated head.

Function to insert at start/head : 

// insertAtFirst function
// to insert at index 0

struct Node * insertAtFirst(struct Node *head, int newData){
  struct Node *newNode = (struct Node*) malloc(sizeof(struct Node));
    
  newNode -> nextAdd = head;
  newNode -> data = newData;
  head = newNode;
  return head;
}

Insertion at end is easier so lets discuss that then we will discuss insertion in between.

For insertion at the end :

For any insertion it's compulsory to create a new node. To insert at the end. 

>>> We do not know the address of last node. For that set a pointer node to head and start moving it ahead till it finds the nextAdd of a particular node as "NULL". 

>>> This will indicate the last node. Now As we are at the last node we change the nextAdd of the last node to newly created node.

>>> Lastly we we set nextAdd of our newNode = NULL. to set it as the last node and finally return head.

Function to insert at end : 

// insertAtEnd function
// to insert at last index 
struct Node * insertAtEnd(struct Node *head, int newData){
  struct Node *newNode = (struct Node*) malloc(sizeof(struct Node));
  newNode -> data = newData;
  
  struct Node * runner = head;
  // int i = 0;
  while (runner -> nextAdd != NULL){
    runner = runner -> nextAdd;
    //i++;
  }
  newNode -> nextAdd = runner -> nextAdd;
  runner -> nextAdd = newNode;
  return head;
}

Now its time to discuss the insertion in between :

We insert in between (or after) an index, or by chance if we directly know the address of node after which insertion has to be done. 

For insertion at index : 

>>> unlike arrays we do not have index directly associated with each node, so we need to start traversal from head and reach the node after which insertion has to be done.

>>> Let's call our pointer node as runner because its running along the linked list. we will assume head having index 0. if we are given an index say 3, then we will move runner node 2 times and thus reach the required position... or if we want to insert at index 2, we will move runner only once. We will stop at one position before the given node. 

>>> We stop one position prior because the actual address of required node is stored in variable "nextAdd" of the previous node where we stop.

>>> For ease of understanding let's consider the above image as example where we have to insert 12 at index 2 (Note : head has index 0). 

>>> When runner reaches index 1 (node just before index 2) we will first write

newNode->nextAdd = runner->nextAdd; to link our new node to next address of node where our runner is... then 

write runner->nextAdd = newNode to link runner to new node, and we return head finally completing this insertion.

>>> As we our talking about insertion by index the user might also give index 0. The problem is if index is N then we move the runner N-1 times, for index N=0, we cannot move N-1  i.e., 0-1 = -1 times as there is no node before head.

>>> so either we can give user a message to use that separate function insertAtFirst() but we are responsible coders so we can writhe a bit of code to solve this problem too. Its a simple set of if conditional statement.

>>> If(index == 0){

            use code of insertAtFirst()

        }

       else{

            go with the regular code for insertAtIndex()

        }

Function to insert at index : 

// insertAtIndex function
// to insert from index 0 to last
struct Node * insertAtIndex(struct Node *head, int newData, int index){
  
  if(index == 0){
    struct Node *newNode = (struct Node*) malloc(sizeof(struct Node));
    
  newNode -> nextAdd = head;
  newNode -> data = newData;
  head = newNode;
  return head;
  }
  else{
      printf("m here\n");
      struct Node *newNode = (struct Node*) malloc(sizeof(struct Node));
      newNode -> data = newData;
  
      struct Node * runner = head;
      int i = 0;
      while (i != index - 1){
        runner = runner -> nextAdd;
        i++;
      }
      newNode -> nextAdd = runner -> nextAdd;
      runner -> nextAdd = newNode;
      return head;
  }
}

In the next post we will implement deletion liked list and also the complete program for insertion and deletion.

click here for the link to complete code for insertion and deletion in simple linked list.

Till then, 

 #KeepLerningKeepGrowing