[OT] Linked list fixup [was: Fast DES IP]

From: Francois Grieu (fgrieu_at_francenet.fr)
Date: 12/09/04 

Date: Thu, 09 Dec 2004 11:52:32 +0100

In article <873byfvmlc.fsf@nonospaz.fatphil.org>,
 Phil Carmody <thefatphil_demunged@yahoo.co.uk> wrote:

> "Douglas A. Gwyn" <DAGwyn@null.net> writes:
> > There is a related XOR trick sometimes used to
> > traverse a linked list in either forward or
> > reverse direction with only a single link field
> > in each node, with one extra field of information
> > for the whole list needed to get started (that
> > can be stored in a list header). If you aren't
> > familiar with this trick, it is a nice little
> > exercise to figure it out.
>
> Now that (as far as I know) _is_ Knuth's.

While I fail to identify which trick / Knuth's algo
this is, I can't resist a little [non-crypto] puzzle
on linked lists. 

---
We have a non-empty linked list in RAM, of unknown size n,
and a pointer to the head node. Instead of nicely ending
with a node having a NULL "next" field, the list is
"loopy" and the last node in the list has a "next"
field that points to some unknown node in the list.
Find an O(n) algorithm using O(1) memory that fixes
the list, changing the "next" field of the last
element to NULL.
Note: solutions that store an extra bit of info in each
node do not count as O(1) memory.
   Francois Grieu

Relevant Pages

  • Re: race on multi-processor solaris
    ... > Use a lock-free garbage collector. ... So what does protect the memory attached to the node? ... >>such linked lists, ...
    (comp.unix.solaris)
  • Re: reuse memory and unset seems slo
    ... > so to reuse memory, do I have to reassign new data to original name ... Nope - tcl lists are not implemented as linked lists, ...
    (comp.lang.tcl)
  • Re: Linked list allocation
    ... and delete_item frees that memory. ... An alternative I thought of was that add_item should allocate a block, ... for inserting and deleting nodes from linked lists. ...
    (comp.lang.c)
  • Re: How to read columns from a file?
    ... You need to specify whether the whitespace is tab (single tab ... Actually you can use the same trick to generate the substrings: ... But the advantage of using two collated lists is that you can ... another slight trick to fix, exercise for OP asking help with homework. ...
    (comp.lang.lisp)
  • Re: Linked list allocation
    ... where add_item allocates memory for a new list item and returns it (or ... and delete_item frees that memory. ... for inserting and deleting nodes from linked lists. ...
    (comp.lang.c)