To insert an element in the list, the first task is to create a new node, assign the element to be inserted to the info field of the node, and then place the new node at the appropriate position by adjusting the appropriate pointers. Insertion in the list can take place at the following positions:

  • At the beginning of the list
  • At the end of the list
  • After a given element

Insertion at the Beginning of the List

First, test whether the linked list is initially empty, if yes, then the element is inserted as the first and only one element by performing the following steps:

  • Assign NULL to the next pointer field of the new node.
  • Assign the address of the new node to head.

If the list is not empty, then the element is inserted as the first element of the list by performing the following steps:

  • Assign the value of head to the next pointer field of the new node.
  • Assign the address of the new node to head.

Programmatically, both cases are equivalent. This is because in both the cases the first step is to assign the value of head (NULL or otherwise) to the next pointer field of the new node.

.cf { font-family: Lucida Console; font-size: 9pt; color: black; background: white; }
.cl { margin: 0px; }
.cb1 { color: green; }
.cb2 { color: blue; }

 

void insertatbeginning(node **head, int item)
{
 node *newNode;

 /* allocate memory for the new node and initialize the data in it*/
 newNode= malloc(sizeof(node));
 newNode->info=item;

 /* assign the value of head to the “next” of newNode*/
 newNode->next=*head;

 /* assign the address of newNode to head */
 *head=newNode;
}

 

Inserting at the End of the List

First test whether the linked list is initially empty, if yes, then the element is inserted as the first and only one element by performing the following steps:

  • Assign NULL to the next pointer field of the new node.
  • Assign the address of the new node to head.

If the list is not empty, we traverse it to reach the last element, and then the new node is inserted as the last element of the list by performing the following steps:

  • Assign NULL to the next pointer field of the new node.
  • Assign the address of the new node to the next pointer field of the last node.

 

void insertatend(node **head, int item)
{
 node *newNode;
 newNode=malloc(sizeof(node));
 newNode->info=item;
 newNode->next=NULL;
 if(*head==NULL)
 *head=newNode;
 else
 {
 node * prev=*head;
 while (prev->next!=NULL)
 prev=prev->next;
 prev->next=newNode;
 }
}

 

Inserting after Given Element

To insert a new element after the given element, first we find the location, say loc, of the given element in the list, and then the element is inserted in the list by performing the following steps:

  • Assign the next pointer field of the node pointed to by loc to the next pointer field of the new node.
  • Assign the address of the new node to the next pointer field of the node pointed to by loc.

 

void insertafterelement(node *head, int item,int after)
{
 node *newNode, *loc;
 loc=searchunsortedlist(head,after);
 if(loc==NULL) /*element after not found*/
 return;
 newNode=malloc(sizeof(node));
 newNode->info=item;
 newNode->next=loc->next;
 loc->next=newNode;
}