BBC BASIC Programmers' Reference

by Richard Russell, May 2006

Structures provide a convenient means to create and manipulate linked lists, because they allow the content of each node in the list to be clearly described.

I will illustrate the steps required to create, search and read a linked list of structures using the example of an insertion sort. Here, the data items that you wish to sort are added one at a time to a list, in the correct place to keep the list sorted. A linked list is particularly suited to this because you can insert a new item anywhere in the list just by manipulating links, without having to move any of the existing items around.

We start by deciding the structure of each node in the list. In this example each node will contain a string item$ and an associated numeric value misc. Because it is a linked list each node must also contain a link link% which points to the next item in the list (the last item in the list has a link value of zero). Hence we can define a suitable structure for each node in the list as follows:

        DIM node{item$, misc, link%%}

The structure could contain any number of additional members, so long as there is always a link member.

We keep track of the start of the linked list by defining a variable first% which points to the first node in the list. Initially the list is empty, so we set this variable to zero:

        first%% = 0

Next we start the insertion sort proper. For convenience we will read each data item in turn from a “DATA” statement:

        DATA The, quick, brown, fox, jumps, over, the, lazy, dog.
 
        FOR n% = 1 TO 9
          READ word$

For each word we need to find where in the list it needs to be inserted to keep the list sorted into an ascending alphabetical sequence. This we do by following the links from the beginning until we either get to the end of the list, or we get to an entry which is later in the alphabet than our word:

          prev%% = 0
          this%% = first%%
          WHILE (this%% <> 0) AND (word$ > FNgetitem(node{}, this%%))
            prev%% = this%%
            this%% = node.link%%
          ENDWHILE

A little explanation is probably necessary at this point. We define two new variables this% and prev% to point to the node in which we are currently interested, and the previous node (the one that links to it), respectively. To begin the search we set this% equal to first% (the start of the list) and we set prev% to zero (because the start of the list has no previous node).

The WHILE statement loops for as long as we haven't reached the end of the list and our data word is greater than the current item. A function FNgetitem is used to return the value of the item$ member for the node pointed to by this% and, importantly, it also sets the structure node{} to correspond to this node. This makes it easy to follow the links.

When the loop has finished we know that, in order to keep the list sorted, we need to insert our new word after node prev% but before node this%. We first create a new node to contain the data:

          new%% = FNnewnode(node{})
          node.item$ = word$
          node.misc = n%

The function FNnewnode creates a new node and returns a pointer to it. It also sets the structure node{} to correspond to this node for the convenience of setting its members. For the purposes of the example we set the misc element to the value of the loop counter n%.

We must now link this new node into the correct place in the list:

          node.link%% = this%%
          IF prev%% THEN
            PROCsetlink(node{}, prev%%, new%%)
          ELSE
            first%% = new%%
          ENDIF
 
        NEXT n%

Here the procedure PROCsetlink sets the link member of node prev% to point to node new%. If we need to insert the new node at the start of the list (hence prev% is zero) we simply set first% to point to the new node.

Now the insertion sort is complete, and all we need to do is print out the contents of the list in sequence to see if they are correct:

        this%% = first%%
        WHILE this%% <> 0
          word$ = FNgetitem(node{}, this%%)
          misc = node.misc
          PRINT word$, misc
          this%% = node.link%%
        ENDWHILE
        END

If all is well this should print:

  1 The
  3 brown
  9 dog.
  4 fox
  5 jumps
  8 lazy
  6 over
  2 quick
  7 the

All that remains is to list the procedures and functions, which contain the 'magic' to make all this work:

        DEF FNnewnode(RETURN n{})
        LOCAL p%%
        DIM p%% DIM(n{})-1
        PTR(n{}) = p%%
        = p%%
 
        DEF FNgetitem(RETURN n{}, n%%)
        IF n%% = 0 THEN = ""
        PTR(n{}) = n%%
        = n.item$
 
        DEF PROCsetlink(n{}, n%%, l%%)
        PTR(n{}) = n%%
        n.link%% = l%%
        ENDPROC