CEG's Linux User Group

CIRCULARLY SINGLY LINKED LIST

Introduction :

A singly linked circular list is a linked list where the last node in the list points to the first node in the list. A circular list does not contain NULL pointers. A good example of an application where circular linked list should be used is a timesharing problem solved by the operating system. In a timesharing environment, the operating system must maintain a list of present users and must alternately allow each user to use a small slice of CPU time, one user at a time. The operating system will pick a user, let him/her use a small amount of CPU time and then move on to the next user, etc. For this application, there should be no NULL pointers unless there is absolutely no one requesting CPU time.

The insert, delete and search operations are similar to the singly linked list. In circular linked list, we should always maintain that the next node of the tail is linked to the head after the insertion and deletion operations.

Advantages:

• Given any node, we can traverser the entire list.

• Certain operations, such as concatenation and splitting of string, is more efficient with circular linked list.

Disadvantage:

• Danger of an infinite loop ! (The header node is used to prevent infinite loop)

Circularly singly linked list operations :

* Inserting a node (new) in the beginning when the list is empty

* Inserting a node (new) in the beginning when the list is not empty

* Inserting a node (new) in the end of the list

Let end1 and end2 be the position of the end pointer before and after insertion respectively.

* Inserting a node (new) in the middle of the list

To insert a node in the middle, the list is traversed till the position where the node to be inserted is reached using a temp node. Here, the above code inserts the new node after the temp node.

* Deleting a node from the list

To delete a node in the end, traverse the list till the last node is reached using temp pointer. The pointer prev is made to point the node before the node which is to be deleted. The deletion of 4 is shown below.