Thread: Circle linked list

one circle linked list is there how to find the starting node (first node) of the list

the list.

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 NIL 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:

myList.tail^.next := myList.head



The following is a procedure for inserting a node at the front of a circular linked list:

Procedure CInsertFirst( var Head:ListType; X:InfoType);

var

NewNode:ListType; {Pointer to new node created}

begin

new(New Node); {Obtain a new node}

NewNode^.Info: = X; {Store the information in the node}

NewNode^.Link: = Head^.Link; {next node of the tail is linked to the head:}

Head^.Link: = NewNode {Set Head to point to new node}

end;



Advantages:

Each node is accessible from any node.
Address of the first node is not needed.
Certain operations, such as concatenation and splitting of string, is more efficient with circular linked list.
Disadvantage:

Danger of an infinite loop !

Hold the address of the first element in a private / protected member variable.
Create function IsFirst which compares the address of the element passed against the member variable address.