Question

A data structure can be defined as a mechanism for organizing the data a program stores in memory. An example of a data structure is a Linked List. Discuss how a linked list works and the methods of this data structure. (Please be super detailed and type the solution)

Answer 1

Linked List:

Linked list is a data structure which completely deals with dynamic memory allocation.It does not follow contiguous memory allocation like arrays.In order to use the memory space efficiently,Linked list has invented.

Generally linked lists are of two types:

1.Single linked list:

The basic structure in the linked list is node.

Data	Pointer to next node

The above figure shows the node structure in a linked list.

First field contains data of this node,and Second field contains Link to next node.

Single linked list supports one way traversal only i.e.,from either left to right or right to left.

Operations on single linked list:

1.We can create a node at beginning.

2.We can add a node at ending.

3.We can add a node at required location.

4.We can find length ;.e.,Number of nodes in the linked list.

5.We can display the data of the linked list.

6.We can Delete the node from beginning.

7.We can Delete the node from ending.

8.We can Delete the node from particular loction.

9.We can sort the data.

10.We can reverse the data linked list.

Program code for Single Linked List in 'C'(Integer data):

#include<stdio.h>
#include<conio.h>
void display();
int length();
void addatbegin();
void addatloc();
void addatend();
void deleteatbeg();
void deleteatend();
void deleteatloc();
void sort();
void reverse();
struct node
{
int data;
struct node *link;
};
struct node *root=NULL;
void main()
{
int n,d,i=1;
clrscr();
printf("This is a programme by PRAVEENA on all the operations of Single Linked List.");
while(i)
{
printf("\n\n\nSingle linked list menu:");
printf("\n1.Add at beginning");
printf("\n2.Add at ending");
printf("\n3.Add at particular location.");
printf("\n4.Delete at beginning.");
printf("\n5.Delete at ending.");
printf("\n6.Delete at particular location.");
printf("\n7.Display");
printf("\n8.Length");
printf("\n9.Sorting");
printf("\n10.Reverse");
printf("\n11.Exit");
printf("\nEnter your choice:");
scanf("%d",&n);
switch(n)
{
case 1:addatbegin();
       break;
case 2:addatend();
       break;
case 3:addatloc();
       break;
case 4:deleteatbeg();
       break;
case 5:deleteatend();
       break;
case 6:deleteatloc();
       break;
case 7:display();
       break;
case 8:d=length();
       printf("Length is:%d",d);
       break;
case 9:sort();
       break;
case 10:reverse();
       break;
case 11:i=0;
       break;
default:printf("wrong choice.");
}
}
getch();
}
void addatbegin()
{
struct node *temp;
temp=(struct node *)malloc(sizeof(struct node));
printf("Enter data:");
scanf("%d",&temp->data);
if(root==NULL)
{
root=temp;
temp->link=NULL;
}
else
{
struct node *p;
p=root;
root=temp;
root->link=p;
}
}
void display()
{
struct node *p;
p=root;
while(p!=NULL)
{
printf("%3d",p->data);
p=p->link;
}
}
int length()
{
struct node *p;
int c=0;
p=root;
while(p!=NULL)
{
p=p->link;
c++;
}
return c;
}
void addatend()
{
struct node *temp;
temp=(struct node *)malloc(sizeof(struct node));
printf("Enter data:");
scanf("%d",&temp->data);
temp->link=NULL;
if(root==NULL)
{
root=temp;
}
else
{
struct node *p;
p=root;
while(p->link!=NULL)
{
p=p->link;
}
p->link=temp;
}
}
void addatloc()
{
struct node *temp;
int loc,i=1;
temp=(struct node *)malloc(sizeof(struct node));
printf("Enter data:");
scanf("%d",&temp->data);
printf("Enter location:");
scanf("%d",&loc);
if(loc>length()+1)
{
printf("Invalid location:");
}
else
{
if(loc<length()+1)
{
struct node *p;
p=root;
while(i<loc-1)
{
p=p->link;
i++;
}
temp->link=p->link;
p->link=temp;
}
if(loc==1)
{
addatbegin();
}
if(loc==length()+1)
{
addatend();
}
}
}
void deleteatend()
{
struct node *p,*q;
p=root;
while(p->link!=NULL)
{
q=p;
p=p->link;
}
q->link=NULL;
p=NULL;
free(p);
}
void deleteatbeg()
{
struct node *temp;
temp=root;
root=temp->link;
free(temp);
}
void deleteatloc()
{
struct node *p,*q;
int loc,i=1;
printf("Enter location:");
scanf("%d",&loc);
if(loc>length())
{
printf("Invalid location.");
}
else
{
if(loc==1)
{
addatbegin();
}
else
{
p=root;
while(i<loc)
{
q=p;
p=p->link;
i++;
}
q->link=p->link;
p->link=NULL;
free(p);
}
}
}
void sort()
{
struct node *p,*q;
int temp=0;
if(root==NULL)
{
printf("There are no nodes to sort.");
}
else
{
printf("Elements after sorting is:");
for(p=root;p!=NULL;p=p->link)
{
for(q=p->link;q!=NULL;q=q->link)
{
if((p->data)>(q->data))
{
temp=p->data;
p->data=q->data;
q->data=temp;
}
}
}
display();
}
}
void reverse()
{
int i,j,k,l;
struct node *p,*q;
int temp=0;
q=root;
p=root;
l=length();
i=0;
j=l-1;
if(root==NULL)
{
printf("Linked list is empty.");
}
else
{
printf("Elements after reversing is:");
while(i<j)
{
k=0;
while(k<j)
{
q=q->link;
k++;
}
temp=p->data;
p->data=q->data;
q->data=temp;
i++;
j--;
p=p->link;
q=root;
}
display();
}
}

2.Double linked list:

The only difference between single and double linked list is we can traverse in both ways in Double linked list as it's node contains link to it's right and left nodes..

Link to left node

Data

Link to right node

It can perform all operations performed by single linked list.

Program code for Double linked list in 'C'(Integer data):

#include<stdio.h>
#include<conio.h>
void display();
int length();
void addatbegin();
void addatloc();
void addatend();
void deleteatbeg();
void deleteatend();
void deleteatloc();
struct node
{
int data;
struct node *rlink;
struct node *llink;
};
struct node *root=NULL;
void main()
{
int n,d,k=1;
clrscr();
printf("\n\nThis is a programme by PRAVEENA on Double Linked List\n\n");
while(k)
{
printf("\n\nDouble linked list menu:");
printf("\n1.Add at beginning");
printf("\n2.Add at ending");
printf("\n3.Add at particular location.");
printf("\n4.Delete at beginning.");
printf("\n5.Delete at ending.");
printf("\n6.Delete at particular location.");
printf("\n7.Display");
printf("\n8.Length");
printf("\n9.Exit");
printf("\nEnter your choice:");
scanf("%d",&n);
switch(n)
{
case 1:
addatbegin();
break;
case 2:
addatend();
break;
case 3:
addatloc();
break;
case 4:
deleteatbeg();
break;
case 5:
deleteatend();
break;
case 6:
deleteatloc();
break;
case 8 :
d=length();
printf("Length of the double linked list is:%d",d);
break;
case 7:
display();
break;
case 9:
k=0;
break;
default:
printf("wrong choice.");
}
}
getch();
}
void addatend()
{
struct node *temp;
temp=(struct node *)malloc(sizeof(struct node));
printf("Enter node data:");
scanf("%d",&temp->data);
if(root==NULL)
{
root=temp;
root->llink=NULL;
root->rlink=NULL;
}
else
{
struct node *p;
p=root;
while(p->rlink!=NULL)
{
p=p->rlink;
}
p->rlink=temp;
temp->llink=p;
temp->rlink=NULL;
}
}
void addatloc()
{
int loc,i=1;
printf("Enter location:");
scanf("%d",&loc);
if(loc>length()+1)
{
printf("Invalid location.(Enter the location which is less than %d).",length()+2);
}
if(loc<=length())
{
if(loc==1)
{
addatbegin();
}
else
{
struct node *temp,*p;
temp=(struct node *)malloc(sizeof(struct node));
printf("Enter data:");
scanf("%d",&temp->data);
p=root;
while(i<loc-1)
{
p=p->rlink;
i++;
}
temp->rlink=p->rlink;
p->rlink->llink=temp;
p->rlink=temp;
temp->llink=p;
}
}
if(loc==length()+1)
{
addatend();
}
}
void addatbegin()
{
struct node *temp;
temp=(struct node *)malloc(sizeof(struct node));
printf("Enter data:");
scanf("%d",&temp->data);
temp->llink=NULL;
if(root==NULL)
{
root=temp;
root->rlink=NULL;
}
else
{
temp->rlink=root;
root->llink=temp;
root=temp;
}
}
int length()
{
int c=0;
struct node *p;
p=root;
while(p!=NULL)
{
p=p->rlink;
c++;
}
return c;
}
void display()
{
struct node *p;
p=root;
if(root==NULL)
{
printf("Double Linked list is empty");
}
else
{
printf("Elements in the Double linked list are:");
while(p!=NULL)
{
printf("%3d",p->data);
p=p->rlink;
}
}
}
void deleteatend()
{
struct node *p,*q;
p=root;
while(p->rlink!=NULL)
{
q=p;
p=p->rlink;
}
printf("Deleted node data is:%d",p->data);
q->rlink=NULL;
p->llink=NULL;
free(p);
}
void deleteatbeg()
{
struct node *p;
p=root;
if(root==NULL)
{
printf("Sorry!!!There is no node to delete.");
}
else
{
printf("Deleted node data is:%d",p->data);
root=p->rlink;
root->llink=NULL;
free(p);
}
}
void deleteatloc()
{
struct node *p,*q;
int i=1,loc;
printf("Enter location:");
scanf("%d",&loc);
if(loc>length())
{
printf("Invalid node(Enter the number which is less than %d)",length()+1);
}
if(loc==length())
{
deleteatend();
}
if(loc<length())
{
if(loc==1)
{
deleteatbeg();
}
else
{
p=root;
while(i<loc)
{
q=p;
i++;
p=p->rlink;
}
printf("Deleted node data is:%d",p->data);
q->rlink=p->rlink;
p->rlink->llink=q;
}
}
}

3.Circular linked list:

In single and double linked lists,The last node address part contains null as there is no next node to point out.

But in circular linked list,The last node point out to the first node of linked list.

It can be implemented using either Single Linked list or double linked list.

It can perform all operations performed by Single and Double Linked lists.

Program code for Circular Linked List in 'c'(Using Single Linked List)(Integer data):

#include<stdio.h>
#include<conio.h>
void addatbeg();
void addatend();
void delatbeg();
void delatend();
int length();
void display();
struct node
{
int data;
struct node *link;
};
struct node *root=NULL;
void main()
{
int n,p,i=1;
clrscr();
while(i)
{
printf("\n\n\nThis is a programme by PRAVEENA on Circular linked List\n\n");
printf("Circular linked List Menu:");
printf("\n1.Add at beginning");
printf("\n2.Add at Ending");
printf("\n3.Delete at beginning");
printf("\n4.Delete at Ending");
printf("\n5.Length");
printf("\n6.Display");
printf("\n7.Exit");
printf("\nEnter your choice:");
scanf("%d",&n);
switch(n)
{
case 1:addatbeg();
       break;
case 2:addatend();
       break;
case 3:delatbeg();
       break;
case 4:delatend();
       break;
case 5:p=length();
       printf("Length of the CLL is:%d",p);
       break;
case 6:display();
       break;
case 7:i=0;
       break;
default:printf("Wrong choice.");
}
}
getch();
}
void addatbeg()
{
struct node *temp,*p;
temp=(struct node *)malloc(sizeof(struct node));
printf("Enter node data:");
scanf("%d",&temp->data);
if(root==NULL)
{
root=temp;
temp->link=root;
}
else
{
p=root;
while(p->link!=root)
{
p=p->link;
}
p->link=temp;
temp->link=root;
root=temp;
}
}
void addatend()
{
struct node *temp,*p;
temp=(struct node *)malloc(sizeof(struct node));
printf("Enter node data:");
scanf("%d",&temp->data);
if(root==NULL)
{
root=temp;
temp->link=root;
}
else
{
p=root;
while(p->link!=root)
{
p=p->link;
}
p->link=temp;
temp->link=root;
}
}
void delatbeg()
{
struct node *p,*q;
if(root==NULL)
{
printf("Circular linked List is empty.");
}
else
{
p=root;
while(p->link!=root)
{
p=p->link;
}
q=root;
printf("Deleted element is :%d",q->data);
root=q->link;
p->link=root;
q->link=NULL;
free(q);
}
}
void delatend()
{
struct node *p,*q;
if(root==NULL)
{
printf("Circular linked List is empty.");
}
else
{
p=root;
while(p->link!=root)
{
q=p;
p=p->link;
}
printf("Deleted element is:%d",p->data);
q->link=root;
p->link=NULL;
free(p);
}
}
int length()
{
struct node *p;
int c=0;
p=root;
if(root==NULL)
{
printf("Circular linked list is empty.");
return 0;
}
else
{
c++;
while(p->link!=root)
{
c++;
p=p->link;
}
return c;
}
}
void display()
{
struct node *p;
if(root==NULL)
{
printf("There is no node to display.");
}
else
{
p=root;
printf("Data in the Circular linked List are:");
printf("%3d",p->data);
p=p->link;
while(p!=root)
{
printf("%3d",p->data);
p=p->link;
}
}
}