lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]

Phil Bewig wrote:
I suppose it's fair to say that the three fundamental data
structures in computing are arrays, lists, and hash tables
(I still remember how amazed I was when I first learned
about hash tables, almost thirty years ago -- they seemed
like magic them, and sometimes still do today).  It's also
probably fair to say that most imperative languages are
built around arrays, most functional languages are built
around lists, and most scripting languages are built around
hash tables.  And even further, it's probably fair to say
that all three data structures can do a reasonable job of
simulating each other, so whichever one your language gives
you, it's always possible to get your task written.  But
the three are fundamentally different, with varying strengths
and weaknesses, and there is no reason to say that lua uses
hash tables, so linked lists are somehow unclean.

I note that all three people who responded on the mailing
list objected to my use of the list data structure.  That
surprises me.  Lists are intrinsically ordered, tables are
intrinsically unordered.  Lists take one object per node,
tables take two objects, key and value, per node.  Lists
and tables are just ... different.  Is there some reason
lua people don't like lists?  Is there some unmentionable
tar pit you are all trying to steer me away from?

Hello Phil

Since you are a self-proclamed beginner, you may have missed the point that there is actually two kinds of tables in Lua, with different internal management: the hash table that you mention, with key/value pairs, unordered; and the array, using consecutive implicit numbers starting a 1 as "keys", implemented as such, ie. with direct access to the value by its index, without collision, and of course ordered (there is a table.sort function...).

Actually, both kinds of tables have the same syntax and Lua manage the difference transparently; you can even mix them freely: entries with string keys and sparse indexes are hashed, entries with indexes (keys) from 1 to n (without gap) are indexed.

Eg. taken from the manual:

x = 2
g = 3.1415926535897932384
f = function (p) return p * 5 end
a = {[f(1)] = g; "x", "y"; x = 1, f(x), [30] = 23; 45}
-- Dump the array part of the table, by index order
for i, v in ipairs(a) do
  print(i, v)
-- Dump the whole table (including the array part) in random order
for i, v in pairs(a) do
  print(i, v)

Note that the array can be built in any order:
a = { [3] = 23, [1] = 2, [2] = 213 }
is OK.
a = { [3] = 23, [4] = 2, [2] = 213 }
isn't OK, because index 1 is missing.

Now to your linked list:
I believe you can implement it with arrays, because the table library offers functions like table.insert and table.remove. The language offers direct access to a value, and the basic library offers iterators.
This way, you can shift entries as needed.
I don't know if it is as efficient as a C linked list, but I trust it is quite efficient, not moving data around, just indexes.


Philippe Lhoste (Paris -- France)
Professional programmer and amateur artist (outdated) (in French, for files to download)