CIRCULAR LINKED LIST IN DATA STRUCTURES CLL

Circular linked list IN DATA STRUCTURES

2. Circular Linked List
single linked list - link field of the last node is
null.
circular linked list - link field of the last node
holds
the address of the first node.
HEA
D
1 2 3

3. Singly linked list
1 2
3X

4. Singly Circular linked list
1 2 3

5. Doubly linked
list
5
HEA
D
X1 X9

6. Doubly Circular linked
list
5
HEA
D
1 9

7. insertio
n

8. Singly Circular linked list – insert at front/end
Current=head
While(current.link!
=head)
Current=current.link
EndWhile
Current.link=newnode
Newnode.link=head
Head=newnode
1 2 3
HEA
D
curren
t

9. Singly Circular linked list – insert at front/end
Current=hea
d
While(current.link!
=head)
Current=current.link
EndWhile
Current.link=newno
de
Newnode.link=head
Head=newnode
1 2 3
HEA
D
curren
t
5
newnod
e
HEA
D

10. Insertion at the front/end
Algorithm
CIRCULAR_ADD_FRONT_END
(item)
Input: Header is the pointer to the front
of the circular list
Output: Item inserted at the front/end of the
list
Data Structure: Linked
list.
Steps
:
1.
2.
3.
4.
1.
2.
3.
5.
1.
2.
Newnode=malloc(node)
Newnode.data=item
Newnode.link=NULL
If(head=NULL)
Head=newnode
Newnode.link=newnode
Exit
Else
Current=head
While(current.link!=head)
1
.
Current=current.li
nk EndWhile
Current.link=newnod
e Newnode.link=head
Head=newnode
EndIf Stop
3.
4.
5.
6.
6.
7.

11. deletio
n

12. Singly Circular linked list – delete from front
Current=head Do
Prev=current
Current=current.link
While(current!
=head)
1 2 3
HEAD
curren
t

13. Singly Circular linked list – delete from front
Current=head Do
Prev=current
Current=current.link
While(current!
=head)
1 2 3
HEA
D
curren
t
pre
v

14. Singly Circular linked list – delete from front
Current=head Do
Prev=current
Current=current.link
While(current!
=head)
1 2 3
HEA
D
curren
t
pre
v

15. Singly Circular linked list – delete from front
Current=head Do
Prev=current
Current=current.link
While(current!
=head)
1 2 3
HEA
D
curre
nt
pre
v

16. Singly Circular linked list – delete from
front
Prev.link=current.link Head=head.link FREE (current)
1 2 3
HEA
D
curre
nt
pre
v

17. Singly Circular linked list – delete from
front
Prev.link=current.link Head=head.link FREE (current)
1 2 3
HEA
Dcurren
t
pre
v

18. Singly Circular linked list – delete from
front
Prev.link=current.link Head=head.link FREE (current)
1 2 3
HEA
Dcurren
t
pre
v

19. Singly Circular linked list – delete from
front
Prev.link=current.link Head=head.link FREE (current)
1 2 3
HEA
D
pre
v

20. Deletion from the front
Algorithm
CIRCULAR_DELETE_FRO
NT ()
Input: Header is the
pointer to the front of
the circular list
Output: Item deleted
from the front /end of
the list
Data Structure: Linked
list.
Steps
:
1.If(head=NULL)
1.Print(“List Empty”)
2.Exit
2.Else If( head.link=head)
1.Item=head.data
2.FREE (head)
3.Head=NULL
3.Else
1.Current=head
2.Do Prev=current
2.Current=current.link
3.While(current!=head)
4.Prev.link=current.link
5.Head=head.link
6.FREE (current)
1
.
4.EndI
f
5.Stop

21. Singly Circular linked list – delete from end
Current=head
While(current.link!
=header)
Prev=current
Current=current.link
EndWhile
1 2 3
HEA
D
curre
nt
prev

22. Singly Circular linked list – delete from end
Current=head
While(current.link!
=header)
Prev=current
Current=current.link
EndWhile
1 2 3
HEA
D
curren
t
pre
v

23. Singly Circular linked list – delete from
end
Prev.link=head FREE (current)
1 2 3
HEA
D
curren
t
pre
v

24. Singly Circular linked list – delete from
end
Prev.link=head FREE (current)
1 2 3
HEA
D
curren
t
pre
v

25. Singly Circular linked list – delete from end
Prev.link=head FREE (current)
1 2
HEA
D
pre
v

26. Deletion from the end
Algorithm
CIRCULAR_DELETE_END ()
Input: Header is the pointer to
the front of the circular list
Output: Item deleted from the
end of
the list
Data Structure: Linked list.
Steps
:
1.If(head=NULL)
1.Print(“List is Empty”)
2.Exit
2.Else If( head.link=head)
1.Item=head.data
2.FREE (head)
3.Head=NULL
4.Exit
3.Else
1.Current=head
2.While(current.link!
=head)
Prev=current
2.Current=current.link
1.EndWhile
2.Prev.link=head
3.FREE (current)
1
.
4.EndI
f
5.Stop