OpenEuphoria

Re: Linked Lists

• Posted by Derek Parnell <ddparnell at bigpond.com> Aug 13, 2001
• 689 views

----- 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.