Linked list algorithms: Insert,remove and traverse

In this post, we will discuss linked list algorithms for basic operations on linked list like insert node, delete node and traverse a linked list.

Linked list is a collection of nodes, these nodes being connected to each other using pointer usually referred to as next pointer which stores pointer to immediate next node in linked list. Last node stores NULL as next pointer and that signifies end of list. Typical declaration of node  is as follows

```typedef struct Node {
void * data;
struct Node * next;
} Node;
```

Any node in linked list contains data which can be anything like integer, character, or string or any other structure itself. It also contains a pointer of same type as node type which points to node next to this node as explained above.Typical example of linked list is shown in figure below:

Process of adding a node into a linked list is called as insertion. There are three places where a node can be inserted into linked list.

```1. At start or head of linked list
2. At end or tail of linked list

Before going into details of placing a node, we first need to create a node. To create any node, three steps are to be performed:

```1. Allocated node
2. Set data of allocated node to value provided.
3. Set next pointer to NULL (we will modify it later when we place node in list).
```

Allocation of node

```Node * create_node(int val){
Node * newNode = (Node *)malloc(sizeof(Node));
if(newNode){
newNode->data = value;
newNode->next = NULL;
}
return newNode;
}
```

One condition needs to be taken care of while creating a linked list and that is before head is created,which is first node in the list, there is no node present in list. This is special case in insert operation and needs extra care. Once, head node is inserted, other node can be insert before the head or after the head. This gives rise to two types of insertion operation on list that are:
1. Insertion at front of linked list

When node is inserted at front, next pointer of new node created is set to the present head pointer and head pointer is updated to new node.

```1. Create a node with data and next pointer as null
2. Change next pointer of new node to point to head.
3. Change head of list, now updated to new node.
```

Wrong and most common implementation

```void push(Node *head, int data){
Node * newNode  = (Node *)malloc(sizeof(Node));
newNode->data = data;
}
```

Above code suffers from a very basic problem which  can be stated as : Values assigned to local parameters of a function are never reflected in calling function. So instead of passing head pointer itself, pass pointer to head pointer, i.e. double pointer. So whatever is changed inside the function is also reflected back.

Correct implementation of insertion operation on linked list

```void push(Node **headRef, int data){
Node * newNode  = (Node *)malloc(sizeof(Node));
newNode->data = data;
}
```

2. Insertion at end or tail of linked list.
One way to insert a node at end of linked list to traverse entire list and find the last node, and then change next pointer of last node to point to newly created list.Code shown below:

```void insert_node_at_tail(Node **head,int value){
Node * newNode = createNode(value);

//If this is first node to be inserted
return;
}

//traverse till the end of list
while(current->next){
current = current->next;
}
current->next = newNode;
return;
}
```

When node is inserted at head, every time a new node is inserted, head pointer of linked list changes. Whereas when node is inserted at tail, one needs to scan the whole list in order to reach last node and insert new node. Scanning can be avoided if we can keep a tail pointer which points to current end node of list.

Code to insert at tail

```Node * createNode(int key){
Node * newNode  = (Node *)malloc(sizeof(Node));
newNode->data = data;
newNode->next = NULL;
return newNode;
}
void push_with_tail(Node *headRef, Node *tailRef, int key) {
Node * newNode  = NULL;
newNode = createNode(key);
//Special case to handle first node where head and tail are same.
*tail_ref = newNode
}
// else make next of tail pointer as new node and change the tail pointer.
else{
*tailRef->next  = newNode;
*tailRef = newNode;
}

}
```

There is another method with which we can insert a node, that is using local reference to last node, it is same as head reference, only thing is it stores pointer to the last nodes pointer. Below code implements insert operation using local reference to tail.

```#include <stdio.h>
#include <stdlib.h>
typedef struct node{
int data;
struct node *next;
}Node;

Node * newNode  = (Node *)malloc(sizeof(Node));
newNode->data = key;
}

int main(){
push(localRef, 3);

localRef = &((*localRef)->next);
push(localRef, 4);

localRef = &((*localRef)->next);
push(localRef, 5);

return 0;
}
```

After understanding the basic definition of linked list, let’s move on to second problem on it, that is how to traverse a linked list. For traversing a linked list, all we need is head pointer.
Take another temporary pointer called as current, assign head to it. Now while current is not NULL, print current node’s data and move current to current’s next. Once current becomes NULL, complete list has been traversed.

```void traverseList(Node *head){
while(current){
printf("%d", current->data);
current = current->next;
}
}
```

In the code above current start with head and ends at NULL, this pointer is automatically returned back to heap once function is executed as it is local variable or in an auto variable.
Condition of while loop automatically takes care of condition if the list is NULL, in that case head will be NULL and loop will never be executed. Most important step of traversal is to advance the current pointer to next pointer, most of the infinite loops are result of missing this step.

Next problem on linked list which is commonly asked in interviews is to delete a node from linked list.
To find the node to be deleted, we can traverse the list and compare each node with value to be deleted, once the node is found, what next? To delete a node, we need to connect the previous of current node to next of current node.

But there is no way we can now current node’s previous.  That means we need to traverse with two nodes, one current and other previous which just one node behind current. Initially current is set to head and previous to NULL, before moving current to current’ next next, previous is set to current node. When node to be deleted is found, previous will be just one node behind, and we can link previous’s next to current’s next as

`prev->next = current->next`

Complete code to delete a node from linked list is

```void deleteNode(Node **headRef, int key){
if(!(*headRef)) return; // If the list is empty

}

Node * prev = NULL;

while(current && current->data != key){
prev = current;
current = current->next;

}
// To check if element is present in list
if (current){
prev->next = current->next;
free(current);
}
}
```

There is another interesting variant of this problem, where node’s pointer is given and not the value. If interested, please read through this post : Delete a node from linked list
In this post we learnt basic linked list opearations, how to insert a node, delete a node from it and how to traverse a linked list. In following posts, we will solve some more problems on linked list.