The principles behind the algorithm previously described are fairly straight forward, but there are details to consider when turning it into a real program, so let’s take a look at some pseudocode.
In the algorithm we simply said “identify the new item’s place in the list”, but in reality, in order to add a new item to a list, we need to traverse it, in the same way we would to search for an existing item, by following a trail of pointers. Once we know our new item’s correct notional position in the linked list, we need to do a little pointer manipulation to establish where it belongs.
Data(NextFree) = new Item
IF NextFree = 1 THEN
NextFree = NextFree + 1
EXIT PROCEDURE
END IF
ptr=Start
WHILE ptr <> 0
IF NewItem < Data(ptr) THEN
Next(NextFree) = ptr
IF ptr = Start THEN
Start = NextFree
ELSE
Next(prevPtr) = NextFree
END IF
EXIT WHILE
ELSE
prevPtr = ptr
ptr = Next(ptr)
END IF
END WHILE
IF ptr = 0 THEN
Next(prevPtr) = NextFree
END IF
NextFree = NextFree + 1
We have two separate arrays, one array called Data, to store the actual data items, and another array called Next, which contains each item’s pointer to the next item in the list.
We assign the new data to the next empty element of the data array as given by the next free pointer (line 1). This happens unconditionally because where the new item goes in the data array really has nothing to do with its notional position in the linked list.
We need to check to see if NextFree is 1 (line 3). If so, we must be dealing with the very first data item, which is a special case so it’s handled separately; It has already been assigned to the to the first element of the data array and, because it will point to nothing else, there is no decision to make about where it goes in the list, so we simply increment NextFree (line 4) and exit the program (line 5).
The main loop of this program (line 9 & line 22) traverses the linked list, by following the sequence of pointers stored in the Next array.
As we traverse the linked list, we are trying to determine where the new item belongs. We do this by repeatedly asking if the new item is smaller than the item we are currently visiting (line 10).
If the new item should indeed come before the one we are currently visiting, then the new item should point to the existing item that we are visiting, no matter what. It now knows what’s in front of it, so we assign the value of ptr to the new item’s next pointer (line 11).
We then check to see if the new item is a new start item, that is, if it belongs at the very beginning of the list (line 12). If it is, we will need to handle it in a different way to something that should sit in between a couple of existing items. We can establish if the new item is a new starting item by comparing ptr, which represents the current node, with the current value of start.
If ptr and Start have the same value, then we are visiting the current starting item and, since our new item belongs before the current item, we can make the new item the new starting item by assigning NextFree to Start (line 13).
If a new starting item has just been inserted, the loop can exit and the program can end (line 17).
Suppose the new item is not smaller than the current item, so we haven’t yet found the correct position for our new node (line 10), then we need to start our little pointer juggling act (lines 19 and 20). We need to temporarily keep a handle on the current item (line 19) before we reset ptr (line 20) in order to visit the next item in the chain.
This means that when we pass through the loop next time (line 9) and find the correct place a typical new item (that is, an item which is not a new starting item), (line 10) we can slot it into place by setting the new item’s pointer to the current item (line 11), and the preceding item’s pointer to this new item (line 15).
It would be well worth coding this up yourself and stepping through it carefully. The code here is almost a VB.NET implementation.