Linear Data Structure 517
void show()
{
printf (”n Linked lis t elements are : " );
while (header I«NULL)
{
printf (" %d ", header->num);
header-header- >next;
}
>
OUTPUT;
Operation creation:
Enter number. 12 3 4 5 0
Linked list elements are: 1 2 3 4 5
After deletion:
Linked list elements are: 2 3 4 5
Linked list elements are: 3 4 5
Linked list elements are: 4 5
Explanation In the above program the f orm () and show () operations are the same as
implemented in the last programs. In addition, rem () operation is carried out. In the rem () function
the new object *s is declared. The memory allocated to pointer header is assigned to pointer *s. The
f ree () function deallocates the memory allocated to s. The address of the second node is assigned
to pointer header. The pointer header points to the first node. In this way, when nodes are removed,
memory is released.
14.22 DOUBLE LINKED LIST
In this type of linked list the data structure holds two pointer fields. In the single linked list, address
of only the next element is pointed. In addition, in a double linked list addresses of next as well as
preceding elements are linked with the current node. The single linked list has some limitations that
can be overcome by the double linked list. Consider a case in which the access pointer is in between
the linked list and we need to access the earlier element. Due to lack of previous item link, we cannot
transverse the list in reverse direction and hence we have no option except to transverse the list from
the beginning.
In a double linked list, each node has two link fields and they hold the addresses of the previous
and next nodes which enables us to access not only the next element but also the previous element.
Start
y
r
.......
I
5 I & • &
7
&
00
4
/
I
---
I 1 /
j :
Previous
Next
Fig. 14.23 Double linked list
518 Programming and Data Structures
The structure of this type of link would be as follows,
struct node
int num;
struct node *next;
struct node *previous;
}
In the above structure, the integer num is used to store data values. The pointer *next holds the
link of the next node and the pointer ^previous holds the link of the previous node.
The pointer ^previous of the first node is NULL because it has no previous element. The pointer
*next of last element of the node will be NULL since the linked list ends here. The following
program explains the creation and displays the operation of a doubly linked list.
14.24 Write a program to create a double linked list and display its elements.
# include <stdio.h>
# include <conio.h>
# include <malloc.h>
struct doubly
{
struct doubly *p;
int number;
struct doubly +next;
} *firs t;
main ()
{
int form (int);
int show(void);
int option, nodes, n, j;
c lr s c r ();
firs t NULL;
while (1)
{
c lrs c r ();
printf ("n 1. Create l i s t " );
printf ("
2. Display l i s t " ) ;
prin tf ("
3. Exit");
prin tf ("
Enter Your option : ");
scanf ( "%d",fcoption);
switch (option)
Linear Data Structure 519
{
case 1 :
prin tf ("
Enter number of nodes :
scanf ( ”%d”,fibnodes);
■) »
for (j«0;j<nodes;j++)
{
printf ("
Enter the element : ■);
scanf ( a%da,&n);
form(n) ;
}
break;
case 2 : show (); break;
case 3 :
>
}
}
form (int number)
{
struct doubly *q,*temp;
temp*(struct doubly*)m alloc(sizeof(struct
temp->number-number;
temp->next-NULL;
doubly));
i f (f i r s t — NULL)
{
temp - >p=NULL;
first->p*temp;
first*temp;
}
else
{
q «f ir s t ;
while (q->nextl*0)
q«*q->next;
q->next*temp;
temp->p«q;
}
return 0;
}
int show ()
{
struct doubly *q;
if (first=-NULIi)
520 Programming and Data Structures
{
prin tf ("List is Bmpty ■);
return 0;
}
q -firs t;
printf ("
List is : n ");
while (ql-NULL)
{
printf ( ” %d ■,q->number);
q*q->next;
>
printf ("n");
getch {);
return 0;
}
OUTPUT;
1. Create list
2. Display list
3. Exit
Enter Your option: 1
Enter number of nodes: 3
Enter the element: 12 3
1. Create list
2. Display list
3. Exit
Enter Your option: 2
List is:
1 5 9
Explanation In the above program structure doubly is dedared. The structure contains two pointer
variables *p and *next and single integer data element number. The variable first is pointer to
structure doubly. The choice entered by the user is passed to sw itch () case structure and the
corresponding function is executed. There are two functions: form () used to create the list and
show () to display the elements.
The user is prompted to enter the number of nodes to be created and the integer. The entered
value is passed to function form (). In this function two more pointers to structures *q and *temp
are declared.
temp=(struct doubly*)malloc(sizeof(struct doubly));
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.