1. Linked Lists
Does anyone have some good alternatives to the
standard
linked list implementation in C?
I'd be happy to see any code you can come up with.
Dr. Cage
__________________________________________________
Do You Yahoo!?
Yahoo! Auctions - Buy the things you want at great prices.
http://auctions.yahoo.com/
2. Linked Lists
Hi all,
can someone tell what a linked list is?
Chris
3. Re: Linked Lists
----- Original Message -----
From: "Chris Bensler" <bensler at telus.net>
To: "EUforum" <EUforum at topica.com>
Subject: Linked Lists
> can someone tell what a linked list is?
A linked list is a list in which each element is "linked" to the next
logical element. The logical sequence of the list is not necessarily the
same as the physical sequence. It usually is in some sorted order.
An example:
sequence LinkList
LinkList = {
{0, "Parnell"},
{1, "John"},
{2, "Derek"}
}
In this list, each entry is a 2-element sequence. The first of these
elements is the index to the next logical entry, and the second element is
the data. To find the start of the list, you need to locate the entry which
has no other entries pointing to it.
This is an example of a singly-linked list. The doublely-linked list is more
common because it is faster to traverse in either direction.
LinkList = {
{0,2, "Parnell"},
{1,3, "John"},
{2,0, "Derek"}
}
The difference here is that there is a double link - one forwards and one
backwards. To find the start of the list, find the element that has 0 as its
backward link. To go forward through the list, use the first element in each
entry, to go backwards find the end of the list (forward link is zero), and
use the backward links.
To make things even faster, many implementations add an extra element as the
first one. All this does is point to the head and tail of the list.
LinkList = {
{4,2},
{0,3, "Parnell"},
{2,4, "John"},
{3,0, "Derek"}
}
The awkward part is deleting and inserting entries. You have to update the
pointers everytime to make sure there is no break in the chain.
To add "Michael" in between "Derek" and "John" I would do this...
LinkList = append(LinkList, {0, 0, "Michael"})
i = length(LinkList)
a = 4 -- Index to Derek
b = 3 -- Index to John
-- "insert" Michael after Derek and before John
LinkList[i][1] = b
LinkList[i][2] = a
-- "update" Derek to point ot Michael
LinkList[a][1] = i
-- "update" John to point back to Michael
LinkList[[b][2] = i
The tricky bit is when adding (or deleting) to either end of the chain.
To add "Smith" to the end of the chain...
LinkList = append(LinkList, {0, 0, "Smith"})
i = length(LinkList)
a = LinkList[1][2] -- End of chain
-- "insert" Smith after the last entry
LinkList[i][2] = a
-- "update" last element to point to Smith
LinkList[a][1] = i
The usefulness of a doublely linked list is that for very large lists,
adding and deleting entries is faster than making a new copy of the updated
list. In Euphoria, it can be made even faster by predefining a number of
empty elements whenever you have to enlarge the list.
------------
Derek.
4. Re: Linked Lists
On Monday 13 August 2001 08:57, Derek Parnell wrote:
> From: "Chris Bensler" <bensler at telus.net>
> Subject: Linked Lists
>
> > can someone tell what a linked list is?
Good answer from Derek. I'll just add, Chris, since I know you
sometimes use GTK, that GLib has single and doubly-linked
lists "ready to use", and they work much like Euphoria sequences:
object myList
myList = NULL -- must assign a null pointer
myList = g_list_append(myList,"Some Stuff")
etc... also available is g_list_prepend.
myList = g_list_insert(myList,"More Stuff in the middle",1)
easier than Euphoria. note: the number is zero based, so
element 0 is the first on the list, etc.
There's also a g_list_sort(list,sortfunction), like custom_sort,
and a g_list_insert_sorted, which inserts in the correct place
to maintain the sort order., as well as g_list_find, which does
what you would expect it to. Probably some other stuff as well,
but my book doesn't list them.
Regards,
Irv
5. Re: Linked Lists
Thanks Derek,
Now why would one need to use such a cumbersome structure?
It must have some value, considering the overhead of implementing it.
Chris
6. Re: Linked Lists
Nevermind,
Irv answered for me. :)
They're basically the equivalent of a sequence.
Is there some other benefit of a linked list that I am missing
though?
Chris
> Thanks Derek,
> Now why would one need to use such a cumbersome structure?
> It must have some value, considering the overhead of implementing it.
>
> Chris
7. Re: Linked Lists
On Mon, 13 Aug 2001 08:17:04 -0700, Derek Parnell <ddparnell at bigpond.com>
wrote:
>----- Original Message -----
>From: "Chris Bensler" <bensler at telus.net>
>To: "EUforum" <EUforum at topica.com>
>Sent: Monday, August 13, 2001 10:24 PM
>Subject: Linked Lists
>> can someone tell what a linked list is?
>A linked list is a list in which each element is "linked" to the next
>logical element. The logical sequence of the list is not necessarily the
>same as the physical sequence. It usually is in some sorted order.
[Extensive examples deleted]
The key thing about linked lists in other languages is that they are
dynamic structures, allocated and expanded as needed rather than its
resources being statically declared at compile/load time. In Euphoria,
given that sequences already have this characteristic, I don't see a real
need for linked lists - any operation you can do on a linked list, I
believe I can do on a sequence, and usually it'll be clearer what I'm doing
with the sequence, and will require less code. The advantage to a
double-linked list in other languages is that it can be traversed in either
direction; again, this is something I can do with sequences in Euphoria.
I think that some people here - not all, by any means - fail to realize
just how useful the sequence data type is - most of the structures that one
learns about in first- or second-semester Computer Science classes (stacks,
queues, linked lists, trees, etc.) can be implemented fairly easily using
sequences - or don't need to be implemented in Euphoria, because a sequence
is more efficient. More, some complex data structures that appear in only
a few specialized languages (e.g., the association list of LISP) can also
be implemented fairly easily in Euphoria using sequences as a base. (Watch
this space; I am going to look at the data structure includes I wrote some
time ago, and re-release them, cleaned up if necessary. The current
versions of them are in the archive as zeitlin.zip, a bad choice of name.)
--
Jeff Zeitlin
jzeitlin at cyburban.com
(ILink: news without the abuse. Ask via email.)
8. Re: Linked Lists
There is not much to be gained in Euphoria by using a linked list.
They are usually used to connect together pieces of RAM. Typically a program
would allocate some RAM, put the data it needs into that allocation and then
link it in to the chain. They do this either because the chain must be in a
specific sorted order, or just to remember where the RAM was so they can
deallocate it later on.
You can still do this with Euphoria, but the sequence data type is a lot
easier to work with. However, if you are talking about really huge amounts
of data, with lots of random insertions and deletions in real-time, then a
linked list could still be faster to use than sequences.
----- Original Message -----
From: "Chris Bensler" <bensler at telus.net>
To: "EUforum" <EUforum at topica.com>
Sent: Tuesday, August 14, 2001 1:33 AM
Subject: Re: Linked Lists
>
> Nevermind,
>
> Irv answered for me. :)
> They're basically the equivalent of a sequence.
> Is there some other benefit of a linked list that I am missing
> though?
>
> Chris
>
> > Thanks Derek,
> > Now why would one need to use such a cumbersome structure?
> > It must have some value, considering the overhead of implementing
it.
> >
> > Chris
>
>
>
>
>
