From: "Benjamin J. Tilly" <ben_tilly@...>
Date: 2001-06-01T07:14:13+09:00
Subject: [ruby-talk:16099] Re: linked list redux

>===== Original Message From Avi Bryant <avi@beta4.com> =====
>On Fri, 1 Jun 2001 05:58:51 +0900
>"Wesley J Landaker" <wjl@mindless.com> wrote:
>
>> Unless you are just trying to make a linked list for the academic fun
>> of it, there really isn't much reason to use one.
>>
>> Instead, just use Ruby's built in Array. Remember, elements in a Ruby
>> array are just references to the real objects, the array itself doesn't
>> actually hold their data. Since the array is growable, searchable,
>> sortable, etc, you have all the benefits of a linked list. =)
>
>If you were doing a lot of insertions and removals on large lists, a
>linked list would probably be a fair bit faster, since I'm pretty sure the
>Array implementation has to do a lot of copying in such cases.

Most of the time when people want to use linked lists, they
are not actually doing much of that.

Alternately if they are, it is usually possible to rework
the design to be list oriented.  For instance instead of
walking a linked list and removing things you don't want,
take an array and producing a new one with find_all.

This is not always possible, of course.  But it is more
often than not.

>But I would still recommend using an Array until you were sure that it was
>a performance problem.

In fact building a linked list is often penny-wise and
pound-foolish.  Algorithmically the linked list may be
better, but the overhead of using a custom built class
as a data type can lose all of your hard-earned savings.

Again, it is not always true.  But as a general rule an
Array combined with trying to take a list-oriented
approach to problems is generally a "good enough"
version of a linked list.

Cheers,
Ben