cyclic doubly link list

[free2cric]

Hi,
how to detect head and tail in cyclic doubly link list ?
Thanks,
Cric

 

[Simon Biber]

Hi,
how to detect head and tail in cyclic doubly link list ?
Thanks,
Cric

Why do you need to detect its head and tail?

The simplest way would be to keep a pointer to the head and tail, and
compare the address of the current element with those pointers.

Another way would be to keep a flag inside the link node structure
describing what type of node it is (head node, tail node, middle node).

 

[Chris Dollin]

Hi,
how to detect head and tail in cyclic doubly link list ?

(a) this is not a C problem.

(b) if it's a cyclic (doubly-)linked list, surely it hasn't
/got/ a head and a tail?

 

[Michael Mair]

(a) this is not a C problem.
Agreed.


(b) if it's a cyclic (doubly-)linked list, surely it hasn't
/got/ a head and a tail?

Not necessarily; sometimes you need the notion of head and tail
or appropriate sentinel list nodes for a part of the algorithms
working on your data structure and cyclicality for others.
However, AFAIR whenever I have seen that, it involved head and
tail nodes not carrying information of any kind and flags to
signal isHead/isTail; I do not remember whether the cyclicality
was really necessary in these cases.


Cheers
Michael

 

[Ben Pfaff]

(b) if it's a cyclic (doubly-)linked list, surely it hasn't
/got/ a head and a tail?

In my experience a circular linked list usually has some
distinguished node, if only because that's the node at which new
nodes are added to the list. (Usually it's just one node, not
two.)

 

[Chris Dollin]

In my experience a circular linked list usually has some
distinguished node, if only because that's the node at which new
nodes are added to the list. (Usually it's just one node, not
two.)

Yes - but the OP wanted to know how to /detect/ the head and
tail of the doubly-linked list.

Either it's external to the list (a reference to some specific
element), in which case if you don't know it you can't detect
it; or there's some marker in the list elements, which the OP
hasn't mentioned and which in any case would make it signitficantly
more than just a (cyclic) (doubly-) linked list.