Unit 3

LINKED LISTS

Linked lists and array s are simila r since they both stor e collection s of
dat a. One way to think abou t linked lists is to look at how arr ay s work
and think abou t alter n a t e app ro a c h e s .

Array is the most common data structure used to store collections of elements. Arrays are convenient
to declare and provide the easy syntax to access any element by its index number. Once the array is
set up, access to any element is convenient and fast.

The dis a d v a n t a g e s of array s are:

 The size of the arr ay is fixed. Most often this size is specified at
compile time. This make s the prog r a m m e r s to allocat e arr ays ,
which see m s "larg e enou g h" than requi r e d .

 Inse r ti n g new elem e n t s at the front is pote n ti ally expe n sive

bec a u s e existing elem e n t s nee d to be shifted over to make
room.

 Deleting an elem e n t from an arr ay is not possible.

Linked lists have their own strengths and weaknesses, but they happen to be strong where arrays are
weak. Generally array's allocates the memory for all its elements in one block whereas linked lists use
an entirely different strategy.

Linked lists allocat e mem o ry for each elem e n t sep a r a t e ly and only when
nec es s a r y.

Her e is a quick review of the ter mi nology and rules of point e r s . The
linked list code will dep e n d on the following functions :

mall o c ( ) is a syste m function which allocat e s a block of memo ry in the

"hea p" and retu r n s a point e r to the new block. The prototy p e of malloc()
and othe r heap functions are in stdlib.h. malloc() retu r n s NULL if it
canno t fulfill the requ e s t . It is define d by:

void *malloc (number_of_bytes)

Since a void * is returned the C standard states that this pointer can be converted to any type. For
example,

char *cp;
cp = (char *) malloc (100);

Attempts to get 100 bytes and assigns the starting address to cp. We can also use the sizeof()
function to specify the number of bytes. For example,

int *ip;
ip = (int *) malloc (100*sizeof(int));

59
free() is the opposite of malloc(), which de-allocates memory. The argument to free() is a pointer to a
block of memory in the heap — a pointer which was obtained by a malloc() function. The syntax is:

free (ptr);

The advantage of free() is simply memory management when we no longer need a block.

6. 1. Link e d List:

A linked list is a non-sequential collection of data items. It is a dynamic data structure. For every data
item in a linked list, there is an associated pointer that would give the memory location of the next
data item in the linked list.

The data items in the linked list are not in consecutive memory locations. They may be anywhere, but
the accessing of these data items is easier as each data item contains the address of the next data
item.

Advan t a g e s of link e d list s :

Linked lists have many adva n t a g e s . Some of the very impor t a n t

adva n t a g e s are:

1. Linked lists are dyna mic dat a struc t u r e s . i.e., they can grow or
shrink durin g the executio n of a prog r a m .

2. Linked lists have efficient memo ry utilization. Her e, mem o ry is

not pre- alloca t e d . Memo ry is alloca t e d whe n ev e r it is req ui r e d
and it is de- allocat e d (rem ove d) when it is no longe r nee d e d .

3. Inse r tio n and Deletion s are easie r and efficient. Linked lists
provide flexibility in inse rtin g a dat a item at a specified position
and deletion of the dat a item from the given position.

4. Many complex applica tio n s can be easily carri e d out with linked
lists.

Dis a d v a n t a g e s of link e d list s:

1. It cons u m e s more spac e beca u s e every node req uir e s a

addition al point e r to stor e addr e s s of the next node.

2. Sear c hi n g a partic ul a r elem e n t in list is difficult and also time

cons u m i n g .

Type s of Link e d List s:

Basically we can put linked lists into the following four item s:

1. Single Linke d List.

2. Double Linke d List.

60
3. Circul a r Linke d List.
4. Circul a r Double Linked List.
A single linked list is one in which all node s are linked toget h e r in som e
sequ e n ti al man n e r. Henc e, it is also called as linea r linked list.

A doubl e linked list is one in which all node s are linked toget h e r by
multiple links which helps in acce s si n g both the succ e s s o r node (next
node) and pred e c e s s o r node (previous node) from any arbit r a r y node
within the list. Ther efo r e eac h node in a double linked list has two link
fields (point e r s ) to point to the left node (previou s) and the right node
(next). This helps to trave r s e in forwa r d direc tio n and backw a r d
direc tio n.

A circula r linke d list is one, which has no beginni n g and no end. A single
linked list can be mad e a circul a r linked list by simply storin g add r e s s of
the very first node in the link field of the last node.

A circula r double linked list is one, which has both the succ e s s o r point e r
and pred e c e s s o r pointe r in the circula r man n e r .

Com p a r i s o n betw e e n array and lin k e d list:

ARRAY LINKED LIST

Size of an array is fixed Size of a list is not fixed
Memo ry is allocat e d from stack Memo ry is allocat e d from heap
It is nece s s a r y to specify the It is not nece s s a r y to specify the
num b e r of elem e n t s during num b e r of elem e n t s during
decla r a ti o n (i.e., during compile decla r a ti o n (i.e., memo ry is
time). alloca t e d durin g run time).
It occupie s less mem o ry than a
linked list for the sam e num b e r It occupie s more memo ry.
of elem e n t s .
Inse r ti n g new elem e n t s at the
front is pote n ti ally expe n sive Inse r ti n g a new elem e n t at any
bec a u s e existing elem e n t s nee d position can be carrie d out easily.
to be shifted over to make room.
Deleting an elem e n t from an
Deleting an elem e n t is possible.
arr ay is not possible.

Appli c a t i o n s of link e d list:

1. Linked lists are used to rep r e s e n t and manip ul a t e polyno mi al.

Polyno mi als are expr e s s io n cont ai ni n g ter m s with non zero
coefficien t and expon e n t s . For exam pl e:

P(x) = a 0 Xn + a 1 Xn- 1 + …… + a n- 1 X + a n

61
2. Repr e s e n t very larg e num b e r s and oper a tio n s of the larg e num b e r
such as addition, multiplica tio n and division.

3. Linked lists are to imple m e n t stack, que u e , tree s and gra p h s .

4. Imple m e n t the symbol table in compiler const r u c t io n

6. 2. Sin g l e Link e d List:

A linked list allocates space for each element separately in its own block of memory called a "node".
The list gets an overall structure by using pointers to connect all its nodes together like the links in a
chain.

Each node cont ai n s two fields; a "dat a" field to stor e what ev e r elem e n t ,
and a "next" field which is a point e r used to link to the next node.

Each node is alloca t e d in the hea p using malloc(), so the node mem o ry
contin u e s to exist until it is explicitly de- allocat e d using free(). The front
of the list is a point e r to the “star t ” node. A single linked list is show n in
figure 6.2.1.

S TAC K H EAP

100

st a rt
10 200 20 300 30 400 40 X
T h e st art 100 200 300 400
p o int er
h o ld s t h e Ea c h n o d e St o r e s t h e n e xt T h e n e xt f i e l d of
a d dr e s s of st or e s t h e d at a. n o d e a d dr e s s. t h e l a st n o d e i s
t h e f ir s t N ULL.
n o d e of t h e
l i st .

Fi g u r e 6 . 2 . 1 . S i n g l e L i n k e d L i s t

The beginni n g of the linked list is store d in a " start " point e r which points
to the first node. The first node cont ai n s a point e r to the secon d node.
The secon d node cont ai n s a point e r to the third node, ... and so on. The
last node in the list has its next field set to NULL to mark the end of the
list. Code can acce s s any node in the list by sta rti n g at the start and
following the next point e r s .

The start point e r is an ordin a ry local point e r variable, so it is draw n

sepa r a t e ly on the left top to show that it is in the stack. The list node s
are draw n on the right to show that they are allocat e d in the hea p.

Impl e m e n t a t i o n of Sin g l e Link e d List:

62
Before writing the code to build the above list, we nee d to crea t e a start
node , used to crea t e and acce s s othe r node s in the linked list. The
following struc t u r e definition will do (see figur e 6.2.2):

 Crea ti n g a struc t u r e with one dat a item and a next point e r,

which will be pointin g to next node of the list. This is called as
self- refer e n ti al struc t u r e .

 Initialise the start point e r to be NULL.

st r u ct s l i n k l ist
{
int d at a; node: d at a n e xt
st r u ct s l i n k l ist * n e x t ;
};

t y p e d e f st r u ct s l i n k l ist n o d e ; st a rt

n o d e * st a r t = N U L L; E m p t y li s t : NULL

Fi g u r e 6 . 2 . 2 . S t r u c t u r e d e f i n it i o n , s i n g l e l i n k n o d e a n d e m p t y l i s t

The bas i c op e r a t i o n s in a sin g l e lin k e d list are:

 Crea tio n.
 Inse r tio n.
 Deletion.
 Traver si n g.

Creating a node for Single Linked List:

Creating a singly linked list starts with creating a node. Sufficient memory has to be allocated for
creating a node. The information is stored in the memory, allocated by using the malloc() function.
The function getnode(), is used for creating a node, after allocating memory for the structure of type
node, the information for the item (i.e., data) has to be read from the user, set next field to NULL and
finally returns the address of the node. Figure 6.2.3 illustrates the creation of a node for single linked
list.

no d e* g et no d e( )
{ new node
no d e* n e w no d e;
n e w n o d e = ( n o d e * ) m a l l o c ( s iz e o f ( n o d e ) ) ; 10 X
p r i n t f ( " \ n En t e r d a t a : " ) ; 100
s ca n f ( " % d " , & n e w n o d e - > d a t a ) ;
n e w n o d e - > n e x t = N U L L;
r et u r n n e w no d e;
}

Fi g u r e 6 . 2 . 3 . n e w n o d e w it h a v a l u e o f 1 0

Creat i n g a Sin g l y Link e d List with ‘n’ nu m b e r of nod e s :

The following steps are to be followed to create ‘n’ number of nodes:

63
 Get the new node using get no d e ().

new no d e = getno d e();

 If the list is empty, assign new node as start.

start = newnode;
 If the list is not empty, follow the steps given below:

 The next field of the new node is mad e to point the first
node (i.e. sta rt node) in the list by assignin g the addr e s s of
the first node.

 The star t point e r is mad e to point the new node by

assignin g the addr e s s of the new node.

 Repe a t the above steps ‘n’ times.

Figur e 6.2.4 shows 4 item s in a single linked list stor e d at differ e n t

locations in memo ry.

st a rt
100

10 200 20 300 30 400 40 X

100 200 300 400

Fi g u r e 6 . 2 . 4 . S i n g l e L i n k e d L i s t w it h 4 n o d e s

The function cre a t elis t(), is used to cre a t e ‘n’ num b e r of node s:

v o i d c r e a t e list ( i n t n )
{
i n t i;
no d e * n e w no d e;
no d e * t e m p ;
fo r( i = 0 ; i < n ; i+ + )
{
n e w no d e = g et no d e( ) ;
if ( st a r t = = N U L L)
{
st a rt = n e w no d e;
}
e ls e
{
t e m p = st a r t ;
w h i l e ( t e m p - > n e x t ! = N U L L)
tem p = t em p - > next;
t e m p - > n e x t = n e w no d e;
}
}
}

64
Ins e r t i o n of a Nod e :

One of the most primitive operations that can be done in a singly linked list is the insertion of a node.
Memory is to be allocated for the new node (in a similar way that is done while creating a list) before
reading the data. The new node will contain empty data field and empty next field. The data field of
the new node is then stored with the information read from the user. The next field of the new node is
assigned to NULL. The new node can then be inserted at three different places namely:

 Inse r ti n g a node at the begin nin g.

 Inse r ti n g a node at the end.
 Inse r ti n g a node at inter m e d i a t e position.

Ins e r t i n g a nod e at th e be g i n n i n g :

The following steps are to be followe d to inser t a new node at the

beginni n g of the list:

 Get the new node using get no d e ().

new no d e = getno d e();

 If the list is empty then start = newnode.

 If the list is not empty, follow the steps given below:

new no d e -> next = star t;

start = newnode;

The function inser t_at_b e g(), is used for insertin g a node at the
beginni n g

Figur e 6.2.5 shows inser ti n g a node into the single linked list at the
beginni n g.

65
st a rt
500

10 200 20 300 30 400 40 X

100 200 300 400

5 100
500

Fi g u r e 6 . 2 . 5 . I n s e r t i n g a n o d e a t t h e b e g i n n i n g

Ins e r t i n g a nod e at th e en d:

The following steps are followe d to inse r t a new node at the end of the
list:

 Get the new node using getnode()

newnode = getnode();

 If the list is empty then start = newnode.

 If the list is not empty follow the steps given below:

tem p = start;
while(te m p -> next != NULL)
tem p = tem p -> next;
temp -> next = newnode;

The function inser t_at_e n d(), is use d for inser ti n g a node at the end.

Figur e 6.2.6 shows inse r ti n g a node into the single linked list at the end.

st a rt
100

10 200 20 300 30 400 40 500

100 200 300 400

50 X
500

Fi g u r e 6 . 2 . 6 . I n s e r t i n g a n o d e a t t h e e n d .

Ins e r t i n g a nod e at int e r m e d i a t e pos i t i o n :

The following steps are followed, to insert a new node in an intermediate position in the list:

 Get the new node using get no d e ().

new no d e = getno d e();

66
 Ens u r e that the specified position is in betw e e n first node and
last node. If not, specified position is invalid. This is done by
count n o d e () function.

 Store the star ti n g add r e s s (which is in star t point e r) in tem p and

prev pointe r s . Then trave r s e the temp point e r upto the specified
position followed by prev point e r .

 After reac hi n g the specified position, follow the step s given

below:

prev -> next = new no d e ;

new no d e -> next = tem p;

 Let the inte r m e d i a t e position be 3.

The function inser t_at_mi d(), is used for inser ti n g a node in the
inter m e d i a t e position.

Figure 6.2.7 shows inserting a node into the single linked list at a specified intermediate position other
than beginning and end.

st a rt pr ev t e mp
100

10 200 20 500 30 400 40 X

100 200 300 400

50 300
500 new node

Fi g u r e 6 . 2 . 7 . I n s e r t i n g a n o d e a t a n i n t e r m e d i a t e p o s it i o n .

Del e t i o n of a nod e:

Anothe r primitive oper a tio n that can be done in a singly linked list is the
deletion of a node. Memo ry is to be rele a s e d for the node to be delet e d. A
node can be delet e d from the list from thre e differe n t place s nam ely.

 Deleting a node at the begin ni n g.

 Deleting a node at the end.
 Deleting a node at inter m e d i a t e position.

Del e t i n g a nod e at th e be g i n n i n g :

67
The following steps are followe d, to delet e a node at the beginni n g of the
list:

 If list is empty then display ‘Empty List’ mess a g e .

 If the list is not empty, follow the step s given below:

tem p = start;
star t = star t -> next;
free(t e m p );

The function delete_at_beg(), is used for deleting the first node in the list.

Figure 6.2.8 shows deleting a node at the beginning of a single linked list.

st a rt

200

10 200 20 300 30 400 40 X

100 200 300 400
t e mp

Fi g ur e 6. 2. 8. De l e t i n g a n o d e at t h e b e g i n n i n g.

Del e t i n g a nod e at th e en d:

The following steps are followe d to delet e a node at the end of the list:

 If list is empty then display ‘Empty List’ mess a g e .

 If the list is not empty, follow the step s given below:

tem p = prev = start;

while(te m p -> next != NULL)
{
prev = temp;
tem p = tem p -> next;
}
prev -> next = NULL;
free(t e m p );

The function delet e_a t_las t(), is used for deletin g the last node in the list.

Figur e 6.2.9 shows deletin g a node at the end of a single linked list.

68
st a rt

100

10 200 20 300 30 X 40 X
100 200 300 400

Fi g u r e 6 . 2 . 9 . D e l e t i n g a n o d e a t t h e e n d .

Del e t i n g a nod e at Int er m e d i a t e pos i t i o n :

The following steps are followe d, to delet e a node from an inter m e d i a t e

position in the list (List must cont ai n more tha n two node).

 If list is empty then display ‘Empty List’ mess a g e

 If the list is not empty, follow the step s given below.

if(pos > 1 && pos < node c t r)

{
tem p = prev = start;
ctr = 1;
while(ct r < pos)
{
prev = temp;
tem p = tem p -> next;
ctr + + ;
}
prev -> next = tem p -> next;
free(t e m p );
printf("\n node delet e d..");
}
The function delet e_a t_mid(), is used for deletin g the inter m e d i a t e node
in the list.

Figure 6.2.10 shows deleting a node at a specified intermediate position other than beginning and
end from a single linked list.

st a rt

100

10 300 20 300 30 400 40 X

100 200 300 400

Fi g u r e 6 . 2 . 1 0 . De l e t i n g a n o d e a t a n i n t e r m e d i a t e p o s it i o n .

Traver s a l and dis pl a yi n g a list (Left to Rig h t ):

69
To display the inform a tio n, you have to trave r s e (move) a linked list,
node by node from the first node, until the end of the list is reac h e d .
Traver si n g a list involves the following steps:

 Assign the add r e s s of star t point e r to a tem p point e r .

 Display the inform a tio n from the dat a field of eac h node.

The function traver s e () is used for trave r si n g and displaying the

inform a tio n store d in the list from left to right.

v o id t r a v e rs e( )
{
no d e * t e m p ;
t e m p = st a r t ;
p r i n t f ( " \ n T h e co n t e n t s o f L ist ( L e f t t o Ri g h t ) : \ n " ) ;
if ( st a r t = = N U L L )
p r i n t f ( " \ n Em p t y L ist " ) ;
e ls e
w h i l e ( t e m p ! = N U L L)
{
p r int f( " % d - > " , t e m p - > d at a) ;
tem p = t em p - > next;
}
p r i n t f ( " X" ) ;
}

Alter n a t i v e l y the r e is anot h e r way to trave r s e and display the

inform a tio n. That is in reve r s e orde r. The function rev_trav e r s e (), is used
for trave r si n g and displayin g the infor m a tio n store d in the list from right
to left.

v o i d r e v _ t r a v e r s e ( n o d e * st )
{
if ( st = = N U L L)
{
r et u r n;
}
e ls e
{
r e v _ t r a v e r s e ( st - > n e x t ) ;
p r i n t f ( " % d - > " , st - > d a t a ) ;
}
}

Cou n t i n g th e Nu m b e r of Nod e s :

The following code will count the num b e r of node s exist in the list using
recursio n .

70
i n t co u n t n o d e ( n o d e * st )
{
if ( st = = N U L L)
r et u r n 0 ;
e ls e
r e t u r n ( 1 + co u n t n o d e ( st - > n e x t ) ) ;
}

6.3. A Complete Source Code for the Implementation of Single Linked List:

# includ e < st dio. h >

# includ e < co nio.h >
# includ e < st dlib. h >

stru ct slinklist
{
int data;
stru ct slinklist *next;
};

typed ef struct slinklist node;

node *start = NULL;

int menu()
{
int ch;
clrscr();
printf("\n 1.Cre a t e a list ");
printf("\n- -------------------------");
printf("\n 2.Inse r t a node at beginnin g ");
printf("\n 3.Inse r t a node at end");
printf("\n 4.Inse r t a node at middle");
printf("\n- -------------------------");
printf("\n 5.Delet e a node from begin nin g");
printf("\n 6.Delet e a node from Last");
printf("\n 7.Delet e a node from Middle");
printf("\n- -------------------------");
printf("\n 8.Trave r s e the list (Left to Right)");
printf("\n 9.Trave r s e the list (Right to Left)");
printf("\n- -------------------------");
printf("\n 10. Count node s ");
printf("\n 11. Exit ");
printf("\n\n Enter your choice: ");
scanf("%d",&ch);
retu r n ch;
}

node* getno d e()

{
node * newno d e ;
newno d e = (node *) malloc(sizeof(no d e));
printf("\n Ente r data: ");
scanf("%d", &new no d e -> data);
newno d e -> next = NULL;
retu r n newno d e ;
}

int count n o d e( n o d e *ptr)

{
int count = 0 ;
while(pt r != NULL)
{
count + + ;
ptr = ptr -> next;

71
}
retu r n (count);
}

void creat elist(in t n)

{
int i;
node *newnod e;
node *temp;
for(i = 0; i < n; i+ + )
{
newno d e = getno d e();
if(star t = = NULL)
{
star t = newno d e;
}
else
{
tem p = start;
while(te m p -> next != NULL)
tem p = temp -> next;
tem p -> next = newno d e ;
}
}
}

void trave r s e()

{
node *temp;
tem p = start;
printf("\n The conte n t s of List (Left to Right): \n");
if(star t = = NULL)
{
printf("\n Empty List");
retu r n ;
}
else
while(te m p != NULL)
{
printf("%d- ->", tem p -> data);
tem p = temp -> next;
}
printf(" X ");
}

void rev_tr av e r s e ( n o d e *start)

{
if(star t = = NULL)
{
retu r n ;
}
else
{
rev_tr av e r s e ( s t a r t -> next);
printf("%d -->", start -> data);
}
}

void insert_at_b e g()

{
node *newnod e;
newno d e = getno d e();
if(star t = = NULL)
{
star t = newno d e;
}
else
{
newno d e -> next = start;

72
star t = newno d e;
}
}

void insert_at_e n d()

{
node *newnod e, *temp;
newno d e = getno d e();
if(star t = = NULL)
{
star t = newno d e;
}
else
{
tem p = start;
while(te m p -> next != NULL)
tem p = temp -> next;
tem p -> next = newno d e ;
}
}

void insert_at_mid()
{
node *newnod e, *temp, *prev;
int pos, nodec t r , ctr = 1;
newno d e = getno d e();
printf("\n Ente r the position: ");
scanf("%d", &pos);
nodect r = count n o d e ( s t a r t );
if(pos > 1 && pos < nodect r)
{
tem p = prev = start;
while(ctr < pos)
{
prev = tem p;
tem p = temp -> next;
ctr + + ;
}
prev -> next = newno d e ;
newno d e -> next = tem p;
}
else
{
printf("position %d is not a middle position", pos);
}
}

void delet e_a t_b e g()

{
node *temp;
if(star t = = NULL)
{
printf("\n No nodes are exist..");
retu r n ;
}
else
{
tem p = start;
star t = temp -> next;
free(t e m p );
printf("\n Node delet e d ");
}
}

void delet e_a t_las t()

{
node *temp, *prev;
if(star t = = NULL)
{

73
printf("\n Empty List..");
retu r n ;
}
else
{
tem p = start;
prev = star t;
while(te m p -> next != NULL)
{
prev = tem p;
tem p = temp -> next;
}
prev -> next = NULL;
free(t e m p );
printf("\n Node delet e d ");
}
}

void delet e_a t_mid()

{
int ctr = 1, pos, nodec t r;
node *temp, *prev;
if(star t = = NULL)
{
printf("\n Empty List..");
retu r n ;
}
else
{
printf("\n Ente r position of node to delet e: ");
scanf("%d", &pos);
nodect r = count n o d e ( s t a r t );
if(pos > nodec t r)
{
printf("\nThis node does no t exist");

}
if(pos > 1 && pos < nodect r)
{
tem p = prev = start;
while(ctr < pos)
{
prev = tem p;
tem p = temp -> next;
ctr + + ;
}
prev -> next = tem p -> next;
free(t e m p );
printf("\n Node delet e d ..");
}
else
{
printf("\n Invalid position..");
getch();
}

}
}

void main(void)
{
int ch, n;
clrscr();
while(1)
{
ch = men u();
switch(c h)
{
case 1:

74
if(star t = = NULL)
{
printf("\n Num b e r of nodes you want to crea t e : ");
scanf("%d", &n);
creat elist(n);
printf("\n List crea t e d . .");
}
else
printf("\n List is alre a dy cre at e d . .");
brea k;
case 2:
insert_at_be g();
brea k;

case 3:
insert_at_en d();
brea k;
case 4:
insert_at_mid();
brea k;
case 5:
delet e_at_be g();
brea k;
case 6:
delet e_at_las t();
brea k;
case 7:
delet e_at_mid();
brea k;
case 8:
trave r s e();
brea k;
case 9:
printf("\n The conte n t s of List (Right to Left): \n");
rev_tr av e r s e ( s t a r t );
printf(" X ");
brea k;
case 10:
printf("\n No of nodes : %d ", count no d e( s t a r t ));
brea k;
case 11 :
exit(0);
}
getch();
}
}

6. 4. Dou b l e Link e d List:

A double linked list is a two-way list in which all nodes will have two links. This helps in accessing
both successor node and predecessor node from the given node position. It provides bi-directional
traversing. Each node contains three fields:

 Left link.
 Data.
 Right link.

The left link point s to the pred e c e s s o r node and the right link points to
the succ e s s o r node. The data field store s the requir e d dat a.

Many applica tion s requir e sea rc hi n g forwa r d and backw a r d thru node s
of a list. For exam pl e sea rc hi n g for a nam e in a telep h o n e direct o ry

75
would nee d forw a r d and backw a r d scan ni n g thru a region of the whole
list.

The basic oper a tio n s in a doubl e linked list are:

 Crea tio n.
 Inse r tio n.
 Deletion.
 Traver si n g.

A double linked list is show n in figur e 6.3.1.

S TAC K St o r e s t h e H EAP
pr ev io u s n o d e
100 a d dr e s s.

st a rt
X 10 200 100 20 300 200 30 X
T h e st art 100 200 300
p o int er
h o ld s t h e St o r e s t h e d a t a . St o r e s t h e n e xt Th e r ig ht f ie ld of
a d dr e s s of n o d e a d dr e s s. t h e l a st n o d e i s
t h e f ir s t N ULL.
n o d e of t h e
l i st .

Fi g u r e 6 . 3 . 1 . D o u b l e L i n k e d L i s t

The begin ni n g of the double linked list is store d in a " start " point e r
which points to the first node. The first node’s left link and last node’s
right link is set to NULL.

The following code gives the struc t u r e definition:

st r u ct d l i n k l ist
{ node: lef t d at a r ig ht
st r u ct d l i n k l ist * l e f t ;
int d at a;
st r u ct d l i n k l ist * r i g h t ;

}; st a rt
E m p t y li s t : NULL
t y p e d e f st r u ct d l i n k l ist n o d e ;
n o d e * st a r t = N U L L;

Fi g u r e 6 . 4 . 1 . S t r u c t u r e d e f i n it i o n , d o u b l e l i n k n o d e a n d e m p t y l i s t

Creat i n g a nod e for Dou b l e Link e d List:

Crea ti n g a double linked list star t s with cre a ti n g a node. Sufficien t

me mo ry has to be allocat e d for cre a ti n g a node. The inform a tio n is
stor e d in the mem o ry, allocat e d by using the malloc() function. The
function getno d e(), is used for crea ti n g a node, afte r allocatin g me mo ry
for the stru c t u r e of type node, the inform a ti o n for the item (i.e., data) has
to be rea d from the use r and set left field to NULL and right field also set
to NULL (see figure 6.2.2).

76
no d e* g et no d e( )
{
no d e* n e w no d e;
n e w n o d e = ( n o d e * ) m a l l o c( s iz e o f ( n o d e ) ) ; new node
p r in t f ( " \ n En t e r d a t a : " ) ; X 10 X
sca n f ( " % d " , & n e w n o d e - > d a t a ) ;
n e w n o d e - > l e f t = N U L L; 100
n e w n o d e - > r i g h t = N U L L;
r et u r n n e w no d e;
}

Fi g u r e 6 . 4 . 2 . n e w n o d e w it h a v a l u e o f 1 0

Creat i n g a Dou b l e Link e d List with ‘n’ nu m b e r of nod e s :

The following steps are to be followed to create ‘n’ number of nodes:

 Get the new node using get no d e ().

new no d e = g e t n o d e ();

 If the list is empty then start = newnode.

 If the list is not empty, follow the steps given below:

 The left field of the new node is mad e to point the

previou s node.

 The previous node s right field mus t be assig n e d with

add r e s s of the new node.

 Repe a t the above steps ‘n’ times.

The function cre a t elis t(), is used to cre a t e ‘n’ num b e r of node s:

v o i d c r e a t e list ( i n t n )
{
i n t i;
no d e * n e w no d e;
no d e * t e m p ;
fo r( i = 0 ; i < n; i+ + )
{
n e w no d e = g et no d e( ) ;
if ( st a r t = = N U L L)
{
st a r t = n e w n o d e ;
}
e ls e
{
t e m p = st a r t ;
w h ile( t e m p - > r ig ht )
t e m p = t e m p - > r ig ht ;
t e m p - > r ig ht = n e w no d e;
n e w no d e - > left = t e m p ;
}
}
}

77
Figur e 6.4.3 shows 3 item s in a double linked list stor e d at differ e n t
locations.

st a rt
100

X 10 200 100 20 300 200 30 X

100 200 300

Fi g u r e 6 . 4 . 3 . D o u b l e L i n k e d L i s t w it h 3 n o d e s

Ins e r t i n g a nod e at th e be g i n n i n g :

The following steps are to be followe d to inser t a new node at the

beginni n g of the list:

 Get the new node using get no d e ().

new no d e = g e t n o d e ( );

 If the list is empty then start = newnode.

 If the list is not empty, follow the steps given below:

new no d e -> right = start;

star t -> left = newno d e ;
star t = new no d e ;

The function dbl_ins e r t_b e g(), is use d for inser ti n g a node at the
beginni n g. Figur e 6.4.4 shows inser ti n g a node into the double linked list
at the begin ni n g.

st a rt
400

400 10 200 100 20 300 200 30 X

100 200 300

X 40 100

400

Fi g u r e 6 . 4 . 4 . I n s e r t i n g a n o d e a t t h e b e g i n n i n g

Ins e r t i n g a nod e at th e en d:

The following steps are followe d to inse r t a new node at the end of the
list:

 Get the new node using getnode()

78
newnode=getnode();

 If the list is empty then start = newnode.

 If the list is not empty follow the steps given below:

tem p = start;
while(te m p -> right != NULL)
tem p = tem p -> right;
tem p -> right = new no d e ;
new no d e -> left = temp;

The function dbl_ins e r t_e n d (), is used for inse rti n g a node at the end.
Figur e 6.4.5 shows inse r ti n g a node into the double linked list at the end.

st a rt
100

X 10 200 100 20 300 200 30 400

100 200 300

300 40 X
400

Fi g u r e 6 . 4 . 5 . I n s e r t i n g a n o d e a t t h e e n d

Ins e r t i n g a nod e at an int er m e d i a t e pos i ti o n :

The following steps are followed, to insert a new node in an intermediate position in the list:

 Get the new node using get no d e ().

new no d e = g e t n o d e ( );

 Ens u r e that the specified position is in betw e e n first node and

last node. If not, specified position is invalid. This is done by
count n o d e () function.

 Store the star ti n g add r e s s (which is in star t point e r) in tem p and

prev pointe r s . Then trave r s e the temp point e r upto the specified
position followed by prev point e r .

 After reac hi n g the specified position, follow the step s given

below:

new no d e -> left = temp;

new no d e -> right = tem p -> right;
tem p -> right -> left = new no d e;
tem p -> right = new no d e ;

79
The function dbl_ins e r t_ mi d(), is used for inser ti n g a node in the
inter m e d i a t e position. Figur e 6.4.6 shows inser ti n g a node into the
double linke d list at a specifie d inter m e d i a t e position othe r than
beginni n g and end.

st a rt
100 40 200
100
400
400 20 300
X 10 400
200
100

200 30 X
300
Fi g u r e 6 . 4 . 6 . I n s e r t i n g a n o d e a t a n i n t e r m e d i a t e p o s it i o n

Del e t i n g a nod e at th e be g i n n i n g :

The following steps are followe d, to delet e a node at the beginni n g of the
list:

 If list is empty then display ‘Empty List’ mess a g e .

 If the list is not empty, follow the step s given below:

tem p = start;
star t = star t -> right;
star t -> left = NULL;
free(t e m p );

The function dbl_delet e_b e g(), is used for deletin g the first node in the
list. Figur e 6.4.6 shows deletin g a node at the begin ni n g of a doubl e
linked list.

st a rt
200

X 10 200 X 20 300 200 30 X

100 200 300

Fi g u r e 6 . 4 . 6 . D e l e t i n g a n o d e a t b e g i n n i n g

Del e t i n g a nod e at th e en d:

The following steps are followe d to delet e a node at the end of the list:
 If list is empty then display ‘Empty List’ mess a g e

 If the list is not empty, follow the step s given below:

tem p = start;

80
while(te m p -> right != NULL)
{
tem p = tem p -> right;
}
tem p -> left -> right = NULL;
free(t e m p );

The function dbl_delet e_la s t(), is use d for deletin g the last node in the
list. Figur e 6.4.7 shows deletin g a node at the end of a double linked list.

st a rt
100

X 10 200 100 20 X 200 30 X

100 200 300

Fi g u r e 6 . 4 . 7 . D e l e t i n g a n o d e a t t h e e n d

Del e t i n g a nod e at Int er m e d i a t e pos i t i o n :

The following steps are followe d, to delet e a node from an inter m e d i a t e

position in the list (List must cont ai n more tha n two nodes).

 If list is empty then display ‘Empty List’ mess a g e .

 If the list is not empty, follow the step s given below:

 Get the position of the node to delet e.

 Ens u r e that the specified position is in betw e e n first node

and last node. If not, specified position is invalid.

 Then perfor m the following steps:

if(pos > 1 && pos < node c t r)

{
tem p = start;
i = 1;
while(i < pos)
{
tem p = tem p -> right;
i+ + ;
}
tem p -> right -> left = tem p -> left;
tem p -> left -> right = tem p -> right;
free(t e m p );
printf("\n node delet e d..");
}

81
The function delete_at_mid(), is used for deleting the intermediate node in the list. Figure 6.4.8 shows
deleting a node at a specified intermediate position other than beginning and end from a double
linked list.

st a rt
100

X 10 300 100 20 300 100 30 X

100 200 300

Fi g u r e 6 . 4 . 8 D e l e t i n g a n o d e a t a n i n t e r m e d i a t e p o s it i o n

Traver s a l and dis pl a yi n g a list (Left to Rig h t ):

To display the inform a ti o n, you have to trave r s e the list, node by node
from the first node, until the end of the list is reac h e d . The function
traver s e_left_righ t () is used for trave r si n g and displaying the inform a ti o n
stor e d in the list from left to right.

The following steps are followe d, to trave r s e a list from left to right:

 If list is empty then display ‘Empty List’ mess a g e .

 If the list is not empty, follow the step s given below:

tem p = start;
while(te m p != NULL)
{
print tem p -> data;
tem p = tem p -> right;
}

Traver s a l and dis pl a yi n g a list (Ri g h t to Left):

To display the inform a tio n from right to left, you have to trave r s e the list,
node by node from the first node, until the end of the list is reac h e d . The
function travers e_rig h t_lef t () is used for trave r si n g and displayin g the
inform a tio n store d in the list from right to left.

The following steps are followe d, to trave r s e a list from right to left:

 If list is empty then display ‘Empty List’ mess a g e .

 If the list is not empty, follow the step s given below:

tem p = start;
while(te m p -> right != NULL)
tem p = tem p -> right;
while(te m p != NULL)

82
{
print tem p -> data;
tem p = tem p -> left;
}

Cou n t i n g th e Nu m b e r of Nod e s :

The following code will count the num b e r of node s exist in the list (using
rec u r sio n).

i n t co u n t n o d e ( n o d e * st a r t )
{
if ( st a r t = = N U L L)
r et u r n 0 ;
e ls e
r e t u r n ( 1 + co u n t n o d e ( st a r t - > r i g h t ) ) ;
}

6.5. A Complete Source Code for the Implementation of Double Linked List:

#i n cl u d e <s t dio. h >

#i n cl u d e <s t dlib. h >
#i n cl u d e <co nio. h >

stru ct dlinklist
{
stru ct dlinklist *left;
int data;
stru ct dlinklist *right;
};

typed ef struct dlinklist node;

node *start = NULL;

node* getno d e()

{
node * newno d e ;
newno d e = (node *) malloc(sizeof(no d e));
printf("\n Ente r data: ");
scanf("%d", &new no d e -> data);
newno d e -> left = NULL;
newno d e -> right = NULL;
retu r n newno d e ;
}

int count n o d e( n o d e *start)

{
if(star t = = NULL)

83
retu r n 0;
else
retu r n 1 + count n o d e ( s t a r t -> right);
}

int menu()
{
int ch;
clrscr();
printf("\n 1.Cre a t e ");
printf("\n- -----------------------------");
printf("\n 2. Inser t a node at begin nin g ");
printf("\n 3. Inser t a node at end");
printf("\n 4. Inser t a node at middle");
printf("\n- -----------------------------");
printf("\n 5. Delete a node from beginni n g");
printf("\n 6. Delete a node from Last");
printf("\n 7. Delete a node from Middle");
printf("\n- -----------------------------");
printf("\n 8. Traver s e the list from Left to Right ");
printf("\n 9. Traver s e the list from Right to Left ");
printf("\n- -----------------------------");
printf("\n 10.Cou n t the Num b e r of node s in the list");
printf("\n 11.Exit ");
printf("\n\n Enter your choice: ");
scanf("%d", &ch);
retu r n ch;
}

void creat elist(in t n)

{
int i;
node *newnod e;
node *temp;
for(i = 0; i < n; i+ + )
{
newno d e = getno d e();
if(star t = = NULL)
star t = newno d e;
else
{
tem p = start;
while(te m p -> right)
tem p = temp -> right;
tem p -> right = newno d e ;
newno d e -> left = tem p;
}
}
}

void trave r s e_left_to_righ t()

{
node *temp;
tem p = start;
printf("\n The conte n t s of List: ");
if(star t = = NULL )
printf("\n Empty List");
else
while(te m p != NULL)
{
printf("\t %d ", temp -> data);
tem p = temp -> right;
}
}

void trave r s e_rig h t_to_left()

{

84
node *temp;
tem p = start;
printf("\n The conte n t s of List: ");
if(star t = = NULL)
printf("\n Empty List");
else
while(te m p -> right != NULL)
tem p = temp -> right;
while(te m p != NULL)
{
printf("\t%d", temp -> data);
tem p = temp -> left;
}
}

void dll_inser t_b e g ()

{
node *newnod e;
newno d e = getno d e();
if(star t = = NULL)
star t = newno d e;
else
{
newno d e -> right = star t;
star t -> left = newno d e ;
star t = newno d e;
}
}

void dll_inser t_e n d ()

{
node *newnod e, *temp;
newno d e = getno d e();
if(star t = = NULL)
star t = newno d e;
else
{
tem p = start;
while(te m p -> right != NULL)
tem p = temp -> right;
tem p -> right = newno d e ;
newno d e -> left = tem p;
}
}

void dll_inser t_mid()

{
node *newnod e,*te m p ;
int pos, node ct r , ctr = 1;
newno d e = getno d e();
printf("\n Ente r the position: ");
scanf("%d", &pos);
nodect r = count n o d e ( s t a r t );
if(pos - nodec t r > = 2)
{
printf("\n Position is out of ran g e..");
retu r n ;
}
if(pos > 1 && pos < nodect r)
{
tem p = start;
while(ctr < pos - 1)
{
tem p = temp -> right;
ctr + + ;
}
newno d e -> left = tem p;
newno d e -> right = tem p -> right;
tem p -> right -> left = newno d e;

85
tem p -> right = newno d e ;
}
else
printf("position %d of list is not a middle position ", pos);
}

void dll_delet e_b e g()

{
node *temp;
if(star t = = NULL)
{
printf("\n Empty list");
getch();
retu r n ;
}
else
{
tem p = start;
star t = start -> right;
star t -> left = NULL;
free(t e m p );
}
}

void dll_delet e_last()

{
node *temp;
if(star t = = NULL)
{
printf("\n Empty list");
getch();
retu r n ;
}
else
{
tem p = start;
while(te m p -> right != NULL)
tem p = temp -> right;
tem p -> left -> right = NULL;
free(t e m p );
tem p = NULL;
}
}

void dll_delet e_mid()

{
int i = 0, pos, nodec t r ;
node *temp;
if(star t = = NULL)
{
printf("\n Empty List");
getch();
retu r n ;
}
else
{
printf("\n Ente r the position of the node to delet e: ");
scanf("%d", &pos);
nodect r = count n o d e ( s t a r t );
if(pos > nodec t r)
{
printf("\nt his node does not exist");
getch();
retu r n ;
}
if(pos > 1 && pos < nodect r)
{
tem p = start;
i = 1;

86
while(i < pos)
{
tem p = temp -> right;
i+ + ;
}
tem p -> right -> left = temp -> left;
tem p -> left -> right = temp -> right;
free(t e m p );
printf("\n node delet e d ..");
}
else
{
printf("\n It is not a middle position..");
getch();
}
}
}

void main(void)
{
int ch, n;
clrscr();
while(1)
{
ch = men u();
switch( ch)
{
case 1 :
printf("\n Ente r Numb e r of nodes to creat e: ");
scanf("%d", &n);
creat elist(n);
printf("\n List crea t e d . .");
brea k;
case 2 :
dll_inser t_b e g();
brea k;
case 3 :
dll_inser t_en d ();
brea k;
case 4 :
dll_inser t_mid();
brea k;
case 5 :
dll_delet e_b e g();
brea k;
case 6 :
dll_delet e_last();
brea k;
case 7 :
dll_delet e_mi d();
brea k;
case 8 :
trave r s e_left_to_righ t();
brea k;
case 9 :
trave r s e_rig h t_to_left();
brea k;

case 10 :
printf("\n Num b e r of nodes: %d", count n o d e( s t a r t ));
brea k;
case 11:
exit(0);
}
getch();
}
}

87
6. 6. Circ u l a r Sin g l e Link e d List:

It is just a single linke d list in which the link field of the last node points
back to the add r e s s of the first node. A circula r linke d list has no
beginni n g and no end. It is nece s s a r y to esta blis h a special point e r called
start point e r always pointin g to the first node of the list. Circula r linked
lists are frequ e n tly use d inste a d of ordina ry linke d list beca u s e many
oper a tio n s are much easie r to imple m e n t . In circul a r linked list no null
point e r s are used, henc e all point e r s cont ai n valid addr e s s .

A circula r single linked list is show n in figur e 6.6.1.

st a rt
100

10 200 20 300 30 400 40 100

100 200 300 400

Fi g u r e 6 . 6 . 1 . C ir c u l a r S i n g l e L i n k e d L i s t

The basic oper a tio n s in a circula r single linked list are:

 Crea tio n.
 Inse r tio n.
 Deletion.
 Traver si n g.

Creat i n g a circ u l a r sin g l e Link e d List with ‘n’ nu m b e r of nod e s :

The following steps are to be followed to create ‘n’ number of nodes:

 Get the new node using get no d e ().

new no d e = getno d e();

 If the list is empty, assign new node as start.

start = newnode;

 If the list is not empty, follow the steps given below:

tem p = start;
while(te m p -> next != NULL)
tem p = tem p -> next;
tem p -> next = newno d e ;

 Repe a t the above steps ‘n’ times.

88
 new no d e -> next = star t;

The function cre a t elis t(), is used to cre a t e ‘n’ num b e r of node s:

Ins e r t i n g a nod e at th e be g i n n i n g :

The following steps are to be followe d to inser t a new node at the

beginni n g of the circula r list:

 Get the new node using get no d e ().

new no d e = getno d e();

 If the list is empty, assign new node as start.

star t = new no d e ;
new no d e -> next = star t;

 If the list is not empty, follow the steps given below:

last = star t;
while(las t -> next != sta rt)
last = last -> next;
new no d e -> next = star t;
star t = new no d e ;
last -> next = start;

The function cll_inse r t_b e g(), is used for inser ti n g a node at the
beginni n g. Figur e 6.6.2 show s inser ti n g a node into the circula r single
linked list at the begin ni n g.

st a rt
500

10 200 20 300 30 400 40 500

100 200 300 400

5 100
500

Fi g u r e 6 . 6 . 2 . I n s e r t i n g a n o d e a t t h e b e g i n n i n g

Ins e r t i n g a nod e at th e en d:

The following steps are followe d to inse r t a new node at the end of the
list:

 Get the new node using getnode().

new no d e = getno d e();

89
 If the list is empty, assign new node as start.

star t = new no d e ;
new no d e -> next = star t;

 If the list is not empty follow the steps given below:

tem p = start;
while(te m p -> next != star t)
tem p = tem p -> next;
tem p -> next = newno d e ;
new no d e -> next = star t;

The function cll_inse r t_e n d (), is used for inser ti n g a node at the end.

Figur e 6.6.3 shows inser ti n g a node into the circula r single linked list at
the end.

st a rt
100

10 200 20 300 30 400 40 500

100 200 300 400

50 100
500

Fi g u r e 6 . 6 . 3 I n s e r t i n g a n o d e a t t h e e n d .

Del e t i n g a nod e at th e be g i n n i n g :

The following steps are followe d, to delet e a node at the beginni n g of the
list:

 If the list is empty, display a mes s a g e ‘Empty List’.

 If the list is not empty, follow the step s given below:

last = temp = start;

while(las t -> next != sta rt)
last = last -> next;
star t = star t -> next;
last -> next = start;

 After deletin g the node, if the list is empty the n start = NULL.

The function cll_delet e_b e g (), is used for deletin g the first node in the
list. Figur e 6.6.4 shows deletin g a node at the begin ni n g of a circul a r

90
single linked list.
st a rt

200

10 200 20 300 30 400 40 200

100 200 300 400
t e mp

Fi g u r e 6 . 6 . 4 . D e l e t i n g a n o d e a t b e g i n n i n g .

Del e t i n g a nod e at th e en d:

The following steps are followe d to delet e a node at the end of the list:

 If the list is empty, display a mes s a g e ‘Empty List’.

 If the list is not empty, follow the step s given below:

tem p = start;
prev = star t;
while(te m p -> next != star t)
{
prev = temp;
tem p = tem p -> next;
}
prev -> next = start;

 After deletin g the node, if the list is empty the n start = NULL.

The function cll_delet e_la s t(), is used for deletin g the last node in the
list.

Figur e 6.6.5 shows deletin g a node at the end of a circula r single linked
list.

st a rt

100

10 200 20 300 30 100 40 100

100 200 300 400

Fi g u r e 6 . 6 . 5 . D e l e t i n g a n o d e a t t h e e n d .

Traver s i n g a circ u l a r sin g l e link e d list fro m left to righ t:

The following steps are followe d, to trave r s e a list from left to right:

 If list is empty then display ‘Empty List’ mess a g e .

91
 If the list is not empty, follow the step s given below:

tem p = start;
do
{
printf("%d ", temp -> data);
tem p = tem p -> next;
} while(t e m p != sta rt);

6.7. A Complete Source Code for the Implementation of Circular Single

Linked List:

# includ e < st dio. h >

# includ e < co nio.h >
# includ e < st dlib. h >

stru ct cslinklist
{
int data;
stru ct cslinklist *next;
};

typed ef struct cslinklist node;

node *start = NULL;
int node ct r ;

node* getno d e()

{
node * newno d e ;
newno d e = (node *) malloc(sizeof(no d e));
printf("\n Ente r data: ");
scanf("%d", &new no d e -> data);
newno d e -> next = NULL;
retu r n newno d e ;
}

int menu()
{
int ch;
clrscr();
printf("\n 1. Crea t e a list ");
printf("\n\n- -------------------------");
printf("\n 2. Inser t a node at begin nin g ");
printf("\n 3. Inser t a node at end");
printf("\n 4. Inser t a node at middle");
printf("\n\n- -------------------------");
printf("\n 5. Delete a node from beginni n g");
printf("\n 6. Delete a node from Last");
printf("\n 7. Delete a node from Middle");
printf("\n\n- -------------------------");
printf("\n 8. Display the list");
printf("\n 9. Exit");
printf("\n\n- -------------------------");
printf("\n Ente r your choice: ");
scanf("%d", &ch);
retu r n ch;

92
}

void creat elist(in t n)

{
int i;
node *newnod e;
node *temp;
nodect r = n;
for(i = 0; i < n ; i+ + )
{
newno d e = getno d e();
if(star t = = NULL)
{
star t = newno d e;
}
else
{
tem p = start;
while(te m p -> next != NULL)
tem p = temp -> next;
tem p -> next = newno d e ;
}
}
newno d e -> n ex t = star t; /* last node is pointing to startin g node */
}

void display()
{
node *temp;
tem p = start;
printf("\n The conte n t s of List (Left to Right): ");
if(star t = = NULL )
printf("\n Empty List");
else
do
{
printf("\t %d ", temp -> data);
tem p = temp -> next;
}while(te m p != start);
printf(" X ");
}

void cll_inse rt_b e g()

{
node *newnod e, *last;
newno d e = getno d e();
if(star t = = NULL)
{
star t = newno d e;
newno d e -> next = start;
}
else
{
last = star t;
while(las t -> next != star t)
last = last -> next;
newno d e -> next = start;
star t = newno d e;
last -> next = star t;
}
printf("\n Node insert e d at begin nin g..");
nodect r + + ;
}

void cll_inse rt_e n d()

{
node *newnod e, *temp;
newno d e = getno d e();
if(star t = = NULL )

93
{
star t = newno d e;
newno d e -> next = start;
}
else
{
tem p = start;
while(te m p -> next != start)
tem p = temp -> next;
tem p -> next = newno d e ;
newno d e -> next = start;
}
printf("\n Node insert e d at end..");
nodect r + + ;
}

void cll_inse rt_ mid()

{
node *newnod e, *temp, *prev;
int i, pos ;
newno d e = getno d e();
printf("\n Ente r the position: ");
scanf("%d", &pos);
if(pos > 1 && pos < nodect r)
{
tem p = start;
prev = tem p;
i = 1;
while(i < pos)
{
prev = tem p;
tem p = temp -> next;
i+ + ;
}
prev -> next = newno d e ;
newno d e -> next = tem p;
nodect r + + ;
printf("\n Node insert e d at middle..");
}
else
{
printf("position %d of list is not a middle position ", pos);
}
}

void cll_delet e_b e g()

{
node *temp, *last;
if(star t = = NULL)
{
printf("\n No nodes exist..");
getch();
retu r n ;
}
else
{
last = tem p = start;
while(las t -> next != star t)
last = last -> next;
star t = start -> next;
last -> next = star t;
free(t e m p );
nodect r- -;
printf("\n Node delet e d ..");
if(nodec t r = = 0)
star t = NULL;
}
}

94
void cll_delet e_last()
{
node *temp,*pr ev;
if(star t = = NULL)
{
printf("\n No nodes exist..");
getch();
retu r n ;
}
else
{
tem p = start;
prev = star t;
while(te m p -> next != start)
{
prev = tem p;
tem p = temp -> next;
}
prev -> next = star t;
free(t e m p );
nodect r- -;
if(nodec t r = = 0)
star t = NULL;
printf("\n Node delet e d ..");
}
}

void cll_delet e_mid()

{
int i = 0, pos;
node *temp, *prev;

if(star t = = NULL)
{
printf("\n No nodes exist..");
getch();
retu r n ;
}
else
{
printf("\n Which node to delete: ");
scanf("%d", &pos);
if(pos > nodec t r)
{
printf("\nThis node does not exist");
getch();
retu r n ;
}
if(pos > 1 && pos < nodect r)
{
tem p = s t a r t ;
prev = star t;
i = 0;
while(i < pos - 1)
{
prev = tem p;
tem p = temp -> next ;
i+ + ;
}
prev -> next = tem p -> next;
free(t e m p );
nodect r- -;
printf("\n Node Delete d..");
}
else
{
printf("\n It is not a middle position..");
getch();

95
}
}
}

void main(void)
{
int result;
int ch, n;
clrscr();
while(1)
{
ch = men u();
switch(c h)
{
case 1 :
if(star t = = NULL)
{
printf("\n Ente r Numb e r of nodes to creat e: ");
scanf("%d", &n);
creat elist(n);
printf("\nList creat e d ..");
}
else
printf("\n List is alre a dy Exist..");
brea k;
case 2 :
cll_inser t_b e g();
brea k;
case 3 :
cll_inser t_e n d();
brea k;
case 4 :
cll_inser t_mid();
brea k;
case 5 :
cll_delet e_b e g();
brea k;
case 6 :
cll_delet e_last();
brea k;
case 7 :
cll_delet e_ mid();
brea k;
case 8 :
display();
brea k;
case 9 :
exit(0);
}
getch();
}
}

Circ u l a r Dou b l e Link e d List:

A circula r double linke d list has both succ e s s o r point e r and pred e c e s s o r
point e r in circul a r man n e r . The objective behin d consid e ri n g circula r
double linke d list is to simplify the inser tion and deletion oper a tio n s
perfor m e d on doubl e linked list. In circula r double linked list the right
link of the right most node points back to the start node and left link of
the first node points to the last node.

96
A circula r double linke d list is show n in figur e 6.8.1.

100

st a rt
300 10 200 100 20 300 200 30 100

100 200 300

Fi g u r e 6 . 8 . 1 . C ir c u l a r D o u b l e L i n k e d L i s t

The basic oper a tio n s in a circula r doubl e linked list are:

 Crea tio n.
 Inse r tio n.
 Deletion.
 Traver si n g.

Creat i n g a Circ u l a r Dou b l e Link e d List with ‘n’ nu m b e r of nod e s :

The following steps are to be followed to create ‘n’ number of nodes:

 Get the new node using get no d e ().

new no d e = getno d e();

 If the list is empty, then do the following

star t = new no d e ;
new no d e -> left = star t;
new no d e -> ri g h t = start;

 If the list is not empty, follow the steps given below:

new no d e -> left = star t -> left;

new no d e -> right = start;
star t -> left- > ri g h t = new no d e;
star t -> left = newno d e ;

 Repe a t the above steps ‘n’ times.

The function cdll_cre a t e lis t(), is use d to cre a t e ‘n’ num b e r of node s:

Ins e r t i n g a nod e at th e be g i n n i n g :

The following steps are to be followe d to inser t a new node at the

beginni n g of the list:

 Get the new node using get no d e ().

97
new no d e = g e t n o d e ( );

 If the list is empty, then

star t = new no d e ;
new no d e -> left = star t;
new no d e -> right = start;

 If the list is not empty, follow the steps given below:

new no d e -> left = star t -> left;

new no d e -> right = start;
star t -> left -> right = new no d e;
star t -> left = newno d e ;
star t = new no d e ;

The function cdll_ins e r t_b e g (), is used for inse r ti n g a node at the
beginni n g. Figur e 6.8.2 show s inser ti n g a node into the circula r doubl e
linked list at the begin ni n g.

st a rt
400

400 10 200 100 20 300 200 30 400

100 200 300

300 40 100

400

Fi g u r e 6 . 8 . 2 . I n s e r t i n g a n o d e a t t h e b e g i n n i n g

Ins e r t i n g a nod e at th e en d:

The following steps are followe d to inse r t a new node at the end of the
list:

 Get the new node using getnode()

newnode=getnode();

 If the list is empty, then

star t = new no d e ;
new no d e -> left = star t;
new no d e -> right = start;

 If the list is not empty follow the steps given below:

new no d e -> left = star t -> left;

new no d e -> right = start;
star t -> left -> right = new no d e;
star t -> left = newno d e ;

98
The function cdll_ins e r t_e n d(), is used for inser ti n g a node at the end.
Figur e 6.8.3 shows inser ti n g a node into the circula r linke d list at the
end.

st a rt
100

400 10 200 100 20 300 200 30 400

100 200 300

300 40 100
400

Fi g u r e 6 . 8 . 3 . I n s e r t i n g a n o d e a t t h e e n d

Ins e r t i n g a nod e at an int er m e d i a t e pos i ti o n :

The following steps are followed, to insert a new node in an intermediate position in the list:

 Get the new node using get no d e ().

new no d e = g e t n o d e ( );

 Ens u r e that the specified position is in betw e e n first node and

last node. If not, specified position is invalid. This is done by
count n o d e () function.

 Store the star ti n g add r e s s (which is in star t point e r) in tem p and

prev pointe r s . Then trave r s e the temp point e r upto the specified
position followed by prev point e r .

 After reac hi n g the specified position, follow the step s given

below:

new no d e -> left = temp;

new no d e -> right = tem p -> right;
tem p -> right -> left = new no d e;
tem p -> right = new no d e ;
nodec t r + + ;

The function cdll_insert_mid(), is used for inserting a node in the intermediate position. Figure 6.8.4
shows inserting a node into the circular double linked list at a specified intermediate position other
than beginning and end.

99
st a rt
100 40 200
100
400
300 10 400 400 20 300

100 200

200 30 100
300

Fi g u r e 6 . 8 . 4 . I n s e r t i n g a n o d e a t a n i n t e r m e d i a t e p o s it i o n

Del e t i n g a nod e at th e be g i n n i n g :

The following steps are followe d, to delet e a node at the beginni n g of the
list:

 If list is empty then display ‘Empty List’ mess a g e .

 If the list is not empty, follow the step s given below:

tem p = start;
star t = star t -> right;
tem p -> left -> right = star t;
star t -> left = tem p -> left;

The function cdll_delet e_b e g (), is used for deletin g the first node in the
list. Figur e 6.8.5 shows deletin g a node at the begin ni n g of a circul a r
double linke d list.

st a rt
200

300 10 200 300 20 300 200 30 200

100 200 300

Fi g u r e 6 . 8 . 5 . D e l e t i n g a n o d e a t b e g i n n i n g

Del e t i n g a nod e at th e en d:

The following steps are followe d to delet e a node at the end of the list:

 If list is empty then display ‘Empty List’ mess a g e

 If the list is not empty, follow the step s given below:

100
tem p = start;
while(te m p -> right != star t)
{
tem p = tem p -> right;
}
tem p -> left -> right = tem p -> right;
tem p -> right -> left = tem p -> left;

The function cdll_delet e_la s t(), is used for deletin g the last node in the
list. Figur e 6.8.6 shows deletin g a node at the end of a circul a r double
linked list.

st a rt
100

200 10 200 100 20 100 200 30 100

100 200 300

Fi g u r e 6 . 8 . 6 . D e l e t i n g a n o d e a t t h e e n d

Del e t i n g a nod e at Int er m e d i a t e pos i t i o n :

The following steps are followe d, to delet e a node from an inter m e d i a t e

position in the list (List must cont ai n more tha n two node).

 If list is empty then display ‘Empty List’ mess a g e .

 If the list is not empty, follow the step s given below:

 Get the position of the node to delet e.

 Ens u r e that the specified position is in betw e e n first node

and last node. If not, specified position is invalid.

 Then perfor m the following steps:

if(pos > 1 && pos < node c t r)

{

tem p = start;
i = 1;
while(i < pos)
{
tem p = tem p -> right ;
i+ + ;
}
tem p -> right -> left = tem p -> left;
tem p -> left -> right = tem p -> right;
free(t e m p );

101
printf("\n node delet e d..");
nodec t r- -;
}

The function cdll_delet e_ mid(), is used for deletin g the inter m e d i a t e node
in the list.
Figure 6.8.7 shows deleting a node at a specified intermediate position other than beginning and end
from a circular double linked list.

st a rt
100

300 10 300 100 20 300 100 30 100

100 200 300

Fi g u r e 6 . 8 . 7 . D e l e t i n g a n o d e a t a n i n t e r m e d i a t e p o s it i o n

Traver s i n g a circ u l a r dou b l e link e d list fro m left to rig h t:

The following steps are followe d, to trave r s e a list from left to right:

 If list is empty then display ‘Empty List’ mess a g e .

 If the list is not empty, follow the step s given below:

tem p = start;
Print tem p -> dat a;
tem p = tem p -> right;
while(te m p != star t)
{
print tem p -> data;
tem p = tem p -> right;
}

The function cdll_display_left _right(), is used for trave r si n g from left to

right.

Traver s i n g a circ u l a r dou b l e link e d list fro m rig h t to left:

The following steps are followe d, to trave r s e a list from right to left:

 If list is empty then display ‘Empty List’ mess a g e .

 If the list is not empty, follow the step s given below:

tem p = start;
do
{

102
tem p = tem p -> left;
print tem p -> data;
} while(t e m p != sta rt);

The function cdll_display_righ t_left(), is used for trave r si n g from right to

left.

6.9. A Complete Source Code for the Implementation of Circular Double

Linked List:

# includ e < st dio. h >

# includ e < st dlib. h >
# includ e < co nio.h >

stru ct cdlinklist
{
stru ct cdlinklist *left;
int data;
stru ct cdlinklist *right;

};

typed ef struct cdlinklist node;

node *start = NULL;
int node ct r ;

node* getno d e()

{
node * newno d e ;
newno d e = (node *) malloc(sizeof(no d e));
printf("\n Ente r data: ");
scanf("%d", &new no d e -> data);
newno d e -> left = NULL;
newno d e -> right = NULL;
retu r n newno d e ;
}

int menu()
{
int ch;
clrscr();
printf("\n 1. Crea t e ");
printf("\n\n- -------------------------");
printf("\n 2. Inser t a node at Beginnin g");
printf("\n 3. Inser t a node at End");
printf("\n 4. Inser t a node at Middle");
printf("\n\n- -------------------------");
printf("\n 5. Delete a node from Beginni n g");
printf("\n 6. Delete a node from End");
printf("\n 7. Delete a node from Middle");
printf("\n\n- -------------------------");
printf("\n 8. Display the list from Left to Right");
printf("\n 9. Display the list from Right to Left");
printf("\n 10.Exit");
printf("\n\n Enter your choice: ");
scanf("%d", &ch);
retu r n ch;
}

void cdll_cre a t elist(int n)

{
int i;
node *newnod e, *temp;
if(star t = = NULL)

103
{
nodect r = n;
for(i = 0; i < n; i+ + )
{
newno d e = getno d e();
if(star t = = NULL)
{
star t = newno d e;
newno d e -> left = star t;
newno d e -> rig h t = start;
}
else
{
newno d e -> left = start -> left;
newno d e -> right = star t;
star t -> left- > rig h t = newno d e;
star t -> left = newno d e ;
}
}
}
else
{
printf("\n List alrea dy exists..");
}
}

void cdll_display_left_righ t()

{
node *temp;
tem p = start;
if(star t = = NULL)
printf("\n Empty List");
else
{
printf("\n The conte n t s of List: ");
printf(" %d ", tem p -> data);
tem p = temp -> right;
while(te m p != start)
{
printf(" %d ", tem p -> data);
tem p = temp -> right;
}
}
}

void cdll_display_rig h t_left()

{
node *temp;
tem p = start;
if(star t = = NULL)
printf("\n Empty List");
else
{
printf("\n The conte n t s of List: ");
do
{
tem p = temp -> left;
printf("\t%d", temp -> data);
}while(te m p != start);
}
}

void cdll_inse r t_b e g()

{
node *newnod e;
newno d e = getno d e();
nodect r + + ;
if(star t = = NULL)
{

104
star t = newno d e;
newno d e -> left = star t;
newno d e -> right = star t;
}
else
{
newno d e -> left = star t -> left;
newno d e -> right = star t;
star t -> left -> right = newno d e;
star t -> left = newno d e ;
star t = newno d e;
}
}

void cdll_inse r t_en d ()

{
node *newnod e,*te m p ;
newno d e = getno d e();
nodect r + + ;
if(star t = = NULL)
{
star t = newno d e;
newno d e -> left = star t;
newno d e -> right = star t;
}
else
{
newno d e -> left = star t -> left;
newno d e -> right = star t;
star t -> left -> right = newno d e;
star t -> left = newno d e ;
}
printf("\n Node Inser t e d at End");
}

void cdll_inse r t_mi d()

{
node *newnod e, *temp, *prev;
int pos, ctr = 1;
newno d e = getno d e();
printf("\n Ente r the position: ");
scanf("%d", &pos);
if(pos - nodec t r > = 2)
{
printf("\n Position is out of ran g e..");
retu r n ;
}
if(pos > 1 && pos < = nodec t r)
{
tem p = start;
while(ctr < pos - 1)
{
tem p = temp -> right;
ctr + + ;
}
newno d e -> left = tem p;
newno d e -> right = tem p -> right;
tem p -> right -> left = newno d e;
tem p -> right = newno d e ;
nodect r + + ;
printf("\n Node Inser t e d at Middle.. ");
}
else
{
printf("position %d of list is not a middle position", pos);

}
}

105
void cdll_delet e_b e g()
{
node *temp;
if(star t = = NULL)
{
printf("\n No nodes exist..");
getch();
retu r n ;
}
else
{
nodect r- -;
if(nodec t r = = 0)
{
free(st a r t );
star t = NULL;
}
else
{
tem p = start;
star t = start -> right;
tem p -> left -> right = start;
star t -> left = tem p -> left;
free(t e m p );
}
printf("\n Node delet e d at Beginnin g..");
}
}

void cdll_delet e_last()

{
node *temp;
if(star t = = NULL)
{
printf("\n No nodes exist..");
getch();
retu r n ;
}
else
{
nodect r- -;
if(nodec t r = = 0)
{
free(st a r t );
star t = NULL;
}
else
{
tem p = start;
while(te m p -> right != star t)
tem p = temp -> right;
tem p -> left -> right = temp -> right;
tem p -> right -> left = temp -> left;
free(t e m p );
}
printf("\n Node delet e d from end ");
}
}

void cdll_delet e_mi d()

{
int ctr = 1, pos;
node *temp;
if( start = = NULL)
{
printf("\n No nodes exist..");
getch();
retu r n ;
}

106
else
{
printf("\n Which node to delete: ");
scanf("%d", &pos);
if(pos > nodec t r)
{
printf("\nThis node does not exist");
getch();
retu r n ;
}
if(pos > 1 && pos < nodect r)
{
tem p = start;
while(ctr < pos)
{
tem p = temp -> right ;
ctr + + ;
}
tem p -> right -> left = temp -> left;
tem p -> left -> right = temp -> right;
free(t e m p );
printf("\n node delet e d ..");
nodect r- -;
}
else
{
printf("\n It is not a middle position..");
getch();
}
}
}

void main(void)
{
int ch,n;
clrscr();
while(1)
{
ch = men u();
switch( ch)
{
case 1 :
printf("\n Ente r Numb e r of nodes to creat e: ");
scanf("%d", &n);
cdll_cre a t elist( n);
printf("\n List crea t e d . .");
brea k;
case 2 :
cdll_inser t_b e g ();
brea k;
case 3 :
cdll_inser t_e n d ();
brea k;
case 4 :
cdll_inser t_mid();
brea k;
case 5 :
cdll_delet e_b e g ();
brea k;
case 6 :
cdll_delet e_last();
brea k;
case 7 :
cdll_delet e_mi d();
brea k;
case 8 :
cdll_display_left_rig h t();
brea k;
case 9 :

107
cdll_display_rig h t_left();
brea k;
case 10:
exit(0);
}
getch();
}
}

6. 9. Link e d List Impl e m e n t a t i o n of Sta c k:

We can repr e s e n t a stack as a linke d list. In a stack push and pop

oper a tio n s are perfor m e d at one end called top. We can perfor m similar
oper a tio n s at one end of list using top point e r. The linke d stack looks as
show n in figure 6.9.1:

top
400
d at a n e xt
40 X
400

30 400
300

20 300
200
st art
100 10 200
100

Fi g u r e 6 . 9 . 1 . L i n k e d s t a c k
re pr e s e nt at io n

The pro g r a m for link e d list imp l e m e n t a t i o n of sta c k:

# includ e < st dio. h >

# includ e < co nio.h >
# includ e < st dlib. h >

stru ct stack
{
int data;
stru ct stack *next;
};

void push();
void pop();
void display();
typed ef struct stack node;
node *start = N U L L;
node *top = NULL;

node* getno d e()

{
stru ct stack *temp;
tem p = ( n o d e *) malloc( sizeof(nod e)) ;
printf("\n Ente r data ");

108
scanf("%d", &tem p -> dat a);
tem p -> next = NULL;
retu r n tem p;
}

void push(no d e *newno d e)

{
node *temp;
if( newno d e = = NULL )
{
printf("\n Stack Overflow..");
retu r n ;
}
if(star t = = NULL)
{
star t = newno d e;
top = newno d e;
}
else
{
tem p = start;
while( tem p -> next != NULL)
tem p = temp -> next;
tem p -> next = newno d e ;
top = newno d e;
}
printf("\n\n\t Data push e d into stack");
}

void pop()
{
node *temp;
if(top = = NULL)
{
printf("\n\n\t Stack unde rflow");
retu r n ;
}
tem p = start;
if( start -> next = = NULL)
{
printf("\n\n\t Popp e d elem e n t is %d ", top -> data);
star t = NULL;
free(top);
top = NULL;
}
else
{
while(te m p -> next != top)
{
tem p = temp -> next;
}
tem p -> next = NULL;
printf("\n\n\t Popp e d elem e n t is %d ", top -> data);
free(top);
top = temp;
}
}

void display()
{
node *temp;
if(top = = NULL)
{
printf("\n\n\t\t Stack is empty ");
}
else
{
tem p = start;
printf("\n\n\n\t\t Elem e n t s in the stack: \n");

109
printf("%5d ", tem p -> data);
while(te m p != top)
{
tem p = temp -> next;
printf("%5d ", tem p -> data);
}
}
}

char menu()
{
char ch;
clrscr();
printf("\n \tStack oper a tio n s using point e r s .. ");
printf("\n -----------**********-------------\n");
printf("\n 1. Push ");
printf("\n 2. Pop ");
printf("\n 3. Display");
printf("\n 4. Quit ");
printf("\n Ente r your choice: ");
ch = getch e();
retu r n ch;
}

void main()
{
char ch;
node *newnod e;
do
{
ch = men u();
switch(c h)
{
case '1' :
newno d e = getno d e();
push(n e w n o d e );
brea k;
case '2' :
pop();
brea k;
case '3' :
display();
brea k;
case '4':
retu r n ;
}
getch();
}while( ch != '4' );
}

6. 1 0 . Link e d List Impl e m e n t a t i o n of Que u e :

We can repr e s e n t a que u e as a linke d list. In a que u e dat a is delet e d

from the front end and inser t e d at the rear end. We can perfor m similar
oper a tio n s on the two ends of a list. We use two point e r s front and rear
for our linked que u e imple m e n t a t i o n .

The linke d que u e looks as show n in figur e 6.10.1:

110
fr o nt rear
100 400

10 200 20 300 30 400 40 X

100 200 300 400

Fi g u r e 6 . 1 0 . 1 . L i n k e d Q u e u e r e p r e s e n t a t i o n

The pro g r a m for link e d list imp l e m e n t a t i o n of qu e u e :

# includ e < st dio. h >

# includ e < st dlib. h >
# includ e < co nio.h >

stru ct que u e
{
int data;
stru ct que u e *next;
};

typed ef struct queu e node;

node *front = NULL;
node *rear = NULL;

node* getno d e()

{
node *temp;
tem p = (node *) malloc(sizeof(no d e)) ;
printf("\n Ente r data ");
scanf("%d", &tem p -> dat a);
tem p -> next = NULL;
retu r n tem p;
}

void insert Q()

{
node *newnod e;
newno d e = getno d e();
if(new no d e = = NULL)
{
printf("\n Queu e Full");
retu r n ;
}
if(front = = NULL)
{
front = newno d e ;
rea r = newno d e;
}
else
{
rea r -> next = newno d e;
rea r = newno d e;
}
printf("\n\n\t Data Insert e d into the Queu e..");
}

void delet eQ()

{
node *temp;
if(front = = NULL)
{
printf("\n\n\t Empty Queu e..");
retu r n ;

111
}
tem p = front;
front = front -> next;
printf("\n\n\t Delete d elem e n t from queu e is %d ", temp -> data);
free(t e m p );
}

void displayQ()
{
node *temp;
if(front = = NULL)
{
printf("\n\n\t\t Empty Queu e ");
}
else
{
tem p = front;
printf("\n\n\n\t\t Elem e n t s in the Queu e are: ");
while(te m p != NULL )
{
printf("%5d ", tem p -> data);
tem p = temp -> next;
}
}
}

char menu()
{
char ch;
clrscr();
printf("\n \t..Que u e oper a tio n s using point e r s .. ");
printf("\n\t -----------**********-------------\n");
printf("\n 1. Inser t ");
printf("\n 2. Delete ");
printf("\n 3. Display");
printf("\n 4. Quit ");
printf("\n Ente r your choice: ");
ch = getch e();
retu r n ch;
}

void main()
{
char ch;
do
{
ch = men u();
switch(c h)
{
case '1' :
insert Q();
brea k;
case '2' :
delet e Q();
brea k;
case '3' :
displayQ();
brea k;
case '4':
retu r n ;
}
getch();
} while(ch != '4');
}

112
113