Circular Linked Lists

Circular Linked List

The following is taken directly from: https://cathyatseneca.gitbooks.io/data-structures-and-algorithms/content/lists/circular_linked_list.html

Another method of implementing a linked list involves using a circular form so that the next_ pointer of the last node points back to the first node.

Advantages of a circular linked list

  • Some problems are circular and a circular data structure would be more natural when used to represent it. (For example, a computer typically arranges its tasks in a circular queue and them timeslices each one repeatedly.)
  • The entire list can be traversed starting from any node (traverse means visit every node just once)
  • fewer special cases when coding(all nodes have a node before and after it)

Disadvantages of a circular linked list

  • Depending on implementation, inserting at start of list would require doing a search for the last node which could be expensive.
  • Finding end of list and loop control is harder (no NULL's to mark beginning and end)

Visual Representation

Below is a picture of a circular linked list. Because the structure is circular, the definition of the head node (shown with an additional pointer) is somewhat arbitrary.
Circular Linked List