- 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 Yorumlar