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