Insertion in a Single Linked List ~ Webkit academy

Insertion in Single Linked list

There can be four cases while inserting a node in a linked list.

Insertion at the beginning.
Insertion in an empty list.
Insertion at the end.
Insertion in between the list nodes.
Insertion at the given position.

To insert a node, initially we will dynamically allocate space for that node using malloc( ).

tmp=(struct node *)malloc(sizeof(struct node));
tmp->info=data;

The link part of the node contains garbage value; we will assign address to it separately in the different cases.

1. Insertion at the beginning

Suppose, we have to insert node T at the beginning of the list and the first node of list is node P at this time, so the new node T should be inserted before it.

We know that before the insertion of any node start has address of node P.
To insert a node tmp the address of node P should be assigned in tmp->link that is stored in start.

tmp->link = start;

After this statement, link of node T will point to node P.

We want to make node T the first node, hence we should update start so that now it points to node T.

start = tmp;

The following function addatbeg( ) adds a node at the beginning of the list.

// function definition to insert a node at the beginning
struct node *addatbeg(struct node *start, int data)
{
struct node *tmp;
tmp = (struct node *)malloc(sizeof(struct node));
tmp->info = data;
tmp->link = start;
start = tmp;
return start;
}

2. Insertion in an empty list

When the list is empty, value of start will be NULL. The new node that we are adding will be the only node in the list. Since, it is the first node, start should point to this node and it is also the last node so its link should be NULL.

tmp->link = NULL;
start = tmp;

3. Insertion at the end of the list

We have to insert a new node T at the end of the list. Suppose the last node of list is node P, so node T should be inserted after node P.

In this case, we have a pointer ptr that will be used to traversing of list. Here, we want the loop to terminate when ptr is pointing to the last node so the terminating condition is (ptr->link != NULL).

The following function addatend( ) insert a node at the end of the list.

// function definition to add a node at the end of the list
struct node *addatend(struct node *start, int data)
{
struct node *ptr, *tmp;
tmp = (struct node *)malloc(sizeof(struct node));
tmp->info = data;
ptr = start;
while(ptr->link!=NULL)
ptr = ptr->link;
ptr->link = tmp;
tmp->link = NULL;
return start;
}

4. Insertion in between the list nodes

In this case, we are given a value from the list and we have to insert the new node after the node that contains this value. Suppose the node P contains the given value, and the node Q is its successor. We have to insert the new node T after node P.

We need to find the pointer ptr which points to the node that contains item. The procedure is same as we have seen in searching of an element in the linked list.

// function definition to add node between the nodes of list
struct node *addafter(struct node *start, int data, int item)
{
struct node *tmp, *ptr:
ptr = start;
while(ptr!=NULL)
{
if(ptr->info == item)
{
tmp = (struct node *)malloc(sizeof(struct node));
tmp->info = data;
tmp->link = ptr->link;
ptr->link = tmp;
return start;
}
ptr = ptr->link;
}
printf("%d not present in the list\n",item);
return start;
}

5. Insertion at a given position

In this case we have to insert the new node at a given position. The two insertion statements are same as in the previous cases (tmp->link = ptr->link; ptr->link = tmp;).

// To add node at the given position
struct node *addatpos(struct node *start, int data, int pos)
{
struct node *tmp, *ptr;
int i;
tmp = (struct node *)malloc(sizeof(struct node));
tmp->info = data;
if(pos==1)
{
tmp->link = start;
start = tmp;
return start;
}
ptr = start;
for(i=1; i<pos-1 && ptr!=NULL; i++)
ptr = ptr->link;
if(ptr==NULL)
printf("There are less than %d elements\n",pos);
else
{
tmp->link = ptr->link;
ptr->link = tmp;
}
return start;
}

Previous Next

Ads block