There are various linked list operations that allow us to perform different actions on linked lists. For example, the insertion operation adds a new element to the linked list.

Here's a list of basic linked list operations

• Traversal - access each element of the linked list
• Insertion - adds a new element to the linked list
• Deletion - removes the existing elements
• Search - Find a node in the linked list
• Sort - sort the nodes of the linked list

Traverse a Linked List

Displaying the contents of a linked list is very simple. We keep moving the temp node to the next one and display its contents.

When the temp is NULL, we know that we have reached the end of the linked list so we get out of the while loop

struct node *temp = head;
printf("\n\nList elements are - \n");
while(temp != NULL) {
  printf("%d --->",temp->data);
  temp = temp->next;
}

Insert Elements to a Linked List

You can add elements to either the beginning, middle, or end of the linked list.

1. Insert at the beginning

• Allocate memory for the new node
• Store data
• Change next of new node to point to head
• Change head to point to the recently created node

struct node *newNode;

newNode = malloc(sizeof(struct node));

newNode->data = 4;

newNode->next = head;

head = newNode;

2. Insert at the End

• Allocate memory for the new node

• Store data

• Traverse to the last node

• Change next of the last node to the recently created node

struct node *newNode;

newNode = malloc(sizeof(struct node));

newNode->data = 4;

newNode->next = NULL;

struct node *temp = head;

while(temp->next != NULL){

  temp = temp->next;

}


temp->next = newNode;

3. Insert at the Middle

• Allocate memory and store data for the new node

• Traverse to node just before the required position of new node

• Change next pointers to include new node in between

  struct node *newNode;
  newNode = malloc(sizeof(struct node));
  
  
  
  newNode->data = 4;
  
  struct node *temp = head;
  
  for(int i=2; i < position; i++) {
    if(temp->next != NULL) {
      temp = temp->next;
    }
  }
  newNode->next = temp->next;
  temp->next = newNode;
  

Delete from a Linked List

You can delete either from the beginning, end, or from a particular position.

1. Delete from beginning

Point head to the second node

head = head->next;

2. Delete from end

• Traverse to second last element
-

Change its next pointer to null

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

3. Delete from middle

• Traverse to element before the element to be deleted
• Change next pointers to exclude the node from the chain

  for(int i=2; i< position; i++) {

  if(temp->next!=NULL) {

    temp = temp->next;

  }

}


temp->next = temp->next->next;

Search an Element on a Linked List

You can search an element on a linked list using a loop using the following steps. We are finding item on a linked list.

• Make head as the current node.
• Run a loop until the current node is NULL because the last element points to NULL.
• In each iteration, check if the key of the node is equal to item. If it the key matches the item, return true otherwise return false.

// Search a node

bool searchNode(struct Node** head_ref, int key) {

  struct Node* current = *head_ref;


  while (current != NULL) {

    if (current->data == key) return true;

      current = current->next;

  }

  return false;

}

Sort Elements of a Linked List

We will use a simple sorting algorithm, Bubble Sort, to sort the elements of a linked list in ascending order below.

• Make the head as the current node and create another node index for later use. If the head is null, return.
• Else, run a loop till the last node (i.e. NULL).
• In each iteration, follow the following step 5-6.
• Store the next node of current in index.
• Check if the data of the current node is greater than the next node. If it is greater, swap current and index.

• Check the article on bubble sort for better understanding of its working.

  // Sort the linked list
  void sortLinkedList(struct Node** head_ref) {
    struct Node *current = *head_ref, *index = NULL;
    int temp;
  
    if (head_ref == NULL) {
      return;
    } else {
      while (current != NULL) {
        // index points to the node next to current
        index = current->next;
  
      while (index != NULL) {
          if (current->data > index->data) {
            temp = current->data;
            current->data = index->data;
            index->data = temp;
            }
            index = index->next;
      }
      current = current->next;
      }
  }}