Linear Linked Lists - Introduction and Implementation

In a single linked list, every element is called a node. Every node consists of some data and the address of the next element. Clearly, single linked lists are better than arrays because insertion, deletion etc., operations are easy with single linked lists. The operations on single linked lists are insertion at beginning, insertion at end, insertion in the middle, deletion by position, deletion by value, display, sorting, reverse, merge etc,. The last node has some data and a NULL pointer because there is no node next to it.

C Program to implement Single Linked List

Program
#include<stdio.h>
#include<alloc.h>
#include<conio.h>
#include<stdlib.h>
{
int data;
}node;
node* create_list(int n)
{
node *p,*q,*r;
int i;
p=(node*)malloc(sizeof(node));
printf("\n Enter the %d values : ",n);
scanf("%d",&(p->data));
p->next=NULL;
q=p;
for(i=0;i<n-1;i++)
{
r=(node*)malloc(sizeof(node));
scanf("%d",&(r->data));
r->next=NULL;
q->next=r;
q=r;
}
return p;
}
node* insert_start(node *p)
{
node *s;
if(p!=NULL)
{
s=(node*)malloc(sizeof(node));
printf("\n Enter the value to insert at start : ");
scanf("%d",&(s->data));
s->next=p;
}
else
printf("\n Single Linked List is Empty");
return s;
}
node* insert_end(node *p)
{
node *m,*n;
n=p;
if(p==NULL)
printf("\n Single Linked List is Empty");
else
{
m=(node*)malloc(sizeof(node));
printf("\n Enter the value to insert at end : ");
scanf("%d",&(m->data));
m->next=NULL;
while(p->next!=NULL)
p=p->next;
p->next=m;
}
return n;
}
node* delete_node(node *p,int pos)
{
node *r1,*r2;
r1=p;
int check=1;
if(pos==1)
{
p=p->next;
r1->next=NULL;
free(r1);
return p;
}
else
{
r2->next=r1;
while(check<pos)
{
r1=r1->next;
r2=r2->next;
check++;
}
r2->next=r1->next;
r1->next=NULL;
free(r1);
return p;
}
}
void display(node *p)
{
node *t;
t=p;
printf("\n Single Linked List is : ");
while(p!=NULL)
{
printf("%d ",p->data);
p=p->next;
}
p=t;
}
void main()
{
clrscr();
char stay;
int choice,a,b;
node*list=NULL;
do
{
printf("\n 1.Create List");
printf("\n 2.Insert at Start");
printf("\n 3.Insert at End");
printf("\n 4.Delete Node");
printf("\n 5.Display");
printf("\n 6.Exit");
printf("\n Enter your choice : ");
scanf("%d",&choice);
switch(choice)
{
case 1:
printf("\n Enter number of values : ");
scanf("%d",&a);
list=create_list(a);
break;
case 2:
list=insert_start(list);
break;
case 3:
list=insert_end(list);
break;
case 4:
printf("\n Enter the position of the node to be deleted : ");
scanf("%d",&b);
list=delete_node(list,b);
break;
case 5:
display(list);
break;
case 6:
exit(0);
break;
default:
break;
}
printf("\n Do you want to continue? <y/n> : ");
stay=getche();
}
while(stay=='y'||stay=='Y');
}

Output
1.Create List
2.Insert at Start
3.Insert at End
4.Delete Node
5.Display
6.Exit
Enter number of values : 2
Enter the 2 values : 1 4
Do you want to continue? <y/n> : y

1.Create List
2.Insert at Start
3.Insert at End
4.Delete Node
5.Display
6.Exit
Enter the value to insert at start : 0
Do you want to continue? <y/n> : y

1.Create List
2.Insert at Start
3.Insert at End
4.Delete Node
5.Display
6.Exit
Enter the value to insert at end : 6
Do you want to continue? <y/n> : y

1.Create List
2.Insert at Start
3.Insert at End
4.Delete Node
5.Display
6.Exit
Enter the value to insert at end : 8
Do you want to continue? <y/n> : y

1.Create List
2.Insert at Start
3.Insert at End
4.Delete Node
5.Display
6.Exit
Enter the value to insert at end : 9
Do you want to continue? <y/n> : y

1.Create List
2.Insert at Start
3.Insert at End
4.Delete Node
5.Display
6.Exit
Single Linked List is : 0 1 4 6 8 9
Do you want to continue? <y/n> : y

1.Create List
2.Insert at Start
3.Insert at End
4.Delete Node
5.Display
6.Exit
Enter the position of the node to be deleted : 1
Do you want to continue? <y/n> : y

1.Create List
2.Insert at Start
3.Insert at End
4.Delete Node
5.Display
6.Exit
Enter the position of the node to be deleted : 2
Do you want to continue? <y/n> : y

1.Create List
2.Insert at Start
3.Insert at End
4.Delete Node
5.Display
6.Exit
Enter the position of the node to be deleted : 3
Do you want to continue? <y/n> : y

1.Create List
2.Insert at Start
3.Insert at End
4.Delete Node
5.Display
6.Exit
Enter the position of the node to be deleted : 2
Do you want to continue? <y/n> : y

1.Create List
2.Insert at Start
3.Insert at End
4.Delete Node
5.Display
6.Exit
Enter the position of the node to be deleted : 1
Do you want to continue? <y/n> : y

1.Create List
2.Insert at Start
3.Insert at End
4.Delete Node
5.Display
6.Exit
Enter the position of the node to be deleted : 1
Do you want to continue? <y/n> : y

1.Create List
2.Insert at Start
3.Insert at End
4.Delete Node
5.Display
6.Exit
Do you want to continue? <y/n> : y

1.Create List
2.Insert at Start
3.Insert at End
4.Delete Node
5.Display
6.Exit
Do you want to continue? <y/n> : y

1.Create List
2.Insert at Start
3.Insert at End
4.Delete Node
5.Display
6.Exit

A double linked list is similar to a single linked list. In a double linked list also, every element is called a node. But every node consists of some data and the addresses of the next and previous elements. Clearly, double linked lists are better than arrays because insertion, deletion etc., operations are easy with double linked lists. The operations on double linked lists are insertion at beginning, insertion at end, insertion in the middle, deletion by position, deletion by value, display, sorting, reverse, merge etc,. The first/last node have some data and a NULL pointer because there is no node previous/next to it.

C Program to implement Double Linked List

Program
#include<stdio.h>
#include<alloc.h>
#include<conio.h>
#include<stdlib.h>
{
int data;
}node;
node* create_list(int n)
{
node *p,*q,*r;
int i;
printf("\n Enter the %d values : ",n);
p=(node*)malloc(sizeof(node));
scanf("%d",&(p->data));
p->next=NULL;
p->prev=NULL;
q=p;
for(i=0;i<n-1;i++)
{
r=(node*)malloc(sizeof(node));
scanf("%d",&(r->data));
r->next=NULL;
q->next=r;
r->prev=q;
q=r;
}
return p;
}
node* insert_node(node *p)
{
node *q,*r;
int a,n,i;
r=p;
if(r==NULL)
{
printf("\n Double Linked List is Empty");
return p;
}
printf("\n Enter the value and position of the node to be inserted : ");
scanf("%d%d",&a,&n);
q=(node*)malloc(sizeof(node));
q->data=a;
q->next=NULL;
q->prev=NULL;
if(n==1)
{
q->next=r;
r->prev=q;
p=q;
return p;
}
for(i=0;i<n-2;i++)
r=r->next;
q->next=r->next;
r->next->prev=q;
q->prev=r;
r->next=q;
return p;
}
node* delete_node(node *p)
{
node *q;
int n,i;
q=p;
if(p==NULL)
{
printf("\n Double Linked List is Empty");
return q;
}
printf("\n Enter the position of the node to be deleted : ");
scanf("%d",&n);
if(n==1)
{
q=q->next;
q->prev=NULL;
p->next=NULL;
free(p);
return q;
}
q=p;
for(i=0;i<n-1;i++)
p=p->next;
p->prev->next=p->next;
p->next->prev=p->prev;
p->next=p->prev=NULL;
free(p);
return q;
}
void display(node *p)
{
node *q;
q=p;
if(q==NULL)
printf("\n Double Linked List is Empty");
else
{
printf("\n Double Linked List is : ");
while(q!=NULL)
{
printf("%d ",q->data);
q=q->next;
}
}
}
void main()
{
clrscr();
char stay;
int choice,n;
node*list=NULL;
do
{
printf("\n 1.Create List");
printf("\n 2.Insert Node");
printf("\n 3.Delete Node");
printf("\n 4.Display");
printf("\n 5.Exit");
printf("\n Enter your choice : ");
scanf("%d",&choice);
switch(choice)
{
case 1:
printf("\n Enter number of values : ");
scanf("%d",&n);
list=create_list(n);
break;
case 2:
list=insert_node(list);
break;
case 3:
list=delete_node(list);
break;
case 4:
display(list);
break;
case 5:
exit(0);
break;
default:
break;
}
printf("\n Do you want to continue? <y/n> : ");
stay=getche();
}
while(stay=='y'||stay=='Y');
}

Output
1.Create List
2.Insert Node
3.Delete Node
4.Display
5.Exit
Enter number of values : 3
Enter the 2 values : 2 3 7
Do you want to continue? <y/n> : y

1.Create List
2.Insert Node
3.Delete Node
4.Display
5.Exit
Enter the value and position of the node to be inserted : 5 3
Do you want to continue? <y/n> : y

1.Create List
2.Insert Node
3.Delete Node
4.Display
5.Exit
Double Linked List is : 2 3 5 7
Do you want to continue? <y/n> : y

1.Create List
2.Insert Node
3.Delete Node
4.Display
5.Exit
Enter the position of the node to be deleted : 1
Do you want to continue? <y/n> : y

1.Create List
2.Insert Node
3.Delete Node
4.Display
5.Exit
Enter the position of the node to be deleted : 1
Do you want to continue? <y/n> : y

1.Create List
2.Insert Node
3.Delete Node
4.Display
5.Exit
Enter the position of the node to be deleted : 1
Do you want to continue? <y/n> : y

1.Create List
2.Insert Node
3.Delete Node
4.Display
5.Exit
Enter the position of the node to be deleted : 1
Do you want to continue? <y/n> : y

1.Create List
2.Insert Node
3.Delete Node
4.Display
5.Exit
Enter the position of the node to be deleted : 1
Do you want to continue? <y/n> : y

1.Create List
2.Insert Node
3.Delete Node
4.Display
5.Exit
Do you want to continue? <y/n> : y

1.Create List
2.Insert Node
3.Delete Node
4.Display
5.Exit