Code for Insertion in singly Linked List

In computer science, a linked list is a linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a collection of nodes that together represent a sequence. In its most basic form, each node contains data and a reference (in other words, a link) to the next node in the sequence. 

Linked lists are among the simplest and most common data structures. They can be used to implement several other common abstract data types, including lists, stacks, queues, associative arrays, and S-expressions, though it is not uncommon to implement those data structures directly without using a linked list as the basis.

Insertion

 

Insertion operation of linked list adds an item to the linked list. Though it may sound simple, given the structure of the linked list, we know that whenever a data item is added to the linked list, we need to change the next pointers of the previous and next nodes of the new item that we have inserted.

The second thing that we have to consider is the place where the new data item is to be added.

Algorithm 

STEP-1: IF PTR = NULL 

Write OVERFLOW

 Go to STEP-7

ELSE

STEP-2: SET NEW_NODE = PTR 

STEP-3: SET PTR = PTR → NEXT 

STEP-4: SET NEW_NODE → DATA = VAL 

STEP-5: SET NEW_NODE → NEXT = HEAD

 STEP-6: SET HEAD = NEW_NODE 

STEP-7: EXIT

There are three positions in the linked list where a data item can be added.

 

1) At the beginning of the linked list

A linked list is shown below 2->4->6->8->10. If we want to add a new node 1, as the first node of the list, then the head pointing to node 2 will now point to 1 and the next pointer of node 1 will have a memory address of node 2 as shown in the below figure.

 

Fig 1:-Insertion at the beginning

Thus the new linked list becomes 1->2->4->6->8->10.

2) After the given Node

Here, a node is given and we have to add a new node after the given node. In the below-linked list a->b->c->d ->e, if we want to add a node f after node c then the linked list will look as follows:

 

Fig 2:- Insertion after the given node

 

Thus in the above diagram, we check if the given node is present. If it’s present, we create a new node f. Then we point the next pointer of node c to point to the new node f. The next pointer of the node f now points to node d.

3) At the end of the Linked List

In the third case, we add a new node at the end of the linked list. Consider we have the same linked list a->b->c->d->e and we need to add a node f to the end of the list. The linked list will look as shown below after adding the node.

Fig 3 :- Insertion at the end of the linklist

 

Thus, we create a new node f. Then the tail pointer pointing to null is pointed to f and the next pointer of node f is pointed to null. We have implemented all three types of insert functions in the below C++ program.

In C++, we can declare a linked list as a structure or as a class. Declaring a linked list as a structure is a traditional C-style declaration. A linked list as a class is used in modern C++, mostly while using the standard template library.

In the following program, we have used structure to declare and create a linked list. It will have data and pointer to the next element as its members.

#include <iostream> using namespace std;   // A linked list node struct Node {    int data;    struct Node *next; }; //insert a new node in front of the list void push(struct Node** head, int node_data) {    /* 1. create and allocate node */    struct Node* newNode = new Node;      /* 2. assign data to node */    newNode->data = node_data;      /* 3. set next of new node as head */    newNode->next = (*head);      /* 4. move the head to point to the new node */    (*head) = newNode; }   //insert new node after a given node void insertAfter(struct Node* prev_node, int node_data) {   /*1. check if the given prev_node is NULL */ if (prev_node == NULL) {    cout<<"the given previous node is required,cannot be NULL"; return; }      /* 2. create and allocate new node */    struct Node* newNode =new Node;      /* 3. assign data to the node */    newNode->data = node_data;      /* 4. Make next of new node as next of prev_node */    newNode->next = prev_node->next;       /* 5. move the next of prev_node as new_node */     prev_node->next = newNode; }   /* insert new node at the end of the linked list */ void append(struct Node** head, int node_data) { /* 1. create and allocate node */ struct Node* newNode = new Node;   struct Node *last = *head; /* used in step 5*/   /* 2. assign data to the node */ newNode->data = node_data;   /* 3. set next pointer of new node to null as its the last node*/ newNode->next = NULL;   /* 4. if list is empty, new node becomes first node */ if (*head == NULL) { *head = newNode; return; }   /* 5. Else traverse till the last node */ while (last->next != NULL) last = last->next;   /* 6. Change the next of last node */ last->next = newNode; return; }   // display linked list contents void displayList(struct Node *node) {    //traverse the list to display each node    while (node != NULL)    {       cout<<node->data<<"-->";       node = node->next;    }   if(node== NULL) cout<<"null"; } /* main program for linked list*/ int main() { /* empty list */ struct Node* head = NULL;   // Insert 10. append(&head, 10);   // Insert 20 at the beginning. push(&head, 20);   // Insert 30 at the beginning. push(&head, 30);   // Insert 40 at the end. append(&head, 40); //   Insert 50, after 20. insertAfter(head->next, 50);   cout<<"Final linked list: "<<endl; displayList(head);   return 0; }

Output:

Final linked list:

30–>20–>50–>10–>40–>null

Related Post