Data Structure Lecture 7

Problem to be Solved
 Multiple processes want a service of a
single resource
 Each process will use the resource for a
fix amount of time and then the next
resource will start using it.
 The process just used the resource will
go to the end
 We have to assure that

 Multiple processes want a service of a single
resource.
 Each process will use the resource for a fix
amount of time and then the next process
will start using it.
 The process just used the resource will go to
the end.
 We have to assure that
 No process accesses the resource before all the
other processes did.
 Therefore

 We want to arrange all these processes
in such a way that they form a ring.
 Now the question is
 in which data structures such a processes
will be arranged so that they form a ring.
 The data structures used for this type of
problems is
 Circular Lists

Circular Lists
 In a circular lists nodes form a ring.
 The list is finite and each node has
successor.
 In circular lists the tail of the list is
always pointing to the head.
 The external pointer, points to the
current "tail" of the list, then the "head"
is found trivially via tail->next.

Circular Lists (Linked Lists)
Operations
 The common operations on circular lists are:
1. AddToCLLHead(x) Inserts element x in front of the
circular linked list .
2. AddToCLLTail(x) Inserts element x at the end of
the circular linked list.
3. DeleteFromCLLHead() Deletes the first element
of the circular linked list.
4. DeleteFromCLLTail() Deletes the last element of
5. Delete(x) Deletes the node of value x from the
circular linked list.
6. Find(x) Find the entry x in the circular linked list.
7. print() prints the contents of the circular linked list.
8. And so on i.e.as many operations as you
required

Operations AddToCLLHead(x)
tail
tail
2 1
1

tail

2 1
3

tail

2 1
4 3

 Two cases must be considered to add the
node in front of the circular linked list.

1. Either we are creating the first node of the circular
linked list or

1. We are inserting the node in front of the existing

 First Case: Creating first node of a circular
linked list.
 We follow the following steps to create the first node
of the circular linked list.
1. Check the value of the tail of the list.
If this value is null it means we are creating the first node of
2. An empty node is created.

It is empty in the sense that the program performing
insertion does not assign any values to the data members of
the node.

3. The node's info member is initialized to a particular
value.
7

tail
4. Since it is the only node of the circular linked list
therefore its next member will be initialized to point to
the node itself.
5. Since it is the only node of the circular linked list
therefore tail points to this node of the circular linked
list.

 Second Case: Inserting node in front
of the existing circular linked list:
 We follow the following steps to insert the
node in front of the existing circular linked
list.
1. Check the value of the tail of the circular list.
If this value is not null it means we are
inserting node in front of the existing

7

tail


It is empty in the sense that the program
performing insertion does not assign any values
to the data members of the node.
8 7

tail
value.

4. Because the node is being included at the front of the list, the
next member becomes a pointer to the first node on the list,
i.e. the node to which next of tail pointing.

8 7

tail
5. The new node precedes all the nodes on the list, but this fact
has to be reflected, otherwise the new node is not accessible.
Therefore next of tail is updated to become the pointer to the
new node

Operations AddToCLLTail(x)
tail
tail
1 2
1

tail

2 3
1

tail

3 4
1 2

 Two cases must be considered to add the
node at the end of the circular linked list.

1. Either we are creating the first node of the circular
linked list or

1. We are inserting the node at the end of the
existing circular linked list.
 The first case is exactly similar as we
discussed in AddToCLLHead(x) operation.

 Second Case: Inserting node at the end of
the existing circular linked list:
 We follow the following steps to insert the node in
front of the existing circular linked list.
1. Check the value of the tail of the circular list.
If this value is not null it means we are inserting
node at the end of the existing circular linked list.

8 7

tail


It is empty in the sense that the program
performing insertion does not assign any values
to the data members of the node.

8 7 9
tail

value.

4. Because the node is being included at the end of the list, the
next member becomes a pointer to the first node on the list,
i.e. the node to which next of tail pointing.

8 7 9
tail tail

5. Since the new node will becomes the last node of the list,
therefore the next of tail will set to point to the new node.

6. Since the new node will becomes the last node of the list but
this fact must be reflected in the list, therefore the tail will set to

Implementation of Circular
Lists
 In an implementation of a circular list we can use
only one permanent pointer, tail.
template<class T>
class CircularLinkedList {
private:
Node<T> *tail; //pointer to last node of a list
public:
CircularLinkedList() {
tail = 0;
}
~CircularLinkedList(); Continue on next slide…

Lists
bool isEmpty() {
if (tail == 0) return true //Circular list is empty;
}
void addToCLLHead(T el); //inserts an element in front of circular list
void addToCLLTail(T el); //inserts an element at the end of circular list
void deleteFromCLLHead(); //delete a node from the front of a circular list
void deleteFromCLLTail(); //delete a node from the end of a circular list
void CLLDelete(T el); //delete a node from circular list whose value is el
Node *CLLFind(T el); //Find the node from circular list whose value is el
//and returns its pointer.
void CLLprints(); //prints the contents of a circular list
bool CLLIsInList(T el); //check that an element el exists in a circular list or not
};

Lists
void template<class T> CircularLinkedList::addToCLLHead(T el )
{ if (isEmpty) //first node of a list tail
{ tail = new Node<T>(el);
tail -> next = tail; 1

}
else // Insert node in front of the circular list
tail -> next = new Node<T>(el, tail->next);
tail
}
2 3
4 1

Lists
void template<class T> CircularLinkedList :: addToCLLTail(T el )
{ if (isEmpty) //first node of a list tail
{ tail = new Node<T>(el);
tail -> next = tail; 1

}
else // Insert node at the end of the list
{ tail -> next = new Node<T>(el, tail->next); tail
tail
tail = tail -> next
2 3 4
} 1
}

Circular List Variant
 There is one problem with the circular list we
discussed so far.
 Guess What?
 Problem will be with the functions which
deletes a node from circular list.
 A member function for the deletion of the tail
node requires a loop so that tail can be set
after deletion to its predecessor.
 A member function for the deletion of the
node of particular value also requires a loop
so that predecessor of that node will be
connected to the successor of that node.

Circular List Variant
 The use of loop is inefficient if circular list is
very long or if delete operations are called
frequently.
 Moreover processing data in the reverse
order is not very efficient.
 To avoid the problem and still be able
 To insert and delete nodes at the front and at
the end of the circular list without using a
loop, a doubly linked circular list can be
used.

Doubly Linked Circular List
 This list forms two rings:
 One going forward through next members
and

 One going backward through prev
members tail
a b c d

Lab Exercise
 Implement the template class for circular list
with following member functions.
1. A function which inserts node in front of
circular list.
2. A function which inserts node at the end of
linked circular list
3. A function which removes a node from the
front of circular list.
4. A function which removes a node from the
end of circular list.

Lab Exercise
5. A function which removes a node of
particular value from circular list.
6. A function which finds a node of
particular value from circular list.
7. A function which prints the contents of
circular list.

Data Structure Lecture 7

Recommended

More Related Content

What's hot (19)

Viewers also liked (12)

Similar to Data Structure Lecture 7 (20)

More from Teksify (11)

Data Structure Lecture 7