3. Doubly Linked Lists.

If we change the structure of our nodes and add a PRIOR pointer to each node and to the root node as well, we can store the address of both nodes neighbouring our current one, as shown below. Here is the node structure :

+-------+  4 bytes at the start of each node hold the address of the NEXT node in the
| NEXT  |  list.
+-------+  The next 4 bytes hold the address of the node PRIOR to this one in the
| PRIOR |  list.
+-------+
| DATA  |  The data bytes can be any size and hold any data we like.
+-------+

Our conceptual model of the doubly linked list is as follows :

   +-------+
   |       |                    +-----------------------------------+
+--+----+  |       +-------+    |     +-------+          +-------+  |
| FIRST |--|--+--> | NEXT  |----+---> | NEXT  |--------> | NEXT  |  |
+-------+  |  |    +-------+          +-------+          +-------+  |
| PRIOR |  +--^----| PRIOR |          | PRIOR +--+       | PRIOR +--+
+-------+     |    +-------+          +-------+  |       +-------+
  ABCD        |    | DATA  |          | DATA  |  |       | DATA  |
              |    +-------+          +-------+  |       +-------+
              |      1000               2000     |         1200
              +----------------------------------+

3.1. Adding Nodes.

Adding a new node is still simple. Having allocated a node on the heap, you set it's PRIOR pointer to zero and it's NEXT to the current address held in the FIRST pointer - almost identical to the single linked list code above.

Prior      equ 4               ; Offset to PRIOR pointer in a node

Prelude    lea FIRST,a0        ; Pointer to storage of first node address
           lea NewEntry,a1     ; Address of new node

Then adding a new node to a doubly linked list is as simple as this :

AddNode    cmpa.l  a0,a1         ; Don't allow the root node to be added again
           beq.s   AddExit       ; Bale out quietly if attempted
           move.l (a0),(a1)      ; Save current first node in new node's NEXT area
           move.l  a0,Prior(a1)  ; Set the PRIOR node for this new node
           move.l  a1,(a0)       ; Store address of new node in FIRST storage area
           move.l  (a1),a0       ; A0 = address of original FIRST node in list
           cmpa.l  #0,a0         ; Nothing to do if A0 is zero.
           beq.s   AddExit       ; Exit with Z set = First node added to list.
           move.l  a1,prior(a0)  ; Store address of new FIRST node in PRIOR pointer
AddExit    rts

As with single linked lists there is nothing to it. The new node is always added at the start of the list, so the value in FIRST always points to the latest node added. The first non root node in a doubly linked list has no real PRIOR node, so that part of the newly added node is simply set to point back at the root node.

Building up the linked list above in stages, we would start like this :

+-------+
| 0000  |
+-------+
| 0000  |
+-------+
  ABCD

Then add the node at address 1200 as our first node, giving this :

+-------+          +-------+
| 1200  |          | 0000  |
+-------+          +-------+
| 0000  |          | ABCD  |
+-------+          +-------+
  ABCD             | DATA  |
                   +-------+
                     1200

When we add the node at 2000 as the second node, we get the following :

+-------+          +-------+          +-------+
| 2000  |          | 1200  |          | 0000  |
+-------+          +-------+          +-------+
| 0000  |          | ABCD  |          | 2000  |
+-------+          +-------+          +-------+
  ABCD             | DATA  |          | DATA  |
                   +-------+          +-------+
                     2000               1200

And finally, adding the node at address 1000 gives us this :

+-------+          +-------+          +-------+          +-------+
| 1000  |          | 2000  |          | 1200  |          | 0000  |
+-------+          +-------+          +-------+          +-------+
| 0000  |          | ABCD  |          | 1000  |          | 2000  |
+-------+          +-------+          +-------+          +-------+
  ABCD             | DATA  |          | DATA  |          | DATA  |
                   +-------+          +-------+          +-------+
                     1000               2000               1200

You can see how each node points onward to the NEXT one and also backwards to the PRIOR one. The last node nas no NEXT nodes, so it has its NEXT pointers set to zero to indicate the end of the list.

3.2. Deleting Nodes.

Deleting a node is much simpler. There is no need to scan the entire list from the start looking for the node prior to the one you want to delete because you already know it's address by following the PRIOR pointer backwards from the node to be deleted.

Here's the pseudo code to delete a node. We assume, as before, that A0.L is the root node pointer and A1.L is the node to be deleted.

  • If the two addresses are equal, we cannot allow the root node to be deleted, exit with an error.

  • If the address in the root node's NEXT pointer is zero then we still have an empty list so the value in A1 must be illegal. Exit with an error.

  • Fetch the deleted node's PRIOR pointer. Every real node in a list will have a valid PRIOR pointer, only the root node has no prior pointer and we don't allow that to be deleted.

  • Store the NEXT pointer from the deleted node into the NEXT pointer of the prior node.

  • Fetch the deleted node's NEXT pointer, which might be zero if we are deleting the final node in the list.

  • If it is not zero, store the deleted node's PRIOR pointer in the next node's PRIOR pointer.

  • Exit without error.

That's the pseudo code, here's the real code to do all of the above.

Prior      equ 4               ; Offset to PRIOR pointer in each node

Prelude    lea FIRST,a0        ; Pointer to storage of first node address
           lea OldNode,a1      ; Address of node to delete
           moveq #ERR_BP,d0    ; Bad Parameter = trying to delete the root node

Now, here's the actual code to find and remove the requested node.

DelNode    cmpa.l a0,a1        ; Don't allow the root node to be deleted
           beq.s DelExit       ; Bale out with error if attempted

           cmp.l #0,(a0)       ; Do we actually have a list ?
           beq.s DelExit       ; Yes, node not found, exit with error

           move.l Prior(a1),a0 ; Fetch the deleted node's PRIOR pointer
           move.l (a1),(a0)    ; Store the deleted node's NEXT pointer in the NEXT
                               ; pointer of the PRIOR node

           move.l (a1),a0      ; Fetch the deleted node's NEXT pointer
           move.l  Prior(a1),Prior(a0) ; Store the deleted node's PRIOR pointer in the
                                       ; next node's PRIOR pointer.

DelFound   move.l (a1),(a0)    ; PRIOR node's NEXT = the deleted node's NEXT address
           moveq  #0,d0        ; Node deleted ok
           bra.s  DelExit      ; Bale out with no errors

DelNext    move.l (a0),a0      ; A0 now holds the NEXT node in the list
           bra.s  DelNode      ; Go around again

DelExit    tst.l d0            ; Set zero flag for success, unset for error
           rts

3.3. Finding Nodes.

As with single linked lists, you may have a need to locate a specific node by its contents, so you need a generic FindNode routine again. The fact that the list has two pointers this time around is the only difference, so the code is basically the same as for the single linked list above.

The only difference is the offset to the data part of the node needs to be set to 8 bytes instead of 4, so while the code for the FindNode remains the same, the code for the Compare routine needs to be changed to the following to account for the extra pointer.

As before, the comparison routine must preserve A0, A1, A2 and D0 or it will all go horribly wrong.

NData   equ 8                  ; Offset from start of node to the data part

Compare    cmp.l NData(a3),(a2) ; Is the data in the node = the value we want?
           rts                  ; Exit with Z set if so, unset otherwise.

Again, if an attempt is made to 'find' the root node, then it will fail.

3.4. A Better Mousetrap.

Because the code for the linked list find routine is identical except for the offset in the compare routine you can use the same code. If you modify it so that it passes the offset over to the compare routine in a spare register, say D1.W for example, then you can even have the same compare routine for both single and doubly linked lists, as shown below.

Compare    cmp.l 0(a3,d1.w),(a2) ; Is the data in the node = the value we want?
           rts                   ; Exit with Z set if so, unset otherwise.

Another method, much loved in the internals of Microsoft Windows, is to store a word holding the offset to the data at the start of each node. This would remove the need for the D1.W register to be passed into the comparison routine as a parameter as it could easily extract the data from the node itself, as follows :

Compare    move.w (a3),d1        ; Fetch the offset to the data from the node
           cmp.l 0(a3,d1.w),(a2) ; Is the data in the node = the value we want?
           rts                   ; Exit with Z set if so, unset otherwise.

The drawback to this method is the redundancy of the data - each and every node has to have the first two bytes set to the offset to the data plus 2 for the size of the offset word itself. Two extra bytes per node may be the difference between getting all the data in memory or not. It is, of course, always up to you. If you decide to go down this route, don't forget to amend the code to add, find and delete nodes to take the extra two bytes into consideration when manipulating the pointers to NEXT and PRIOR. Your root node must also reflect these changes and have an offset word added to its own structure.

You might see a need to build a couple of comparison routines to compare two nodes rather than the example above where a node is being compared with a value. On the other hand, you could simply write one routine to compare two nodes and when looking for a value, create a dummy node and use that in the comparison routine. That way, you don't need separate routines to compare values and nodes.

3.5. Double Trouble.

The problem with a doubly linked list is that while adding nodes is just as simple as before, but deleting them could be problematical. If you are passed the address of a node which is not in the list, how do you tell that it is or is not a valid node address? You can end up trashing bytes of memory almost at random as you start changing the NEXT and PRIOR pointers for two areas of memory which may not be in your list.

My solution is to use a flag word or long word after the two list pointers in each node and when passed in a node address to delete, compare this value in the flag to see if it is correct before attempting to delete the node. As ever, I leave this 'as an exercise for the reader' to modify the code above to carry out said checks.

3.6. Sorting Lists.

The best way to sort a list is not to have to sort it at all. When you store a node in the list, store it in the correct place according to its value. A doubly linked list is used here again as you will need to go NEXT until you hit a value greater than the one you want to insert, then you might need to go PRIOR to insert it in the correct location. I'll leave you to figure out that little exercise.

There is an another way, which involves TREES of nodes rather than lists. A tree is simply a linked list which has a LEFT, RIGHT and UP pointer in each node.

With a tree, the nodes are not in a long line, but they are off to the LEFT and RIGHT of the root node. Each node may itself have children to the LEFT and RIGHT as well as a parent found by following the UP pointer.

Unfortunately, trees are a bit beyond my skills at the moment. I remember doing them in college and learning all the different ways to navigate them, but I cannot remember much about them nowadays - it's been over 30 years since I last considered them.