CIRCULARLY LINKED LIST:
Singly linked list:
The Singly Linked List can be converted to a Circularly Linked List by connecting the last node in the singly linked list to the first node. It may be recalled that in the singly linked list, the last node has a NULL link. If this NULL link is replaced with the pointer to the head node, the list becomes circular. Circular linked lists have several advantages over the linear lists, first among which is regarding the accessibility of a node from other nodes.
From a node, all the other nodes can be reached by chaining through the list. Another advantage is regarding the deletion of a node in the list. To delete a particular node from the list, the predecessor of the node has to be determined so that the successor can be attached to it. Thus deletion of the node can be achieved easily. In the circularly linked list, the predecessor of a node can be found by traversing the list once.
A major disadvantage of circularly linked lists is that they can cause infinite loops. This possibility arises because, the list can be traversed continuously without encountering a null link. The detection of the end of the list is very important for the correct traversal of the list. for this, we use a special node called the head node or the list head. An added advantage of using such a node is that the list is never empty.
The end of the list can be detected by checking whether the current node is the head node or not. The traversal begins at the head node if the current node becomes the same as the head node during traversal, then it implies that the entire list has been traversed once. The while loop use to control the traversal appears as:
while (curr <> head) do instead of
while (curr <> NULL) do
Doubly linked list:
Note that the right link of the right-most node (tail node) contains the address of the head node and the left link of the head node points to the right-most node (tail node).
step 1: left(head) = tail step 2: right(tail) = head
Applications of Linked Linear Lists:
- Polynomial Manipulation
- Linked Dictionary
- Multiple-Precision Arithmetic