=====Linked lists using structures=====

//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:\\ \\ 
<code bb4w>
        DIM node{item$, misc, link%%}
</code>
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:\\ \\ 
<code bb4w>
        first%% = 0
</code>
Next we start the insertion sort proper. For convenience we will read each data item in turn from a "DATA" statement:\\ \\ 
<code bb4w>
        DATA The, quick, brown, fox, jumps, over, the, lazy, dog.

        FOR n% = 1 TO 9
          READ word$
</code>
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:\\ \\ 
<code bb4w>
          prev%% = 0
          this%% = first%%
          WHILE (this%% <> 0) AND (word$ > FNgetitem(node{}, this%%))
            prev%% = this%%
            this%% = node.link%%
          ENDWHILE
</code>
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:\\ \\ 
<code bb4w>
          new%% = FNnewnode(node{})
          node.item$ = word$
          node.misc = n%
</code>
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:\\ \\ 
<code bb4w>
          node.link%% = this%%
          IF prev%% THEN
            PROCsetlink(node{}, prev%%, new%%)
          ELSE
            first%% = new%%
          ENDIF

        NEXT n%
</code>
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:\\ \\ 
<code bb4w>
        this%% = first%%
        WHILE this%% <> 0
          word$ = FNgetitem(node{}, this%%)
          misc = node.misc
          PRINT word$, misc
          this%% = node.link%%
        ENDWHILE
        END
</code>
If all is well this should print:\\ \\ 
<code>
  1 The
  3 brown
  9 dog.
  4 fox
  5 jumps
  8 lazy
  6 over
  2 quick
  7 the
</code>\\ \\  All that remains is to list the procedures and functions, which contain the 'magic' to make all this work:\\ \\ 
<code bb4w>
        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
</code>