Linear Linked Lists - Introduction and Implementation


Linear linked lists may be single linked lists or double linked lists. Read this article for a brief introduction of linear linked lists and the C programs to implement single linked lists and double linked lists.

Single Linked List


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>
typedef struct slinkedlist
{
int data;
struct slinkedlist* next;
}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\n Single Linked List Operations");
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:
printf("\n Your choice is invalid");
break;
}
printf("\n Do you want to continue? <y/n> : ");
stay=getche();
}
while(stay=='y'||stay=='Y');
}

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

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

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

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

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

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

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

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

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

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

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

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

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

Single Linked List Operations
1.Create List
2.Insert at Start
3.Insert at End
4.Delete Node
5.Display
6.Exit
Enter your choice : 7
Your choice is invalid
Do you want to continue? <y/n> : y

Single Linked List Operations
1.Create List
2.Insert at Start
3.Insert at End
4.Delete Node
5.Display
6.Exit
Enter your choice : 6

Double Linked List


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>
typedef struct dlinkedlist
{
int data;
struct dlinkedlist *next,*prev;
}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\n Double Linked List Operations");
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:
printf("\n Your choice is invalid");
break;
}
printf("\n Do you want to continue? <y/n> : ");
stay=getche();
}
while(stay=='y'||stay=='Y');
}

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

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

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

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

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

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

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

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

Double Linked List Operations
1.Create List
2.Insert Node
3.Delete Node
4.Display
5.Exit
Enter your choice : 6
Your choice is invalid
Do you want to continue? <y/n> : y

Double Linked List Operations
1.Create List
2.Insert Node
3.Delete Node
4.Display
5.Exit
Enter your choice : 5

Single linked lists and double linked lists are collectively called as linear linked lists.


Comments

No responses found. Be the first to comment...


  • Do not include your name, "with regards" etc in the comment. Write detailed comment, relevant to the topic.
  • No HTML formatting and links to other web sites are allowed.
  • This is a strictly moderated site. Absolutely no spam allowed.
  • Name:
    Email: