From: "Benjamin J. Tilly" <ben_tilly@...>
Date: 2001-06-02T02:23:29+09:00
Subject: [ruby-talk:16143] Re: linked list redux

Al Chou <hotfusionman@yahoo.com> wrote:
>> Wesley J Landaker wrote:
[...]
>This is premature, but since you posted something, so will I. <g>  I'm just
>gathering together what you guys have posted.  I suppose it doesn't need to 
be
>a subclass, but I guess I'm harping on the idea that if you want a linked 
list,
>the class you use should be called that....
>
I would not use this.

If something is called a linked list, it should be an efficient
implementation.  Several of these operations are O(n) when a true
linked list should be O(1).  The slow ones are insert_at,
insert_after, and tail.  OTOH last, which is supposed to be O(n),
is O(1).  What that means is that a naive translation of code that
uses linked lists will run with this implementation, but will be
very slow.
>
>class LinkedList < Array
>  def insert_at( pos, data )
>    self[pos, 0] = data
>    # (or self[pos..pos-1] but it's not really nice looking)
>  end
>
>  def insert_after( pos, data )
>    self[pos + 1, 0] = data
>  end
>
>  def head
>    return self[0]
>  end
>
>  def tail
>    return self[1..self.length]
>    # or:
>    # self[1..-1]
>  end
>
>  def last
>    return self[-1]
>  end
>end

The right way, if you really want a linked list, is to have
a data structure where each element of the list is a small
structure.  Create the basic linked list operations, and
then include Enumerable to get many of the iteration
constructs that people expect to see.

This will have the algorithmic characteristics of a linked
list.  It will, however, have considerable overhead due to
being implemented on top of a complex data structure.

That is why most people rethink linked lists entirely and
state their algorithms in terms of arrays.  For instance if
you want to turn an array into a head and a tail, just shift
to get the head and what is left is the tail.

Cheers,
Ben