- Linked lists are among the simplest and most common data structures.
- It is used to implement the several other common types (Abstract data types,stacks,Queues,Associative arrays and S-expressions).
- Mainly they are two types of linked list singly linked list and doubly linked list
Difference between singly linked list and doubly linked list
Single
linked list
|
Double
linked list
|
It has tail only
|
It has head and tail
|
It has next node only
|
It has next and
previous only
|
Singly linked lists contain nodes which have
a data field as well as a 'next' field, which points to the next node in line
of nodes. Operations that can be performed on singly linked lists include
insertion, deletion and traversal.
|
In a 'doubly linked list', each node
contains, besides the next-node link, a second link field pointing to the
'previous' node in the sequence. The two links may be called 'forward('s')
and 'backwards', or 'next' and 'prev'('previous').
|
Singly linked list
A singly linked list whose nodes contain two
fields: an integer value and a link to the next node
Doubly
linked list
A doubly linked list whose nodes contain three fields: an
integer value, the link forward to the next node, and the link backward to the
previous node
Coding for singly linked list :
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
struct NODE
{
int data;
struct NODE *next;
}*start = NULL;
struct NODE *newNode = NULL,*currentNode = NULL;
void createNode();
void displayList();
void searchNode();
int lengthList();
void insertNode();
void deleteNode();
int main()
{
int choice,len;
char wish;
do{
printf("\n\tSINGLY
LINKED LIST OPERATIONS\n");
printf("\t------------------------------------- \n");
printf("\n\t
1.CreatNode \n\t 2.Display List \n\t
3.Search Node \n\t
4.Length");
printf("\n\t
5.Insert \n\t 6.Delete Node \n\t
7.Exit");
printf("\n Enter
your choice: ");
scanf("%d",&choice);
switch(choice)
{
case 1:
createNode();
break;
case 2:
displayList();
break;
case 3:
searchNode();
break;
case 4:
len =
lengthList();
printf("\n
Lenght of the list is: %d",len);
break;
case 5:
insertNode();
break;
case 6:
deleteNode();
break;
case 7:
exit(0);
default:
printf("\n
Enter correct choice....");
}
printf("\n Do you
want to continue the list
operations?
(y/n)");
scanf("%c%c",&wish,&wish);
}while(wish=='y');
return 0;
}
void createNode()
{
char ch;
do
{
newNode = (struct NODE
*)malloc(sizeof(struct NODE));
printf("\n Enter
the data: ");
scanf("%d",
&newNode->data);
newNode->next = NULL;
if(start==NULL)
{
start = newNode;
currentNode = newNode;
}
else
{
currentNode->next
= newNode;
currentNode =
newNode;
}
printf("\nSuccessfully
Nodes are created and linked
together
properly..");
printf("\nContinue
to create Node:(y/n)");
scanf("%c%c",&ch,&ch);
}while(ch=='y');
}
void displayList()
{
struct NODE *temp = NULL;
temp = start;
printf("\n\n");
if(start == NULL)
{
printf("\n There is
no nodes are available to
print..\n");
exit(0);
}
else
{
while(temp != NULL)
{
printf("%5d",temp->data);
temp = temp->next;
}
}
}
void searchNode()
{
int no,flag=0;
char ch;
struct NODE *temp = NULL;
do
{
printf("\n Enter
the Data to find:");
scanf("%d",&no);
flag=0;
temp = start;
while(temp != NULL)
{
if(no ==
temp->data)
{
printf("%d
is present at list..",temp
->data);
flag=1;
break;
}
temp =
temp->next;
}
if(flag==0)
{
printf("\n Your
search element is not present in
list..");
}
printf("\n Want to
Search again? (y/n)");
scanf("%c%c",&ch,&ch);
}while(ch=='y');
}
int lengthList()
{
int count=0;
struct NODE *temp = NULL;
temp = start;
while(temp != NULL)
{
count++;
temp = temp -> next;
}
return count;
}
void insertNode()
{
int pos,len;
struct NODE *temp = NULL;
len = lengthList();
printf("\n Enter the
position to add: ");
scanf("%d",&pos);
if(pos>0 &&
pos<= len+1)
{
newNode = (struct NODE
*)malloc(sizeof(struct NODE));
printf("\n Enter
the data:");
scanf("%d",&newNode->data);
newNode->next = NULL;
if(pos==1)
{
newNode->next = start;
start = newNode;
}
else
{
temp = start;
while(pos > 2)
{
temp =
temp->next;
pos--;
}
newNode->next =
temp->next;
temp->next =
newNode;
}
}
else
printf("\n
Given position is wrong..");
}
void deleteNode()
{
int pos,len;
struct NODE *temp = start;
len = lengthList();
printf("\n Enter the
position to delete: ");
scanf("%d",&pos);
if(pos>0 &&
pos<=len)
{
if(pos==1)
{
start =
start->next;
free(temp);
}
else
{
while(pos > 2)
{
temp =
temp->next;
pos--;
}
newNode =
temp->next;
temp->next =
newNode->next;
free(newNode);
}
}
else
{
printf("\n Invalid
Position...");
}
}
OUTPUT:
SINGLY LINKED LIST OPERATIONS
-----------------------------------------
1.CreatNode
2.Display List
3.Search Node
4.Length
5.Insert
6.Delete Node
7.Exit
Enter your choice: 1
Enter the data: 12
Successfully Nodes are
created and linked together properly..
Continue to create
Node:(y/n)
Enter the data: 1
Successfully Nodes are
created and linked together properly..
Continue to create
Node:(y/n)
Enter the data: 6
Successfully Nodes are
created and linked together properly..
Continue to create
Node:(y/n)
Do you want to
continue the list operations? (y/n)
Coding for Doubly Linked list :
#include<stdio.h>
struct NODE
{
int data;
struct NODE *prev;
struct NODE *next;
}*start = NULL;
struct NODE *newNode = NULL,*currentNode = NULL;
void createNode()
{
char ch;
struct NODE *temp = NULL;
do
{
newNode = (struct NODE
*)malloc(sizeof(struct NODE));
printf("\n Enter
the data: ");
scanf("%d",
&newNode->data);
newNode->next = NULL;
newNode->prev = NULL;
if(start==NULL)
{
start = newNode;
currentNode=newNode;
}
else
{
currentNode->next=newNode;
newNode->prev=currentNode;
currentNode=newNode;
}
printf("\nSuccessfully
Nodes are created and linked together properly..");
printf("\nContinue
to create Node:(y/n)");
scanf("%c%c",&ch,&ch);
}while(ch=='y');
}
void displayList()
{
struct NODE *temp = NULL;
temp = start;
printf("\n\n");
if(start == NULL)
{
printf("\n There is
no nodes are available to print..\n");
exit(0);
}
else
{
while(temp != NULL)
{
printf("%5d",temp->data);
temp =
temp->next;
}
}
}
void searchNode()
{
int no,flag=0;
char ch;
struct NODE *temp = NULL;
do
{
printf("\n Enter
the Data to find:");
scanf("%d",&no);
flag=0;
temp = start;
while(temp != NULL)
{
if(no ==
temp->data)
{
printf("%d
is present at list..",temp->data);
flag=1;
break;
}
temp =
temp->next;
}
if(flag==0)
{
printf("\n Your
search element is not present in list..");
}
printf("\n Want to
Search again? (y/n)");
scanf("%c%c",&ch,&ch);
}while(ch=='y');
}
int lengthList()
{
int count=0;
struct NODE *temp = NULL;
temp = start;
while(temp != NULL)
{
count++;
temp = temp -> next;
}
displayList();
return count;
}
void insertNode()
{
int pos,len;
struct NODE *temp = NULL;
len = lengthList();
printf("\n Enter the
position to add: ");
scanf("%d",&pos);
if(pos>0 &&
pos<= len+1)
{
newNode = (struct NODE
*)malloc(sizeof(struct NODE));
printf("\n Enter
the data:");
scanf("%d",&newNode->data);
newNode->prev = NULL;
newNode->next = NULL;
if(pos==1)
{
newNode->next =
start;
start->prev =
newNode;
start = newNode;
}
else
{
temp = start;
while(pos > 2)
{
temp =
temp->next;
pos--;
}
if(temp->next!=NULL)
temp->next->prev = newNode;
newNode->next =
temp->next;
newNode->prev =
temp;
temp->next =
newNode;
}
}
else
printf("\n
Given position is wrong..");
}
void deleteNode()
{
int pos,len;
struct NODE *temp = start;
len = lengthList();
printf("\n Enter the
position to delete: ");
scanf("%d",&pos);
if(pos>0 &&
pos<=len)
{
if(pos==1)
{
start =
start->next;
start->prev =
NULL;
free(temp);
}
else
{
while(pos > 2)
{
temp =
temp->next;
pos--;
}
newNode =
temp->next;
temp->next =
newNode->next;
if(newNode->next!=NULL)
newNode->next->prev
= temp;
free(newNode);
}
}
else
{
printf("\n Invalid
Position to Delete...");
}
}
int main()
{
int choice,len;
char wish;
do{
printf("\n\tDOUBLY
LINKED LIST OPERATIONS\n");
printf("\t-----------------------------------------\n");
printf("\n\t
1.CreatNode \n\t 2.Display List \n\t 3.Search Node \n\t 4.Length");
printf("\n\t
5.Insert \n\t 6.Delete Node \n\t 7.Exit");
printf("\n Enter
your choice: ");
scanf("%d",&choice);
switch(choice)
{
case 1:
createNode();
break;
case 2:
displayList();
break;
case 3:
searchNode();
break;
case 4:
len =
lengthList();
printf("\n
Lenght of the list is: %d",len);
break;
case 5:
insertNode();
break;
case 6:
deleteNode();
break;
case 7:
exit(0);
default:
printf("\n
Enter correct choice....");
}
printf("\n Do you
want to continue the list operations? (y/n)");
scanf("%c%c",&wish,&wish);
}while(wish=='y');
return 0;
}
OUTPUT:
DOUBLY LINKED LIST
OPERATIONS
-----------------------------------------
1.CreatNode
2.Display List
3.Search Node
4.Length
5.Insert
6.Delete Node
7.Exit
Enter your choice: 1
Enter the data: 12
Successfully Nodes are created and linked together properly..
Continue to create Node:(y/n)
Enter the data: 43
Successfully Nodes are created and linked together properly..
Continue to create Node:(y/n)
Enter the data: 78
0 comments:
Post a Comment