Mr.
Saqib Ubaid &
Mr. Muhammad Umer
Department of Computer Science,
KFUEIT
Data Structures & Algorithms
[COSC-2101]
Hadith of the day
• Abdullah ibn Umar (RA) reported:
The Messenger of Allah, Muhammad( َص َّلٰى ٱُهَّٰلل َع َلْيِه َو آِلِه َو َس َّلَمtook me by
the shoulder and said: Be in this world as though you were a stranger
or a wayfarer.” And Ibn Umar (may Allah be pleased with him) used to
say, “In the evening do not expect [to live until] the morning, and in the
morning do not expect [to live until] the evening. Take [advantage of]
your health before times of sickness, and [take advantage of] your life
before your death.
Source: Al-Bukhari Hadith No. 40
Circular Linked List
• A circular linked list is one which has no beginning
and no ending. The null pointer in the last node of a
linked list is replaced with the address of its first
node such a list is called circular linked list.
Graphical Representation
Circular Singly Linked List
Last node contains the address of the first node
First
10 1000 15 2000 20
4000
4000 1000 2000
SINGLE LINKED
LIST
500 200
45 100 60 35 N
Start
CIRCULAR LINKED LIST:-
45 100 60 200 35 400
400 100 200
Inserting a new node : Before inserting:
14 100 35 200 20 N
400 100 200
After inserting:
14 100 35 200 20 N
75 400
400 100
200
Delete a node from the list: before deletion:
35 400 48 300 46 500 30 N
200 400 300 500
after deletion :
35 300 46 500 30 N
200 300 500
In circular linked list we have three
functions. They are
• addcirq( )
• delcirq( )
• cirq_display( )
addcirq( ) :-
This function accepts three
parameters.
First parameter receives the
address of the first node.
The second parameter receives
the address of the pointer to the last
node.
Delcirq( ) :-
• This function receives two parameters.
The first parameter is the pointer to the front no
The second is the pointer to the rear.
front rear
10 17 16 5
OPERATIONS ON LINKED LISTS
The basic operations on linked lists are
1. Creation
2. Insertion
3. Deletion
4. Traversing
5. Searching
6. Concatenation
7. Display
• The creation operation is used to
create a linked list.
• Insertion operation is used to insert a
new node in the linked list at the
specified position. A new node may be
inserted at the beginning of a linked list ,
at the end of the linked list , at the
specified position in a linked list. If the
list itself is empty , then the new node is
inserted as a first node.
• Deletion operation is used to delete on
item from the linked list. It may be deleted
from the beginning of a linked list ,
specified position in the list.
• Traversing operation is a process of
going through all the nodes of a linked list
from one end to the another end. If we
start traversing from the very first node
towards the last node , It is called
forward traversing.
• If the traversal start from the last node
towards the first node , it is called back
word traversing.
• Searching operation is a process of
accessing the desired node in the list.
We start searching node –by-node and
compare the data of the node with the
key.
• Concatenation operation is the process
of appending the second list to the end
of the first list. When we concatenate
two lists , the resultant list becomes
larger in size.
• The display operation is used to print
each and every node’s information.
BASIC OPERATIONS ON A
LIST
• Creating a List
• Inserting an element in a
list
• Deleting an element from a list
• Searching a list
• Reversing a list
INSERTION AT THE BEGINNING
There are two steps to be followed:-
a) Make the next pointer of the node point
towards the first node of the list
b) Make the start pointer point towards this new
node
If the list is empty simply make the start pointer
point towards the new node;
INSERTING THE NODE IN A
SLL
There are 3 cases here:-
Insertion at the beginning
Insertion at the end
Insertion after a particular node
INSERTING AT THE END
Here we simply need to make the next pointer
of the last node point to the new node
INSERTING AFTER AN
ELEMENT
Here we again need to do 2 steps :-
Make the next pointer of the node to be inserted
point to the next node of the node after which you
want to insert the node
Make the next pointer of the node after which the
node is to be inserted, point to the node to be
inserted
DELETING A NODE IN
SLL
Here also we have three cases:-
Deleting the first node
Deleting the last node
Deleting the intermediate node
DELETING THE FIRST
NODE
Here we apply 2 steps:-
Making the start pointer point towards the 2nd
node
Deleting the first node using delete keyword
start
one two three
DELETING THE LAST
NODE
Here we apply 2 steps:-
Making the second last node’s next pointer point
to NULL
Deleting the last node via delete keyword
start
node1 node2
node3
DELETING A PARTICULAR NODE
Here we make the next pointer of the node
previous to the node being deleted ,point to
the successor node of the node to be deleted
and then delete the node using delete
keyword
node1 node3
node2
To be deleted
SEARCHING
Searching involves finding the required element in the
list
We can use various techniques of searching like linear
search or binary search where binary search is more
efficient in case of Arrays
But in case of linked list since random access is not
available it would become complex to do binary search
in it
We can perform simple linear search traversal
In linear searcheach node is
traversed till the data in the node matches
with the required value
REVERSING A LINKED
LIST
• We can reverse a linked list by reversing the
direction of the links between 2 nodes
Applications of linked list in
computer science
• Implementation of stacks and queues
• Implementation of graphs : Adjacency list representation of graphs
is most popular which is uses linked list to store adjacent vertices.
• Dynamic memory allocation : We use linked list of free blocks.
• Maintaining directory of names
• Performing arithmetic operations on long integers
• Manipulation of polynomials by storing constants in the node of
linked list representing sparse matrices
Applications of linked list in real
world
• Image viewer – Previous and next images are linked, hence can be
accessed by next and previous button.
• Previous and next page in web browser – We can access previous
and next url searched in web browser by pressing back and next
button since, they are linked as linked list.
• Music Player – Songs in music player are linked to previous and next
song. you can play songs either from starting or ending of the list.
Applications of circular linked
• Useful for implementation of queue. Unlike this implementation, we don’t need to maintain
two pointers for front and rear if we use circular linked list. We can maintain a pointer to the
last inserted node and front can always be obtained as next of last.
• Circular lists are useful in applications to repeatedly go around the list. For example, when
multiple applications are running on a PC, it is common for the operating system to put the
running applications on a list and then to cycle through them, giving each of them a slice of
time to execute, and then making them wait while the CPU is given to another application. It
is convenient for the operating system to use a circular list so that when it reaches the end
of the list it can cycle around to the front of the list.
• Circular Doubly Linked Lists are used for implementation of advanced data structures like
Fibonacci Heap.
