Data Structures Using C, 2nd Edition by Pearson

258 Data Structures Using C

4. Next(First) = ptr.

5. First = ptr.

}

The effect of the above algorithm is shown in Figure 6.21.

Fig. 6.21 Insertion of a node at the tail of a circular linked list without travel

First

ptr

First

ptr

First

ptr

It may be noted that in both the cases of insertion (at the head and tail), no travel of the circu-

lar linked list was made. Therefore, the new representation has removed the drawback of the ordinary

circular linked list. In fact, it offers the solution in the order of O(1).

6.4.2 Doubly Linked List

Another variation of linked list is a doubly linked list. It is a list in which each node contains two

links: leftLink ...