VietMX Staff asked 3 years ago
A circularly linked list may be a natural option to represent arrays that are naturally circular, e.g:
- the corners of a polygon,
- a pool of buffers that are used and released in FIFO (“first in, first out”) order, or
- a set of processes that should be time-shared in round-robin order.
In these applications, a pointer to any node serves as a handle to the whole list.
With a circular list, a pointer to the last node gives easy access also to the first node, by following one link. Thus, in applications that require access to both ends of the list (e.g., in the implementation of a queue), a circular structure allows one to handle the structure by a single pointer, instead of two.
A circular list can be split into two circular lists, in constant time, by giving the addresses of the last node of each piece. The operation consists in swapping the contents of the link fields of those two nodes. Applying the same operation to any two nodes in two distinct lists joins the two list into one. This property greatly simplifies some algorithms and data structures, such as the quad-edge and face-edge.
In overall, circularly linked lists can be useful if you want to iterate through the entire list starting from a random iterator or inserting in any position. They simplify the algorithms for those operations as you don’t have to account for the beginning or end of the list.
