Linked list algorithms: Insert,remove and traverse

Linked list algorithms and operations

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:
linked list operations

For reading on differences between array and linked lists, please refer to difference between arrays and linked list

Linked list operations : Insert node in linked list

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
3. In between 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. 

Linked List algorithms and operations
Insert a node in linked list at front

Insertion in linked list at head can be summarized as follows:

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;
	newNode->next = head;
	head  = newNode;
}

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;
	newNode->next = *headRef;
	*headRef  = new_node;
}

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 * current = *head;
    Node * newNode = createNode(value);

    //If this is first node to be inserted
    if(!(*head)){
      *head = newNode;
      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.

Insert a node at the end of linked list
Insert a node at the end of linked 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.
 	if(!(*headRef)){
 		*headRef = newNode;
 		*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;

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

int main(){
    Node * head = NULL;
    Node ** localRef = &head;
    push(localRef, 3);

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

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

    traverse_list(head);
    return 0;
}

Linked list operations : Traverse linked list

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.

Code to traverse linked list

void traverseList(Node *head){
    Node * current = 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.

Linked list operations : Delete node from linked list

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.

delete node from linked list

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
	
	if((*headRef)->data == key){
		Node *nextNode = (*headRef)->next;
		free(*headRef);
		*headRef = nextNode;
	}

	Node * current = *headRef;
	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.

Please share if there is something wrong or missing. If you are interested in contributing to website, please contact us and earn.