Sunday, March 10, 2013

Circular Linked List


Circular Linked List

A linked list where the link field of last node contains address of first node is called a circular linked list .It is represented as follows.

Circular linked list have certain advantageous over single linked list.


1.  Traversing is simple.

           In a single linked list, it is not possible to traverse the entire linked list starting from any node. In other words, if we start from first node only, we can visit all nodes. Starting from the middle node we cannot visit all nodes. However in circular linked list one can traverse the entire linked list starting from any node.

2.      Deletion requires less number of inputs in circular linked list over  single
linked list.

            In single linked list if we wish to delete a node, we require the address of that node and also we require the address of first node. This is because the predecessor of the node to be deleted had to be kept track off. However, in circular linked list, if we want to delete a node we require the address of that node. However, we do not require the address of first node. Since the initialization of the temp pointer which has to point to the predecessor node is made at deleted node itself  i.e. In single linked list if we require two address, one X, which is the address of node deleted, second is first, this is required because temp is initialized to first and moved it tempàlink=X.

            Where as in circular linked list we require only one address of X i.e. X, which is the address of node to be deleted. Here temp is initialized to X itself and moved till tempàlink=X.
           
            However there is a disadvantageous in circular linked list. If one is not careful while processing a circular linked list, then we can end up in an infinite loop. In circular linked list it is not possible to distinguish last node from other nodes since its link field also contain address .To over come  this we use a special node called head node at beginning of the linked list .The head node link field points to first node and first link field of last node contain address of head node. The data field of head node is unused. The circular linked list with head node is as follows:



No comments:

Post a Comment