Insertion in Linked List

A linked list is a set of data structures interconnected by links. A linked list is a set of links that contains items. Linked lists are the second most widely used data structure after arrays.

Insertion in Linked list:

There are three situations for inserting element in list.

Insertion at the beginning.
Insertion in the given location.
Insertion at the end.

Steps to insert an item into a linked list:

Step-1: Get the value of the NEW node to add to the list and its position. Step-2: Call malloc () to create a new empty node. If malloc () does not return an error, go to step 3 or say “out of memory.” Step-3: Insert the data value into the data field of the NEW node. Step-4: Add this new node to the desired location (denoted by “location”) in the list. Step-5: Continue with Step 1 until you have more values to add to the list.

Insertion Node in Linked List:

Here Code:

void insert(node *ptr, int data)
{
while(ptr->next!=NULL)
{
ptr = ptr -> next;
}
ptr->next = (node *)malloc(sizeof(node));
ptr = ptr->next;
ptr->data = data;
ptr->next = NULL;
}

Insertion at the beginning:

Allocate memory to the new node.
Save data.
Change the new node to point to the side of the head.
Change the head to point to the newly created node.

For example:

Here Code:

struct node *newNode;
newNode = malloc(sizeof(struct node));
newNode->data = 4;
newNode->next = head;
head = newNode;

Insertion at the given location:

Allocate memory and save data for new nodes.
Move to the previous node in the required location of the new node.
Change the next pointer to include a new node in the middle.

For example:

Here Code:

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;

Insertion at the end:

Allocate memory to the new node.
Save data.
Scroll to the last node.
Replace the node next to the last node with the newly created node.

For example:

Here Code:

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;

Below is a complete data structure program using C ++ that uses all of the above methods or examples to create a linked list.

For example:

Here Code:

#include <bits/stdc++.h>
using namespace std;
class Node
{
public:
int data;
Node *next;
};
void push(Node** head_ref, int new_data)
{
Node* new_node = new Node();
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
void insertAfter(Node* prev_node, int new_data)
{
if (prev_node == NULL)
{
cout<<"the given previous node cannot be NULL";
return;
}
Node* new_node = new Node();
new_node->data = new_data;
new_node->next = prev_node->next;
prev_node->next = new_node;
}
void append(Node** head_ref, int new_data)
{
Node* new_node = new Node();
Node *last = *head_ref;
new_node->data = new_data;
new_node->next = NULL;
if (*head_ref == NULL)
{
*head_ref = new_node;
return;
}
while (last->next != NULL)
last = last->next;
last->next = new_node;
return;
}
void printList(Node *node)
{
while (node != NULL)
{
cout<<" "<<node->data;
node = node->next;
}
}
int main()
{
Node* head = NULL;
append(&head, 6);
push(&head, 7);
push(&head, 1);
append(&head, 4);
insertAfter(head->next, 8);
cout<<"Created Linked list is: ";
printList(head);
return 0;
}

Conclusion:

A linked list is a data structure that is used to store data items in a linear fashion but in non-contiguous locations. Linked lists are expensive as far as traversal is concerned, as items such as arrays cannot be randomly accessed. However, the cost of the insert operation is less compared to a matrix.