Editing Linked list (section)

===Circularly linked vs. linearly linked===

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 [[data buffer|buffers]] that are used and released in [[FIFO (computing and electronics)|FIFO]] ("first in, first out") order, or a set of processes that should be [[time sharing|time-shared]] in [[round-robin scheduling|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 data structure|quad-edge]] and [[face-edge data structure|face-edge]].

The simplest representation for an empty ''circular'' list (when such a thing makes sense) is a null pointer, indicating that the list has no nodes. Without this choice, many algorithms have to test for this special case, and handle it separately. By contrast, the use of null to denote an empty ''linear'' list is more natural and often creates fewer special cases.

For some applications, it can be useful to use singly linked lists that can vary between being circular and being linear, or even circular with a linear initial segment. Algorithms for searching or otherwise operating on these have to take precautions to avoid accidentally entering an endless loop. One [[Cycle detection|well-known method]] is to have a second pointer walking the list at half or double the speed, and if both pointers meet at the same node, a cycle has been found.