1
$\begingroup$

Is a singly-linked list that contains a cycle considered a corrupted data structure or is there some practical use for it?

(You could argue that a car without its front shield is not corrupted, if the owner intends for it to be like that, so lets understand the word "corrupted" in a sense of "damaged into state that it is useless".)

One of the possible ideas that I got is that it can represent some sort of a computation: the initial "non-cycled head" of the list can be viewed as the initialisation phase, whereas the "cycled tail" can serve as a never-ending computation. However, this reasoning is a bit Texas Sharp-shooter fallacy to me.

Any ideas?

$\endgroup$
  • 2
    $\begingroup$ It is called circular linked list, and it is used, but listing possible usages is overwhelming and not helpful. Even if this is not intention, when cycle occurs it might be desired effect or very nasty error - it depends on particular application. $\endgroup$ – Evil Dec 20 '15 at 20:24
  • $\begingroup$ That is a very good comment indeed! I did not think of a case when the whole list is one cycle and no elements of the list are outside of it. I am pretty sure that this scenario has some good uses. But what about the case that has some elements "before" the cycle starts? $\endgroup$ – Daniel Lovasko Dec 20 '15 at 20:37
  • $\begingroup$ Isn't a circular singly linked list is same as Cyclic graph with only one edge per node? $\endgroup$ – Ankur Dec 21 '15 at 4:46
  • $\begingroup$ Have you read Wikipedia? Why do you think that a circular list should be “corrupted” anyway? $\endgroup$ – Gilles Dec 26 '15 at 17:05
2
$\begingroup$

In the case of circular linked list - this might be a buffer, neat structure to handle operations that must be consecutive or form a ring (like in parallel programming).

What if not the whole list is cycle?
This might be intended like conflict resolving, and thanks to cycle it will not go further.
It might be the case that every operation changes state so there is cycle, but it will eventually resolve.

If you write a turn-based game with general loop, there might be cycle if user can do something multiple times per turn. So here it is intended.

And totally not constructive - cycle came from bug, so it pushes application into infinite computation.

$\endgroup$
0
$\begingroup$

The Hamiltonian cycle problem asks for a cycle connecting all nodes. In this case the solution is a full circular linked list. However a modified version of the problem may ask that a particular connected subset must not form a cycle (so just a Hamiltonian path) while the others must. The solution will therefore be a linked list with a cycle.

I guess this can be useful in a graph problem where a particular subset of nodes form a connected path between the head node and the connected cycle of nodes. An example is to have the head node at the borders of city A, a path from city A to B through the desert, and connected nodes in city B.

                   5 6
     0 - 1 2 3 - 4     7
                   9 8
 city A  desert   city B
$\endgroup$
0
$\begingroup$

One particular example that I personally like and would like to share: cyclic linked lists can be useful when dealing with non-strict functional languages.

One can represent cyclic lists with recursive functions or recursive data structures and the latter can be more efficient performance-wise. A couple examples in Haskell:

(1) The $repeat$ function produces an infinite list consisting of $x$'s only: [x, x, x, ...].

repeat x = x:repeat x            -- recursive function representation
repeat x = xs  where xs = x:xs   -- recursive data structure representation

(2) The $iterate$ function returns an infinite list of repeated applications of $f$ to $x$: [x, f x, f (f x), ...].

iterate f x = x:iterate1 f (f x)            -- recursive function repr.
iterate f x = xs  where xs = x : map f xs   -- recursive data structure repr.

The performance gain can vary significantly for the above examples.

Examples are taken from the book "Thinking Functionally with Haskell" (2015) by Richard Bird (pp. 212 - 213).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.