linked list with cycle structure

Terry Reedy tjreedy at udel.edu
Thu Jan 8 01:08:03 CET 2009


David Hláčik wrote:

> so okay, i will create a helping set, where i will be adding elements
> ID, when element ID will be allready in my helping set i will stop and
> count number of elements in helping set. This is how long my cycled
> linked list is.

CPython now does this in printing and marshalling/pickling so that the 
following terminates instead of going into an infinite spin.

 >>> a=[1]
 >>> b=[2,a]
 >>> c=[3,b]
 >>> d=[4,c]
 >>> a.append(d)
 >>> a
[1, [4, [3, [2, [...]]]]]
 >>>

Sets cannot be recursive because members must be hashable.
Dict values do not have to be.  So
 >>> d={1:None}
 >>> d[1]=d
 >>> d
{1: {...}}
 >>>

> But what if i have another condition , and that is *i can use only
> helping memory with constant size* ? This means i am not able to
> create any set and adding elements there. I need to have a constant
> size variables . This is complication a complication for me.

Interesting problem.  If it is homework, there must be an answer.  Think 
time-space tradeoff.  However, this of really off-topic here.  It not 
only has nothing in particular to with Python, but an indefinitely long 
looping linked list is something very unlikely in a Python program since 
Python is based on array-type lists.

If you do write a solution in Python, you could, however, post it.

tjr




More information about the Python-list mailing list