linked list with cycle structure
Terry Reedy
tjreedy at udel.edu
Wed Jan 7 19:08:03 EST 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