Linked List Operations with Algorithms | Data Structures Using C Tutorials

In this page

A singly linked list is the most simple type of linked list, with each node containing some data as well as a pointer to the next node. That is a singly linked list allows traversal of data only in one way. There are several linked list operations that allow us to perform different tasks.

The basic linked list operations are:

Traversal – Access the nodes of the list.
Insertion – Adds a new node to an existing linked list.
Deletion – Removes a node from an existing linked list.
Search – Finds a particular element in the linked list.

Traverse a Linked List

Accessing the nodes of a linked list in order to process it is called traversing a linked list. Normally we use the traverse operation to display the contents or to search for an element in the linked list. The algorithm for traversing a linked list is given below.

Algorithm: Traverse

Step 1: [INITIALIZE] SET PTR = HEAD
Step 2: Repeat Steps 3 and 4 while PTR != NULL
Step 3:     Apply process to PTR -> DATA
Step 4:     SET PTR = PTR->NEXT
        [END OF LOOP]
Step 5: EXIT

We first initialize PTR with the address of HEAD. Now the PTR points to the first node of the linked list.
A while loop is executed, and the operation is continued until PTR reaches the last node (PTR = NULL).
Apply the process(display) to the current node.
Move to the next node by making the value of PTR to the address of next node.

The following block of code prints all elements in a linked list in C.

struct node *ptr = head;
printf("Elements in the linked list are : ");
while (ptr != NULL)
{
    printf("%d ", ptr->data);
    ptr = ptr->next;
}

Inserting Elements to a Linked List

We will see how a new node can be added to an existing linked list in the following cases.

The new node is inserted at the beginning.
The new node is inserted at the end.
The new node is inserted after a given node.

Insert a Node at the beginning of a Linked list

Consider the linked list shown in the figure. Suppose we want to create a new node with data 24 and add it as the first node of the list. The linked list will be modified as follows.

inserting an element in the beginning of a linked list 1

Allocate memory for new node and initialize its DATA part to 24.
Add the new node as the first node of the list by pointing the NEXT part of the new node to HEAD.
Make HEAD to point to the first node of the list.

Algorithm: InsertAtBeginning

Step 1: IF AVAIL = NULL
           Write OVERFLOW
           Go to Step 7
        [END OF IF]
Step 2: SET NEW_NODE = AVAIL
Step 3: SET AVAIL = AVAIL -> NEXT
Step 4: SET NEW_NODE -> DATA = VAL
Step 5: SET NEW_NODE -> NEXT = HEAD
Step 6: SET HEAD = NEW_NODE
Step 7: EXIT

Note that the first step of the algorithm checks if there is enough memory available to create a new node. The second, and third steps allocate memory for the new node.

This algorithm can be implemented in C as follows:

struct node *new_node;
new_node = (struct node*) malloc(sizeof(struct node));
new_node->data = 24;
new_node->next = head;
head = new_node;

Insert a Node at the end of a Linked list

Take a look at the linked list in the figure. Suppose we want to add a new node with data 24 as the last node of the list. Then the linked list will be modified as follows.

inserting an element in the end of a linked list

Allocate memory for new node and initialize its DATA part to 24.
Traverse to last node.
Point the NEXT part of the last node to the newly created node.
Make the value of next part of last node to NULL.

Algorithm: InsertAtEnd

Step 1: IF AVAIL = NULL
           Write OVERFLOW
           Go to Step 10
        [END OF IF]
Step 2: SET NEW_NODE = AVAIL
Step 3: SET AVAIL = AVAIL -> NEXT
Step 4: SET NEW_NODE -> DATA = VAL
Step 5: SET NEW_NODE -> NEXT = NULL
Step 6: SET PTR = HEAD
Step 7: Repeat Step 8 while PTR -> NEXT != NULL
Step 8:     SET PTR = PTR -> NEXT
        [END OF LOOP]
Step 9: SET PTR -> NEXT = NEW_NODE
Step 10: EXIT

This can be implemented in C as follows,

struct node *new_node;
new_node = (struct node*) malloc(sizeof(struct node));
new_node->data = 24;
new_node->next = NULL;

struct node *ptr = head;
while(ptr->next != NULL){
  ptr = ptr->next;
}

ptr->next = new_node;

Insert a Node after a given Node in a Linked list

The last case is when we want to add a new node after a given node. Suppose we want to add a new node with value 24 after the node having data 9. These changes will be done in the linked list.

inserting an element after an element in a linked list 1

Allocate memory for new node and initialize its DATA part to 24.
Traverse the list until the specified node is reached.
Change NEXT pointers accordingly.

Algorithm: InsertAfterAnElement

Step 1: IF AVAIL = NULL
           Write OVERFLOW
           Go to Step 12
        [END OF IF]
Step 2: SET NEW_NODE = AVAIL
Step 3: SET AVAIL = AVAIL -> NEXT
Step 4: SET NEW_NODE -> DATA = VAL
Step 5: SET PTR = HEAD
Step 6: SET PREPTR = PTR
Step 7: Repeat Steps 8 and 9 while PREPTR -> DATA != NUM
Step 8:     SET PREPTR = PTR
Step 9:     SET PTR = PTR -> NEXT
        [END OF LOOP]
Step 1 : PREPTR -> NEXT = NEW_NODE
Step 11: SET NEW_NODE -> NEXT = PTR
Step 12: EXIT

Deleting Elements from a Linked List

Let’s discuss how a node can be deleted from a linked listed in the following cases.

The first node is deleted.
The last node is deleted.
The node after a given node is deleted.

Delete a Node from the beginning of a Linked list

Suppose we want to delete a node from the beginning of the linked list. The list has to be modified as follows:

Check if the linked list is empty or not. Exit if the list is empty.
Make HEAD points to the second node.
Free the first node from memory.

Algorithm: DeleteFromBeginning

Step 1: IF HEAD = NULL
           Write UNDERFLOW
           Go to Step 5
        [END OF IF]
Step 2: SET PTR = HEAD
Step 3: SET HEAD = HEAD -> NEXT
Step 4: FREE PTR
Step 5: EXIT

This can be implemented in C as follows,

if(head == NULL)
{
  printf("Underflow"); 
}
else
{
  ptr = head;
  head = head -> next;
  free(ptr);
}

Delete last Node from a Linked list

Suppose we want to delete the last node from the linked list. The linked list has to be modified as follows:

Traverse to the end of the list.
Change value of next pointer of second last node to NULL.
Free last node from memory.

Algorithm: DeleteFromEnd

Step 1: IF HEAD = NULL
           Write UNDERFLOW
           Go to Step 8
        [END OF IF]
Step 2: SET PTR = HEAD
Step 3: Repeat Steps 4 and 5 while PTR -> NEXT != NULL
Step 4:     SET PREPTR = PTR
Step 5:     SET PTR = PTR -> NEXT
        [END OF LOOP]
Step 6: SET PREPTR -> NEXT = NULL
Step 7: FREE PTR
Step 8: EXIT

Here we use two pointers PTR and PREPTR to access the last node and the second last node. This can be implemented in C as follows,

if(head == NULL)
{
  printf("Underflow"); 
}
else
{
  struct node* ptr = head;
  struct node* preptr = NULL;
  while(ptr->next!=NULL){
    preptr = ptr;
    ptr = ptr->next;
  }
  preptr->next = NULL;
  free(ptr);
}

Delete the Node after a given Node in a Linked list

Suppose we want to delete the that comes after the node which contains data 9.

deleting the node after a given node in a linked list

Traverse the list upto the specified node.
Change value of next pointer of previous node(9) to next pointer of current node(10).

Algorithm: DeleteAfterANode

Step 1: IF HEAD = NULL
           Write UNDERFLOW
           Go to Step 10
        [END OF IF]
Step 2: SET PTR = HEAD
Step 3: SET PREPTR = PTR
Step 4: Repeat Steps 5 and 6 while PREPTR -> DATA != NUM
Step 5:     SET PREPTR = PTR
Step 6:     SET PTR = PTR -> NEXT
        [END OF LOOP]
Step 7: SET TEMP = PTR
Step 8: SET PREPTR -> NEXT = PTR -> NEXT
Step 9: FREE TEMP
Step 10 : EXIT

Implementation in C takes the following form:

if(head == NULL)
{
  printf("Underflow"); 
}
else
{
  struct node* ptr = head;
  struct node* preptr = ptr;
  while(ptr->data!=num){
    preptr = ptr;
    ptr = ptr->next;
  }
  struct node* temp = ptr;
  preptr -> next = ptr -> next;
  free(temp);
}

Search

Finding an element is similar to a traversal operation. Instead of displaying data, we have to check whether the data matches with the item to find.

Initialize PTR with the address of HEAD. Now the PTR points to the first node of the linked list.
A while loop is executed which will compare data of every node with item.
If item has been found then control goes to last step.

Algorithm: Search

Step 1: [INITIALIZE] SET PTR = HEAD
Step 2: Repeat Steps 3 and 4 while PTR != NULL
Step 3:     If ITEM = PTR -> DATA
                SET POS = PTR
                Go To Step 5
            ELSE
                SET PTR = PTR -> NEXT
            [END OF IF]
        [END OF LOOP]
Step 4: SET POS = NULL
Step 5: EXIT

Search operation can be implemented in C as follows:

struct node* ptr = head;
struct node* pos = NULL;
while (ptr != NULL) {
  if (ptr->data == item)
    pos = ptr
    printf("Element Found");
    break;
  else
    ptr = ptr -> next; 
}