25-08-2017, 09:32 PM
Circular Linked List
Circular.ppt (Size: 194.5 KB / Downloads: 715)
Circular Linked Lists
In linear linked lists if a list is traversed (all the elements visited) an external pointer to the list must be preserved in order to be able to reference the list again.
Circular linked lists can be used to help the traverse the same list again and again if needed. A circular list is very similar to the linear list where in the circular list the pointer of the last node points not NULL but the first node.
Circular Linked Lists
In a circular linked list there are two methods to know if a node is the first node or not.
Either a external pointer, list, points the first node or
A header node is placed as the first node of the circular list.
The header node can be separated from the others by either heaving a sentinel value as the info part or having a dedicated flag variable to specify if the node is a header node or not.
CIRCULAR LIST with header node
Header Node with Flag: In this case a extra variable called flag can be used to represent the header node. For example flag in the header node can be 1, where the flag is 0 for the other nodes.
struct node{
int flag;
int info;
struct node *next;
};
typedef struct node *NODEPTR;