DSA LAB.
[Link]
Enrolment Number: 01-134132-130
Class: BS(CS), 4B
Course: Data Structures and Algorithms
[Link]@[Link]
April 22, 2015
Description of the program
Program that performs operations on doubley linked list.
The Steps Taken to Write the Program
deleteany function serches for the node to be deleted and deletes the node insertf
function inserts a new node before the first node in the list insertl inserts after
the last node showf displays list showb displays list in reverse order
The Difficulties Faced
There was difficulty in show forward.
4
1
11
13
15
The Code Section
# i n c l u d e <i o s t r e a m >
# i n c l u d e <c o n i o . h>
u s i n g namespace s t d ;
s t r u c t node
{
i n t data ;
node next , p r e v ;
};
class link
{
public :
node head , t a i l ;
link ()
{
head = NULL;
17
19
21
23
t a i l = NULL;
}
void i n s e r t f i r s t ( )
{
node temp ;
temp = new node ;
i f ( head == NULL)
{
c i n >> temp>data ;
temp>n e x t = NULL;
temp>p r e v = NULL;
head = temp ;
t a i l = temp ;
25
27
29
}
else
{
31
33
c i n >> temp>data ;
temp>n e x t = head ;
temp>p r e v = NULL;
head = temp ;
35
37
39
41
43
45
47
49
51
53
55
57
59
61
63
65
67
}
}
void i n s e r t l a s t ( )
{
node temp ;
temp = new node ;
i f ( t a i l != NULL)
{
c i n >> temp>data ;
temp>n e x t = NULL;
temp>p r e v = t a i l ;
t a i l >n e x t = temp ;
t a i l = temp ;
}
}
v o i d i n s e r t a f t e r ( i n t s e a r c h , i n t data )
{
node noder ;
noder = new node ;
node temp ;
noder>data = data ;
f o r ( node temp1 = head ; temp1 != NULL; temp1 = temp1>n e x t )
{
i f ( temp1>data == s e a r c h )
{
temp = temp1>n e x t ;
noder>n e x t = temp ;
temp>p r e v = noder ;
temp1>n e x t = noder ;
noder>p r e v = temp1 ;
}
69
71
73
75
void removef ( )
{
77
node temp = head ;
79
81
83
85
87
89
91
93
95
97
99
101
103
105
107
109
111
113
115
117
119
121
123
i f ( head != NULL)
{
head = head>n e x t ;
head>p r e v = NULL;
d e l e t e temp ;
}
}
void removel ( )
{
node temp ;
temp = t a i l ;
i f ( t a i l != NULL)
{
t a i l = t a i l >p r e v ;
t a i l >n e x t = NULL;
d e l e t e temp ;
}
}
void deleteany ( ) {
node temp = head ;
c o u t << Enter a number : ;
i n t num ;
c i n >> num ;
bool f l a g = f a l s e ;
w h i l e ( temp != NULL && f l a g == f a l s e ) {
w h i l e ( temp>next>data == num) {
node c u r r = temp ;
node d e l = c u r r >n e x t ;
c u r r >n e x t = temp>next>n e x t ;
c u r r >p r e v = temp>p r e v ;
free ( del ) ;
f l a g = true ;
}
temp = temp>n e x t ;
}
}
v o i d showf ( )
{
node temp ;
temp = head ;
w h i l e ( temp != NULL)
{
c o u t << temp>data << e n d l ;
temp = temp>n e x t ;
125
127
129
}
}
v o i d showb ( )
{
node temp ;
temp = t a i l ;
w h i l e ( temp != NULL)
{
c o u t << temp>data << e n d l ;
temp = temp>p r e v ;
131
133
135
137
}
139
141
143
145
147
149
151
153
155
157
159
161
163
165
167
169
171
173
175
177
179
181
183
185
};
v o i d main ( )
{
l i n k a1 ;
int a ;
do
{
c o u t << 1 ) i n s e r t f i r s t \n ;
c o u t << 2 ) i n s e r t l a s t \n ;
c o u t << 3 ) remove f i r s t \n ;
c o u t << 4 ) remove l a s t \n ;
c o u t << 5 ) show backward \n ;
c o u t << 6 ) show f o r w a r d \ n7 ) i n s e r t a f t e r \ n8 ) remove any node \n
;
c o u t << ENTER CHOICE : ;
c i n >> a ;
switch ( a )
{
case 1:
a1 . i n s e r t f i r s t ( ) ;
system ( c l s ) ;
break ;
case 2:
a1 . i n s e r t l a s t ( ) ;
system ( c l s ) ;
break ;
case 3:
a1 . r e m o v e f ( ) ;
system ( c l s ) ;
break ;
case 4:
a1 . r e m o v e l ( ) ;
system ( c l s ) ;
break ;
case 5:
a1 . showb ( ) ;
break ;
case 6:
a1 . showf ( ) ;
break ;
case 7:
i n t n , m;
c o u t << SEARCH : ;
c i n >> n ;
c o u t << ENTER VALUE : ;
c i n >> m;
a1 . i n s e r t a f t e r ( n , m) ;
break ;
case 8:
a1 . d e l e t e a n y ( ) ;
break ;
default :
c o u t << ENTER VALID dataBER\n ;
}
187
189
191
193
} w h i l e ( a != 9 ) ;
getch () ;
195
197
