Go to the Next or Previous section, the Detailed Contents, or the Amiga E Encyclopedia.


9.6 Linked Lists

E-lists and E-strings have a useful extension: they can be used to make linked lists. These are like the lists we've seen already, except the list elements do not occupy a contiguous block of memory. Instead, each element has an extra piece of data: a pointer to the next element in the list. This means that each element can be anywhere in memory. (Normally, the next element of a list is in the next position in memory.) The end of a linked list has been reached when the pointer to the next element is the special value NIL (a constant representing zero). You need to be very careful to check that the pointer is not NIL, or else strange things will happen to your program...

The elements of a linked list are E-lists or E-strings (i.e., the elements are complex typed). So, you can link E-lists to get a `linked list of E-lists' (or, more simply, a `list of lists'). Similarly, linking E-strings gives `linked list of E-strings', or a `list of strings'. You don't have to stick to these two kinds of linked lists, though: you can use a mixture of E-lists and E-strings in the same linked list. To link one complex typed element to another you use the Link function and to find subsequent elements in a linked list you use the Next or Forward functions.

Link(complex1,complex2)
Links complex1 to complex2. Both must be an E-list or an E-string, with the exception that complex2 can be the special constant NIL to indicate that complex1 is the end of the linked list. The value complex1 is returned by the function, which isn't always useful so, usually, calls to Link will be used as statements rather than functions.

The effect of Link is that complex1 will point to complex2 as the next element in the linked list (so complex1 is the head of the list, and complex2 is the tail). For both E-lists and E-strings the pointer to the next element is initially NIL, so you will only need to use Link with a NIL parameter when you want to make a linked list shorter (by losing the tail).

Next(complex)
Returns the pointer to the next element in the linked list. This may be the special constant NIL if complex is the last element in the linked list. Be careful to check that the value isn't NIL before you dereference it! Follow the comments in the example below:

  DEF s[23]:STRING, t[7]:STRING, lt[41]:LIST, lnk
  /* The next two lines set up the linked list "lnk" */
  lnk:=Link(lt,t)  /* lnk list starts at lt and is lt->t    */
  lnk:=Link(s,lt)  /*   Now it starts at s  and is s->lt->t */
  /* The next three lines follow the links in "lnk"  */
  lnk:=Next(lnk)   /*   Now it starts at lt and is lt->t    */
  lnk:=Next(lnk)   /*   Now it starts at t  and is t        */
  lnk:=Next(lnk)   /* Now lnk is NIL so the list has ended  */

You may safely call Next with a NIL parameter, and in this case it will return NIL.

Forward(complex,expression)
Returns a pointer to the element which is expression number of links down the linked list complex. If expression is one, then a pointer to the next element is returned (just like using Next). If it's two a pointer to the element after that is returned, and so on.

If expression is greater than the number of links in the list the special value NIL is returned.

Since the link in a linked list is a pointer to the next element you can look through the list only from beginning to end. Technically this is a singly linked list (a doubly linked list would also have a pointer to the previous element in the list, enabling backwards searching through the list).

Linked lists are useful for building lists that can grow quite large. This is because it's much better to have lots of small bits of memory than a large lump. However, you need only worry about these things when you're playing with quite big lists (as a rough guide, ones with over 100,000 elements are big!).


Go to the Next or Previous section, the Detailed Contents, or the Amiga E Encyclopedia.