linked list with cycle structure

[David Hláèik]

dictionary with cycle structure

Hello guys,

I have a linked list where *number of elements is unlimited* and
**last element points on random (can be first, last, in middle ,
anywhere) element within linked list** - this is important . My goals
is to create an architecture /scheme for **algoritmus which will count
total number of elements** of such linked list.
Yes , maybe it sounds strange, but we need to implement this and i
would be very gladfull for your toughts.

Thanks in advance and wishing you a sucessfull year!

David

 

[Diez B. Roggisch]

dictionary with cycle structure

Hello guys,

I have a linked list where *number of elements is unlimited* and
**last element points on random (can be first, last, in middle ,
anywhere) element within linked list** - this is important . My goals
is to create an architecture /scheme for **algoritmus which will count
total number of elements** of such linked list.
Yes , maybe it sounds strange, but we need to implement this and i
would be very gladfull for your toughts.

Time for homework again? Last time sorting in O(n), now this. How about you
try something yourself and show us the results - then we might comment on
enhancements or problems.

Diez

 

[Terry Reedy]

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

 

[Robert Kern]

Interesting problem. If it is homework, there must be an answer.

It's also an interview question I've seen reasonably often, particularly with
that last complication.

--
Robert Kern

"I have come to believe that the whole world is an enigma, a harmless enigma
that is made terrible by our own mad attempt to interpret it as though it had
an underlying truth."
-- Umberto Eco

 

[Diez B. Roggisch]

Hi,

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.

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.

This isn't to hard - think about what you are really interested in - knowing
if *all* other elements are already counted, or a specific one? You can get
away with only one, to detect the cycle and abort.

Diez