Linear Data Structure 521
The new node is created with the help of pointer temp. The m alloc () function allocates memory
of structure doubly size to pointer temp. The entered number is assigned to member variable
number. The next link field is assigned a NULL value using the statement temp->next=NULL.
The first four statements of the function form () are used for creation of the new node and the
remaining part is for adjusting link fields.
Consider the following statements.
1) temp->p=NULL: This statement is used to assign NULL value to the previous pointer. As it is
the first node and no previous link is available.
2) first->p=temp: The address of the newly created node temp is assigned to the previous pointer
of node first.
3) first=temp: When for the first time a node is created its address is stored in the pointer first.
The i f ( ), statement checks the contents of pointer first. Before creation of the first node, the
pointer first is NULL and hence i f () block is executed. For creating next nodes, the else block of
the i f () statement is executed where the next pointer is assigned the address of the next node and
the previous pointer holds the address of the previous node. For displaying the elements, the
technique is the same as explained in previous programs.
Insertion
Insertion of an element in the doubly linked list can be done in three ways.
1) Insertion at the beginning
2) Insertion at a specified location
3) Insertion at the end
Insertion at the beginning: The process involves creation of a new node, inputing data and adjusting
the pointers.
Header
3 &
Node 1
&
7
& & 8
X
Node 2
Node 3
4
New node
(a) Before insertion
I Header
4
X
3 &
Node 1 Node 2
&
7
&
&
8X
Node 3 Node 4
(b) After insertion
Fig. 14.24 Insertion of an element at the beginning
522 Programming and Data Structures
14.25 Write a program to insert an element at the beginning of the double linked list.
# include <std±o.h>
# include <conio.h>
# include <malloc.h>
# include <process.h>
strvct doubly
{
struct doubly *p;
int number;
struct doubly *next;
} *firs t ;
main ()
{
int form (in t);
int show(void);
void atbeg(int);
int option,nodes,n,j;
c lrs c r ();
while (1)
{
c lr s c r();
printf ("n 1. Create li s t " ) ;
printf ("
2. Display l i s t " ) ;
printf ("
3. Insert at Beginning");
printf ("
4. E xit");
printf ("
Enter Your option : ");
scanf ( "%d", Scoption);
switch (option)
{
case 1 :
printf ("
Enter number of nodes : " );
scanf ("%d", &nodes);
for (j=0;jcnodes;j++)
{
printf ("n Enter the element : ");
scemf ( "%d" , &n) ;
form(n) ;
}
break;
case 2 : show (); break;
Linear Data Structure 523
case 3 :
printf ("
Enter the element : " );
scanf ( "%d",&n);
atbeg(n); break;
case 4 : e x it (0);
}
}
form (int number)
{
struct doubly *q,*temp;
temp-(struct doubly*)malloc(sizeof(struct doubly));
temp->number^number;
t emp- >next =NULL;
i f (f ir s t — NULL)
{
temp- >p»NULL;
first->p*temp;
firstatemp;
}
else
{
q *firs t;
while (q->next1*0)
q»q->next;
q->next*temp;
temp->p«q;
>
return 0;
}
int show ()
{
struct doubly *q;
1C (first»N U L L)
{
printf ("List is Empty ");
return 0;
}
q*=f ir s t ;
printf ("n List is : n");
524 Programming and Data Structures
while (qI-NULL)
{
printf (" %d ■,q->number);
q«q->next/
}
printf ("n");
getchO ;
return 0;
}
void atbeg(int j)
{
struct doubly *temp;
tamp-(struct doubly*)m alloc(sizeof(struct doubly));
tezap- >p«lfULL;
temp->number«j;
temp->next-first/
first->p»temp;
first*temp;
}
OUTPUT;
1. Create list
2. Display list
3. Insert at Beginning
4. Exit
Enter Your option: 2
List is: 4 5 6
Enter Your option: 3
Enter the element: 2
Enter Your option: 2
List is: 2 4 5 6
Explanation This program is the same as the previous one. In addition here, the function at
beg () is defined. This function inserts the element at the beginning of the linked list. The technique
is common; the m alloc () function allocates memory to pointer temp. The entered number to
variable number and NULL value to previous pointer are assigned. The address of pointer first is
assigned to the next pointer of newly created node temp. This is because the temp will be the first
node and the previously first node will be the second node.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.