Linked List Manipulations

Linked lists are data structures that consist of nodes. Nodes have two parts data part and pointer. The first node of the linked list is head. Programmer can perform the following operations on a linked list:

• Insertion
• Deletion
• Search

Linked List Insertion

Programmer can insert a node in the beginning, middle or at the end of linked list. There are three types of insertions:

• Beginning
• Middle
• End

Insertion in the Beginning

The following code inserts an element in the beginning of the linked list. The function insertStart() makes the new node head of the linked list. It allocates memory for the node and stores its data. It then makes pointer of new node point to head. And head points to previously created node.

void insertStart(int data_val) {
   struct node* new_node = (struct node*) malloc(sizeof(struct node));
   new_node->data = data_val;
   new_node->next = head;
   head = new_node;
}

Insertion in the Middle

The function insertBetween() in the following code inserts a node in the middle of linked list. Just like insertStart() function, insertBetween() function also allocates memory for new node and save its data. It then traverses to the node after which a new node will be inserted. The next pointer of previous node points to the new node and the pointer of new node points to the next node.

void insertBetween(struct node* prev_node, int data_val) {
  if (prev_node == NULL) {
    cout << "the given previous node cannot be NULL";
    return;
  }
  struct node* new_node = (struct node*)malloc(sizeof(struct node));
  new_node->data = data_val;
  new_node->next = prev_node->next;
  prev_node->next = new_node;
}

Insertion in the End

The function insertLast() in the following code inserts a node in the end of linked list. It first allocates memory for the node and then stores data. The new inserted node points to NULL. The next pointer of previously last node points to the new inserted node.

void insertLast(struct node** ref, int data_val) {
  struct node* new_node = (struct Node*)malloc(sizeof(struct Node));
  struct node* last = *ref;
  new_node->data = data_val;
  new_node->next = NULL;
  if (*ref == NULL) {
    *ref = new_node;
    return;
  }
while (last->next != NULL)
    last = last->next;
  last->next = new_node;
  return;
}

For example the code below shows the working of all three insert functions. The program creates a node. It adds further nodes in the beginning, middle and end of the nodes using the different insert functions. In the end, the program displays the resulting linked list using displayList() function. The displayList() function takes a linked list, It starts at the beginning of the linked list, the head. And keeps printing data items of each node until it encounters a node that points to NULL.

#include <stdlib.h>
#include <iostream>
using namespace std;
struct node {
  int data;
  struct node* next;
};
void insertStart(struct node** ptr, int data_val) {
  struct node* new_node = (struct node*)malloc(sizeof(struct node));
  new_node->data = data_val;
  new_node->next = (*ptr);
  (*ptr) = new_node;
}
void insertBetween(struct node* prev_node, int data_val) {
  if (prev_node == NULL) {
    cout << "the given previous node cannot be NULL";
    return;
  }

  struct node* new_node = (struct node*)malloc(sizeof(struct node));
  new_node->data = data_val;
  new_node->next = prev_node->next;
  prev_node->next = new_node;
}

void insertLast(struct node** ptr, int data_val) {
  struct node* new_node = (struct node*)malloc(sizeof(struct node));
  struct node* last = *ptr;

  new_node->data = data_val;
  new_node->next = NULL;

  if (*ptr == NULL) {
    *ptr = new_node;
    return;
  }

  while (last->next != NULL)
    last = last->next;

  last->next = new_node;
  return;
}
void displayList(struct node* node) {
  while (node != NULL) {
    cout << node->data << " ";
    node = node->next;
  }
}
// Driver program
int main() {
  struct node* head = NULL;
  insertStart(&head, 6);
  insertLast(&head, 8);
  insertStart(&head, 2);
  insertStart(&head, 1);
  insertLast(&head, 4);
  insertBetween(head->next, 7);
  cout << "The Linked list is: ";
  displayList(head);
}

The output of the above code after compilation is:

Linked List Deletion

Similar to Insertion, programmer can delete a node from the beginning, middle or end of the linked list. There are three types of linked list deletions

• Beginning
• Middle
• End

Deletion from the Beginning

The following code shows how to delete a node from the beginning of a linked list. The function deleteFirst() works by making the second node head of the linked list.

void deleteFirst(struct node* head) 
{ 
    node* temp = head; 
    head = head->next; 
    delete temp;  
} 

Deletion from the Middle

The following code shows how to delete a node from the middle of a linked list. The function deleteMiddle() works by traversing to the node present before the node that programmer wants to delete. The function make previous node to point to the node after the node that is to be deleted. That means it drops that node to be deleted.

void deleteMiddle(struct node* temp, int index) 
{ 
    for(int i=2; i< index; i++) {
    if(temp->next!=NULL) {
        temp = temp->next;
    }
}
temp->next = temp->next->next;
}

Deletion from the End

The following code shows how to delete a node from the end of a linked list. The function deleteLast() works by traversing to the second last node of the linked list. It makes the second last node point to NULL.

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

For example, in the below code, the program creates a node having a data item and a next pointer. The driver program uses insert functions to create a linked list. It inserts nodes in the beginning, middle and at the end of linked list. After it creates a linked list, it uses deleteNode() function to delete nodes from the linked list. It takes the data item of the linked list as one of its parameters. The other parameter is linked list itself. The deleteNode() function deletes the desired node specified by programmer.

#include <stdlib.h>
#include <iostream>
using namespace std;
struct node {
  int data;
  struct node* next;
};
void insertStart(struct node** ptr, int data_val) {
  struct node* new_node = (struct node*)malloc(sizeof(struct node));
  new_node->data = data_val;
  new_node->next = (*ptr);
  (*ptr) = new_node;
}
void insertBetween(struct node* prev_node, int data_val) {
  if (prev_node == NULL) {
    cout << "the given previous node cannot be NULL";
    return;
  }

  struct node* new_node = (struct node*)malloc(sizeof(struct node));
  new_node->data = data_val;
  new_node->next = prev_node->next;
  prev_node->next = new_node;
}

void insertLast(struct node** ptr, int data_val) {
  struct node* new_node = (struct node*)malloc(sizeof(struct node));
  struct node* last = *ptr;

  new_node->data = data_val;
  new_node->next = NULL;

  if (*ptr == NULL) {
    *ptr = new_node;
    return;
  }

  while (last->next != NULL)
    last = last->next;

  last->next = new_node;
  return;
}
void deleteNode(struct node** ptr, int data_val) {
  struct node *temp = *ptr, *prev;

  if (temp != NULL && temp->data == data_val) {
    *ptr = temp->next;
    free(temp);
    return;
  }
  while (temp != NULL && temp->data != data_val) {
    prev = temp;
    temp = temp->next;
  }
  if (temp == NULL) return;
  prev->next = temp->next;
  free(temp);
}
void displayList(struct node* node) {
  while (node != NULL) {
    cout << node->data << " ";
    node = node->next;
  }
}
// Driver program
int main() {
  struct node* head = NULL;
  insertStart(&head, 6);
  insertLast(&head, 8);
  insertStart(&head, 2);
  insertStart(&head, 1);
  insertLast(&head, 4);
  insertBetween(head->next, 7);
  cout << "The Linked list is: ";
  displayList(head);
  deleteNode(&head, 2);
  deleteNode(&head, 1);
  deleteNode(&head, 4);
  cout << endl;
  cout << "The linked list after deletion of a node is: ";
  displayList(head);
}

The output of the above code after compilation is:

Search

The search function takes a linked list and a data item as its input parameters and its return type is bool. The search starts at the head of linked list and traverses the linked list until it finds a node that points to NULL. While traversing, if it finds a match then it exits the function and returns true. If its does not find a match then it returns false.

bool searchLinkedList(node* head, int data_val)  
{  
    node* temp = head;
    while (temp != NULL)  
    {  
        if (temp->data == data_val)  
            return true;  
        temp = temp->next;  
    }  
    return false;  
}  

The below example shows the working of search function.

#include <stdlib.h>
#include <iostream>
using namespace std;
struct node {
  int data;
  struct node* next;
};
void insertStart(struct node** ptr, int data_val) {
  struct node* new_node = (struct node*)malloc(sizeof(struct node));
  new_node->data = data_val;
  new_node->next = (*ptr);
  (*ptr) = new_node;
}
void insertBetween(struct node* prev_node, int data_val) {
  if (prev_node == NULL) {
    cout << "the given previous node cannot be NULL";
    return;
  }

  struct node* new_node = (struct node*)malloc(sizeof(struct node));
  new_node->data = data_val;
  new_node->next = prev_node->next;
  prev_node->next = new_node;
}

void insertLast(struct node** ptr, int data_val) {
  struct node* new_node = (struct node*)malloc(sizeof(struct node));
  struct node* last = *ptr;

  new_node->data = data_val;
  new_node->next = NULL;

  if (*ptr == NULL) {
    *ptr = new_node;
    return;
  }

  while (last->next != NULL)
    last = last->next;

  last->next = new_node;
  return;
}
bool searchLinkedList(node* head, int data_val)  
{  
    node* temp = head;
    while (temp != NULL)  
    {  
        if (temp->data == data_val)  
            return true;  
        temp = temp->next;  
    }  
    return false;  
}  
void displayList(struct node* node) {
  while (node != NULL) {
    cout << node->data << " ";
    node = node->next;
  }
}
// Driver program
int main() {
  struct node* head = NULL;
  insertStart(&head, 6);
  insertLast(&head, 8);
  insertStart(&head, 2);
  insertStart(&head, 1);
  insertLast(&head, 4);
  insertLast(&head, 4);
  insertBetween(head->next, 7);
  cout << "The Linked list is: ";
  displayList(head);
  cout << endl;
  searchLinkedList(head, 2)? cout<<"Found" : cout<<"Not Found";
}

The output of the above code after compilation is:

Time complexity of Linked List

The table below shows the time complexity of operations performed on linked lists.

Operations	Average Case	Worst Case
Insertion	O(1)	O(1)
Deletion	O(1)	O(1)
Search	O(n)	O(n)

Space complexity of Linked List

The space complexity of linked list is: O(n)