A linked list is a data structure which consists of data record in a sequence such that each data record have a field of data as well as link reference to its connected node. It do not provide the random access to any of its member data as it is form of a indexing and the connected node is pre-defined.
There are mainly three kinds of linked lists:
- Singly linked list
- Doubly linked list
- Circular linked list.
Singly link list:
In the singly link list each node have two fields one for data and other is for link reference of the next node. The node have null only to the last node of the link field. This can be seen in the following picuture.
Fig: Singly Link List
Doubly link list:
In the doubly link list each node have three field two fields for link which is the reference to next and previous and one for data record. The node have null only to the first node of previous and last node at the next. This can be seen in the following picture.
Fig: Doubly Link List
Circular link list:
If talking about singly circular link list each node have two fields one for data record and other for link reference to the next node. The last node has link reference to the first node. There in no null present in the link of any node.
Fig: Singly circular link list
In this example you will see how to create a node and insert data record in singly link list.
Code:
# include <stdio.h> # include <stdlib.h> struct node { int data; struct node *link; }; struct node *insert(struct node *p , int num) { struct node *temp; if(p==NULL) { p=(struct node *)malloc(sizeof(struct node)); if(p==NULL) { printf("Error Occurred\n"); exit(0); } p-> data = num; p-> link = NULL; } else { temp = p; while (temp-> link != NULL) temp = temp-> link; temp-> link = (struct node *)malloc(sizeof(struct node)); if(temp -> link == NULL) { printf("Error Occurred\n"); exit(0); } temp = temp-> link; temp-> data = num; temp-> link = NULL; } return (p); } void printlist ( struct node *p ) { printf("The data values of your list are\n"); while (p!= NULL) { printf("%d\t",p-> data); p = p-> link; } } void main() { int n; int x; struct node *start = NULL ; printf("Enter number of nodes you want to create \n"); scanf("%d",&n); while ( n-- > 0 ) { printf( "Enter data values for each node\n"); scanf("%d",&x); start = insert ( start , x ); } printf("The created single link list is\n"); printlist ( start ); }
Output:
Doubly Linked List
This tutorial demonstrate how to implement doubly linked list.
Code:
#include <stdio.h>
#include <conio.h>
#include <malloc.h>
struct node
{
struct node *prev;
int info;
struct node *next;
}*start;
main()
{
int choice,n,m,po,i;
start=NULL;
while(1)
{
printf("1.Create List\n");
printf("2.Add at begining\n");
printf("3.Add after\n");
printf("4.Delete\n");
printf("5.Display\n");
printf("6.Count\n");
printf("7.Reverse\n");
printf("8.exit\n");
printf("Enter your choice : \n");
scanf("%d",&choice);
switch(choice)
{
case 1:
printf("How many nodes you want : ");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("Enter the element : ");
scanf("%d",&m);
create_list(m);
}
break;
case 2:
printf("Enter the element : ");
scanf("%d",&m);
addatbeg(m);
break;
case 3:
printf("Enter the element : ");
scanf("%d",&m);
printf("Enter the position after which this
element is inserted : ");
scanf("%d",&po);
addafter(m,po);
break;
case 4:
printf("Enter the element for deletion : ");
scanf("%d",&m);
del(m);
break;
case 5:
display();
break;
case 6:
count();
break;
case 7:
rev();
break;
case 8:
exit();
default:
printf("Wrong choice\n");
}/*End of switch*/
}/*End of while*/
}/*End of main()*/
create_list(int num)
{
struct node *q,*tmp;
tmp= malloc(sizeof(struct node));
tmp->info=num;
tmp->next=NULL;
if(start==NULL)
{
tmp->prev=NULL;
start->prev=tmp;
start=tmp;
}
else
{
q=start;
while(q->next!=NULL)
q=q->next;
q->next=tmp;
tmp->prev=q;
}
}/*End of create_list()*/
addatbeg(int num)
{
struct node *tmp;
tmp=malloc(sizeof(struct node));
tmp->prev=NULL;
tmp->info=num;
tmp->next=start;
start->prev=tmp;
start=tmp;
}/*End of addatbeg()*/
addafter(int num,int c)
{
struct node *tmp,*q;
int i;
q=start;
for(i=0;i<c-1;i++)
{
q=q->next;
if(q==NULL)
{
printf("There are less than %d
elements\n",c);
return;
}
}
tmp=malloc(sizeof(struct node) );
tmp->info=num;
q->next->prev=tmp;
tmp->next=q->next;
tmp->prev=q;
q->next=tmp;
}/*End of addafter() */
del(int num)
{
struct node *tmp,*q;
if(start->info==num)
{
tmp=start;
start=start->next; /*first element deleted*/
start->prev = NULL;
free(tmp);
return;
}
q=start;
while(q->next->next!=NULL)
{
if(q->next->info==num) /*Element deleted in
between*/
{
tmp=q->next;
q->next=tmp->next;
tmp->next->prev=q;
free(tmp);
return;
}
q=q->next;
}
if(q->next->info==num) /*last element deleted*/
{ tmp=q->next;
free(tmp);
q->next=NULL;
return;
}
printf("Element %d not found\n",num);
}/*End of del()*/
display()
{
struct node *q;
if(start==NULL)
{
printf("List is empty\n");
return;
}
q=start;
printf("List is :\n");
while(q!=NULL)
{
printf("%d ", q->info);
q=q->next;
}
printf("\n");
}/*End of display() */
count()
{ struct node *q=start;
int cnt=0;
while(q!=NULL)
{
q=q->next;
cnt++;
}
printf("Number of elements are %d\n",cnt);
}/*End of count()*/
rev()
{
struct node *p1,*p2;
p1=start;
p2=p1->next;
p1->next=NULL;
p1->prev=p2;
while(p2!=NULL)
{
p2->prev=p2->next;
p2->next=p1;
p1=p2;
p2=p2->prev; /*next of p2 changed to prev */
}
start=p1;
}/*End of rev()*/
===========================================
Code:
# include <stdio.h> # include <stdlib.h> struct dnode { int data; struct dnode *prev, *next; }; struct dnode *insert(struct dnode *p , struct dnode **q, int n) { struct dnode *temp; if(p==NULL) { p=(struct dnode *)malloc(sizeof(struct dnode)); if(p==NULL) { printf("Error Occurred\n"); exit(0); } p->data = n; p-> prev = p->next =NULL; *q =p; } else { temp = (struct dnode *)malloc(sizeof(struct dnode)); if(temp == NULL) { printf("Error Occurred\n"); exit(0); } temp->data = n; temp->prev = (*q); temp->next = NULL; (*q)->next = temp; (*q) = temp; } return (p); } void printnode( struct dnode *p ) { printf("All data of created list is\n"); while (p!= NULL) { printf("%d\t",p-> data); p = p->next; } } void main() { int n; int x; struct dnode *start = NULL ; struct dnode *end = NULL; printf("Enter the number of nodes to be created \n"); scanf("%d",&n); while ( n-- > 0 ) { printf( "Enter the data values for each node\n"); scanf("%d",&x); start = insert ( start , &end,x ); } printnode( start ); }
Output:
================================================================
======
Circular Linked List
Description:
In the circular linked list the link of lat node is connected to the first node.Code:
# include <stdio.h> # include <stdlib.h> struct node { int data; struct node *link; }; struct node *insert(struct node *p , int n) { struct node *temp; if(p==NULL) { p=(struct node *)malloc(sizeof(struct node)); if(p==NULL) { printf("Error Occurred\n"); exit(0); } p-> data = n; p-> link = p; } else { temp = p; while (temp-> link != p) temp = temp-> link; temp-> link = (struct node *)malloc(sizeof(struct node)); if(temp -> link == NULL) { printf("Error Occurred\n"); exit(0); } temp = temp-> link; temp-> data = n; temp-> link = p; } return (p); } void printlist ( struct node *p ) { struct node *temp; temp = p; printf("The data in the list are :\n"); if (p!= NULL) { do { printf("%d\t",temp-> data); temp=temp->link; }while(temp!=p); } else printf("The link is empty \n"); } void main() { int num; int value; struct node *start = NULL ; printf("Enter the number of nodes to be created \n"); scanf("%d",&num); while ( num-- > 0 ) { printf( "Enter the data to be placed in a node\n"); scanf("%d",&value); start = insert ( start , value ); } printlist ( start ); }
Output:
Count number of nodes
This tutorial demonstrate how to count the number of nodes present in the linked list.
Code:
# include <stdio.h> # include <stdlib.h> struct node { int data; struct node *link; }; struct node *insert(struct node * , int); int countnode(struct node*); void printlist (struct node *); struct node *insert(struct node *p , int n) { struct node *temp; if(p==NULL) { p=(struct node *)malloc(sizeof(struct node)); if(p==NULL) { printf("Error Occurred\n"); exit(0); } p-> data = n; p-> link = NULL; } else { temp = p; while (temp-> link!= NULL) temp = temp-> link; temp-> link = (struct node *)malloc(sizeof(struct node)); if(temp -> link == NULL) { printf("Error Occurred\n"); exit(0); } temp = temp-> link; temp-> data = n; temp-> link = NULL; } return (p); } void printlist ( struct node *p ) { printf("The data in the list are\n"); while (p!= NULL) { printf("%d\t",p-> data); p = p-> link; } } int countnode (struct node *p ) { int count=0; while (p != NULL) { count ++; p = p->link; } return(count); } void main() { int n; int x; struct node *start = NULL ; printf("Enter number of nodes to be created \n"); scanf("%d",&n); while ( n-- > 0 ) { printf( "Enter the data for node\n"); scanf("%d",&x); start = insert ( start ,x); } printlist ( start ); n = countnode(start); printf("\nThe number of nodes in a list are: %d\n",n); }
Output:
Split a list into two equal size list
Description:
In this example it has mainly three function one for inserting data into list another for printing the list and last one for split of list.
Code:
# include <stdio.h> # include <stdlib.h> struct node { int data; struct node *link; }; void splitlist(struct node *p, struct node **q, int n) { struct node *temp; int i =1; temp = p; while( i < n) { temp = temp->link; i++; } *q = temp->link; temp->link = p; temp = *q; while(temp->link != p) temp = temp ->link; temp->link = *q; } struct node *insertnode(struct node *p , int n) { struct node *temp; if(p==NULL) { p=(struct node *)malloc(sizeof(struct node)); if(p==NULL) { printf("Error\n"); exit(0); } p-> data = n; p-> link = p; } else { temp = p; while (temp-> link != p) temp = temp-> link; temp-> link =(struct node *)malloc(sizeof(struct node)); if(temp -> link == NULL) { printf("Error\n"); exit(0); } temp = temp-> link; temp-> data = n; temp-> link = p; } return (p); } void printlist ( struct node *p ) { struct node *temp; temp = p; printf("The data values in the list are\n"); if(p!= NULL) do { printf("%d\t",temp->data); temp=temp->link; } while (temp!= p); else printf("empty list\n"); } void main() { int n,num; int x; struct node *start1 = NULL ; struct node *start2=NULL; printf("Enter the number of node for each splited list \n"); scanf("%d",&n); num = n; n*=2; /* this is done to have data multiple of two so that it split into two equal parts. */ while ( n-- > 0 ) { printf( "\nEnter data to be placed in node\n"); scanf("%d",&x); start1 = insertnode ( start1 , x ); } printlist ( start1 ); splitlist(start1,&start2,num); printf("\nFirst list is:\n"); printlist(start1); printf("\nSecond list is:\n"); printlist(start2); }
No comments:
Post a Comment