2 Basic Linked List Operations For Kids Advantage

This post is also available in: हिन्दी (Hindi) العربية (Arabic)

The Linked Lists are a type of data structure. These are of three types, viz. Simple Linked List, Double-Linked, and Circular Linked List. All of these linked lists are linear data structures and therefore, traversed sequentially. There are 2 types of operations that can be performed on these linked lists. This article is about 2 basic operations on linked list for kids’ advantage.

2 Basic Operations on Linked List

Following are the basic operations supported by a list.

• Insertion − Adds an element to the list.
• Deletion − Deletes an element from the list.

Insertion of a Node

Insertion is the process of adding a new node to an existing linked list. A new element can be inserted either at the beginning of a linked list or at the end of the linked list or any position in the linked list.

Insertion of a Node – Simple Linked List

The approach followed to insert a new node in a simple linked list is

• Traverse the linked list up to the position p1(p1 is the position where the new node is inserted).
• Once all the nodes till p1 are traversed, allocate memory, and the given data to the new node.
• Point the next pointer of the new node to the next of the current node.
• Point the next point of the current node to the new node.

Code For Insertion in Simple Linked List in C++

struct Node
{
   int data;
   struct Node *next;
};
void insert(struct Node* prev_node, int node_data)
{
if (prev_node == NULL)
{
   cout<<"the given previous node is required,cannot be NULL"; return; }
   struct Node* newNode =new Node;
   newNode->data = node_data;
   newNode->next = prev_node->next;
    prev_node->next = newNode;
}
int main()
{
struct Node* head = NULL;
insert(head->next, 50);
return 0;
}

Insertion of a Node – Doubly-Linked List

The approach followed to insert a new node in a doubly-linked list is

• Traverse to (p – 1) position node in the list, where p is the position to insert. 
• Create a new node and assign the data to its data field.
• Connect the next address of a new node with the node pointed by the next address of (p -1) node.
• Connect the previous address field of the new node with (p – 1) node.
• Check if the next address of (p – 1) node is not NULL, then connect the previous address of the node next to (p – 1) node to the new node. 
• Connect the next of (p – 1) node to a new node.

Code For Insertion in Doubly-Linked List in C++

struct Node {
   int data;
   struct Node* next;
   struct Node* prev;
};
void insert(struct Node* prev_node, int new_data)
{
   if (prev_node == NULL) {
   cout<<"Previous node is required , it cannot be NULL";
   return;
}
   struct Node* newNode = new Node;
   newNode->data = new_data;
   newNode->next = prev_node->next;
   prev_node->next = newNode;
   newNode->prev = prev_node;
   if (newNode->next != NULL)
   newNode->next->prev = newNode;
}
int main() {
   struct Node* head = NULL;
   insert(head->next, 30);
   return 0;
}

Deletion of a Node

Deletion is the process of removing a node from an existing linked list. A deleted node can be either at the beginning or at the end or any position in the linked list.

Deletion of a Node – Simple Linked List

The approach followed to delete a node from a simple linked list is

• Find the previous node of the node to be deleted.
• Change the next of the previous node.
• Free memory for the node to be deleted.

Code For Deletion in Simple Linked List in C++

struct node{
    int data;
    node* next;
};
void delete_node(node** head,int x){
    if((*head)->next==NULL){
        *head=NULL;
        return;
    }
    struct node* temp=*head;
    if(temp->data==x){
    	temp=temp->next;
    	*head=temp;
    	return;
    }
    while(temp){
    	if(temp->data==x){
    		temp->data=temp->next->data;
    		temp->next=temp->next->next;
    		break;
    	}
    	temp=temp->next;
    }
}
int main()
{
    struct node* n=NULL;
    delete_node(&n,2);
   return 0;
}

Deletion of a Node – Doubly Linked List

The approach followed to delete a node from a doubly-linked list is

• Traverse the linked list from the head until the required position is reached (let it be temp).
• Assign the next pointer of temp to temp’s previous node’s next pointer.
• Assign the temp’s previous pointer to the temp’s next node’s previous pointer.
• Free temp node.

Code For Deletion in Doubly Linked List in C++

struct node {
   int data;
   struct node *prev;
   struct node *next;
};
void remove_data(int data) {
   int pos = 0;
   struct node *pre_node;
   if(head->data == data) {
      if(head->next != NULL) {
         head->next->prev = NULL;
         head = head->next;
         return;
      } else {
         head = NULL;
         return;
      }
   } else if(head->data != data && head->next == NULL) {
      printf("%d not found in the list\n", data);
      return;
   }
   current = head;
   while(current->next != NULL && current->data != data) {
      pre_node = current;
      current = current->next;
   }        
   if(current->data == data) {
      pre_node->next = pre_node->next->next;
      if(pre_node->next != NULL) {          // link back
         pre_node->next->prev = pre_node;
      } else
         last = pre_node;
      free(current);
   } else
      printf("%d not found in the list.", data);
}
int main() {
   remove_data(20);
   return 0;
}