Singly linked list in C
Insertion in Singly Linked List
A singly linked list in Data Structures consists of a node and a next pointer. Singly linked list can implemented in Java , C++ and C.
A node can be inserted in the linked list in three ways:-
- 1: Inserting node at the beginning of the linked list
- 2: Inserting node at the middle of the linked list (at any random position)
- 3: Inserting a node at the end of the linked list.
We will look to all 3 cases one by one :-
Question:-How a node is created ?
A node in the linked list can be created by using the malloc() function. We can insert the data to it. And also set the pointer of it to null so that it does not create the problem of dangling pointer.
Insertion at the beginning
A node is inserted before the current head node.
- Change the next pointer of new node to the head.
- After updating head pointer , the linked list looks like :-
Insertion at the end
In this case ,we need to modify the two next pointers (last node next pointer and new node next pointer).
- After modifying the next two pointers :-
Insertion at the middle
In this we will be given a position where we have to insert the linked list and also we need to modify the two ‘next’ pointers.
Consider , if we want to add a new node at position 3 , then we will traverse the linked list upto second position and modify the next pointers of the two nodes i.e new node points to the next node of the position where we want to add this node.
( Note :- As indexing starts from zero , so to insert at position 3 , we will run the loop till 2 position ).
- After modifying the pointers and insertion of new node.
Deletion in singly linked list :-
The same three operations are performed in the deletion of linked list:-
- Deletion from beginning
- Deletion from end
- Deleting an intermediate node.
Deleting the first node
It can be done in two steps :-
- Create a temp node which will point to the same node as that of head.
- Now, move the head pointer to the next node and free the memory for the temporary node( the node which temp pointer points or the node which is to be deleted ).
Deletion at the end
This operation is a bit trickier than removing the first node from linked list. It can be done in 3 steps:-
- Traverse the linked list while maintaining the address of the previous node At the end of the list , we have two pointers , one pointing to the tail node and other pointing to the before the tail node.
- Update the next pointer of previous node to null
- Now, dispose the tail node by free() method.
Deleting an intermediate node
In this case , the node which is to be removed is located between the two nodes. Such removal is done in two steps :-
- Maintain the previous node while traversing the linked list. Once the node which is to be deleted is found , changes the previous node next pointer to next pointer of the node to be deleted.
- Dispose the node by free() method.
C implementation for singly linked list
#include<stdio.h>
#include<stdlib.h>
typedef struct node1{
int info;
struct node1* next;
}node;
node *head=NULL;
node* create(int i){
node* tmp=(node*)malloc(sizeof(node));
tmp->info=i;
tmp->next=NULL;
printf("\nNode Cretaed...!!!!");
return tmp;
}
void addtohead(node *tmp){
system("cls");
node *t=head;
head=tmp;
tmp->next=t;
printf("\nNode inserted at the start...!!");
}
void addtoend(node *tmp){
system("cls");
if(head->next==NULL){
head->next=tmp;
}
else{
node *t=head;
for(;t->next!=NULL;t=t->next);
t->next=tmp;
}
printf("\nNode inserted at the end...!!!");
}
void atpos(node *newnode){
system("cls");
node *nextp,*curr,*tmp;
int i,pos;
printf("\nEnter the position at which you want to insert the node ?? ");
scanf("%d",&pos);
curr=head;
nextp=head->next;
for(i=1;i<pos-1;i++){
nextp=nextp->next;
curr=curr->next;
}
tmp=nextp;
curr->next=newnode;
newnode->next=tmp;
printf("\nNode inserted at position %d !!!",&pos);
}
void insert(){
int data,i,p,ch;
do{
system("cls");
printf("\nEnter the element you want to insert : ");
scanf("%d",&data);
node* tmp=create(data);
if(head==NULL){
head=tmp;
printf("\nList was Empty....Item inserted at first position !!!");
}
else{
printf("\nAt which position you want to insert the item ??? ");
printf("\n1.Begining");
printf("\n2.Ending");
printf("\n3.At specific position");
printf("\nEnter your choice : ");
scanf("%d",&p);
switch(p){
case 1: addtohead(tmp);
break;
case 2: addtoend(tmp);
break;
case 3: atpos(tmp);
break;
default: printf("\nWrong choice ...Enter again...!!!");
}
}
printf("\nDo you want to insert another node (1/0) ??");
scanf("%d",&ch);
}while(ch==1);
}
void deletefromhead(){
system("cls");
node *tmp=head;
head=head->next;
printf("\nNode deleted from head is : %d",tmp->info);
free(tmp);
}
void deletefromend(){
system("cls");
node *tmp=head;
for(;tmp->next->next!=NULL;tmp=tmp->next);
printf("\nNode deleted from end is : %d",tmp->info);
free(tmp->next);
tmp->next=NULL;
}
void deletepos(){
system("cls");
int pos,i,c;
node *prev,*curr;
prev=head;
curr=head->next;
//do{
printf("\nEnter the position of node you want to delete : ");
scanf("%d",&pos);
if(pos==1)
deletefromhead();
else{
for(i=1;i<pos-1;i++){
curr=curr->next;
prev=prev->next;
}
printf("\nNode deleted from %d is : %d",pos,curr->info);
prev->next=curr->next;
free(curr);
}
/* printf("\nDo you want to delete another node ?? ");
scanf("%d",&c);
}while(c==1);*/
}
void deleten(){
int p,ch;
do{
if(head==NULL){
printf("\nList is empty...!!!!");
}
else if(head->next==NULL){
printf("\nOnly one element in the list.. delelted node is : %d ",head->info);
free(head);
head=NULL; //PROBLEM
}
else{
system("cls");
printf("\nFrom which position you want to delete the node ?? ");
printf("\n1.Begining");
printf("\n2.Ending");
printf("\n3.At specific position");
printf("\nEnter your choice : ");
scanf("%d",&p);
switch(p){
case 1: deletefromhead();
break;
case 2: deletefromend();
break;
case 3: deletepos();
break;
default: printf("\nWrong choice ...Enter again...!!!");
}
}
printf("\nDo you want to delete another node (1/0)??");
scanf("%d",&ch);
}while(ch==1);
}
void display(){
system("cls");
node *tmp=head;
if(head==NULL)
printf("\nList is empty..!!!");
else{
for(;tmp!=NULL;tmp=tmp->next){
printf("-> %d",tmp->info);
}
}
}
int main(){
int c,ch;
do{
system("cls");
printf("\n-------LINKED LIST-------");
printf("\n1.INSERT INTO LIST");
printf("\n2.DELETE FROM LIST");
printf("\n3.DISPLAY THE LIST");
printf("\n4.EXIT");
printf("\nEnter your choice : ");
scanf("%d",&c);
switch(c){
case 1: insert();
break;
case 2: deleten();
break;
case 3: display();
break;
case 4: return(0);
}
printf("\nDo you want to perform any function again (1/0)???");
scanf("%d",&ch);
}while(ch==1);
return 0;
}
Doubly Linked List
Comments
No comment yet.