Matt Neuburg is the author of REALbasic: The Definitive Guide, and a member of the editorial board of REALbasic Developer. This article was originally published in REALbasic Developer Issue 1.1 (Aug/Sept 2002).
The term “algorithm” can mean instructions for carrying out some typically useful operation, but it can also mean a typically useful data structure and the methods for working with it. A linked list is often one of the first data structures treated in books on algorithms, and it makes a good subject for this first Algorithms column.
A linked list is a simple data structure that’s useful chiefly because it’s dynamic. This means you don’t have to set aside storage for the data beforehand; instead, the linked list grows and shrinks as the program runs, when data is added or removed. In REALbasic this fact is not very compelling, though, because arrays are dynamic already! You can add data with Insert or Append, and remove it with Remove. Nevertheless, you can also very easily implement a traditional linked list in REALbasic, and it’s instructional to see how. And the principles involved are applicable to more complicated and powerful data structures, such as binary trees, that we can examine in future columns.
The chief characteristic of a linked list is that from each piece of data it is possible to reach the next piece of data. The pieces of data are connected by pointers; to reach the next piece of data, follow this piece’s pointer (see figure 1).
|
| Figure 1: A linked list |
To see why this is dynamic, consider how you’d insert a new piece of data, “hi”, after “hey”: just disconnect the pointer from “hey” to “ho”, and make it run to “hi” instead, and connect the pointer from “hi” to “ho” (see figure 2).
 |
| Figure 2: Insertion into a linked list |
Let’s implement this in REALbasic. In REALbasic, object references are pointers. (See pp. 94–104 of my book for much more about that.) So the problem is solved if each piece of data is an object, and consists of two things: the value to be stored, and a reference to the next piece of data. An object consisting of two things is merely an instance of some class that has two properties. Let’s call the class ListItem, and let its two properties be called Value, a variant (for generality), and NextItem, another ListItem. It’s easy to see that, with appropriate values for the properties of each instance, we end up with a linked list (see figure 3).
 |
| Figure 3: Linked list made of REALbasic objects |
We can now implement Insert, handing a ListItem the Value we want attached to a new ListItem that will follow it.
ListItem.Insert:
Sub Insert(v As variant) dim newItem as ListItem newItem = new ListItem newItem.value = v newItem.nextItem = self.nextItem // (a) self.nextItem = newItem // (b) End Sub
The last two lines, (a) and (b), perform the disconnection and reconnection of pointers that we talked about earlier. After (a), for an instant, both the new item’s NextItem and the target’s NextItem point at the same thing; then in (b) we repoint the target’s NextItem at the new item. The order of operations is important! If (b) precedes (a), then after (b), the target’s NextItem no longer points at what was the next item in the list — in fact, nothing at all points to it, the item is lost, and the list is ruined.
In REALbasic, an object reference that has never been set explicitly is nil. This fact makes it easy to obtain the last item in the list, by following the chain of pointers pointers item by item until we come to one whose NextItem is nil. This approach works no matter what item of the list we target initially. Following the whole chain of pointers in this way is called traversing the list, and can be neatly expressed in REALbasic.
ListItem.LastItem:
Function LastItem() As ListItem
dim x as listItem
x = self
while x.nextItem <> nil
x = x.nextItem
wend
return x
End Function
As an exercise, implement Append. This accepts a value and adds it at the end of the list, no matter what item of the list we target initially. Hint: combine LastItem and Insert.
Finally, we implement RemoveNext. When sent to an item of the list, it removes the next item from the list. We first check for a NextItem value of nil, since the target might be the last item already; in that case, obviously, we do nothing. Otherwise, we just point the target’s NextItem at the next item’s NextItem (see figure 4). The instant we do this, nothing points at what used to be the next item, whose existence is promptly terminated by REALbasic’s delightful memory management system.
 |
| Figure 4: Deletion from a linked list |
ListItem.DeleteNext:
Sub DeleteNext
if self.nextItem <> nil then
self.nextItem = self.nextItem.nextItem
end
End Sub
A stack is a data structure where access to the pieces of data works like a pile of plates: you can add or remove an item only at the top of the pile. Items can thus be retrieved only in the reverse of the order in which they were added; for this reason, a stack is often described as LIFO (last in, first out). The two fundamental operations on a stack are called Push (add a new item at the top of the stack) and Pop (remove the topmost item from the stack and return its value).
Under the hood, stacks are fundamental to many computer operations, such as calling subroutines. They also come in handy during certain kinds of parsing operations, and wherever backtracking is involved. For example, a stack would be a good way to implement an Undo list. In the case of an EditField, every time the EditField changes, you could Push its current state (its text and style) onto the stack; to Undo one level, just Pop the stack to retrieve the previous state.
A stack is easily implemented as a linked list. We might, indeed, have a class Stack that is a subclass of ListItem. Suppose we maintain somewhere a property or variable called TheStack, which is a Stack. TheStack represents the entire stack; Push and Pop are sent only to it. But in reality it is the start of a linked list, and points to the topmost item of the actual stack.
Stack.Push:
Sub Push(v as variant) self.insert v End Sub
Stack.Pop:
Function Pop() as variant
dim v as variant
if self.nextitem <> nil then
v = self.nextitem.value // (a)
self.deleteNext // (b)
return v
end
End Function
Again, order of operations is important. We use a local variable to capture the value to be returned, in (a), before deleting the item that contained it, in (b). If (b) were performed before (a), the value would be destroyed before it could be returned; there would be nothing to return.
Since, as mentioned earlier, a REALbasic array is already a dynamic data structure, Stack could just as well be implemented by wrapping a variant array. Let’s start over. Stack now has no superclass, and has a single property, MyArray, a variant array initially dimmed to size –1. We’ll treat the end of the array as the top of the stack. So Push just means Append.
Stack.Push:
Sub Push(v as variant) MyArray.append v End Sub
As an exercise, implement Pop.
To the programmer, you’ll observe, it doesn’t matter whether Stack is implemented as a linked list or an array. This is in keeping with the principle of abstraction: lower-level manipulation of data is hidden inside a controller object. As much as possible, you should try to program this way. For one thing, other objects in your program have no need to concern themselves with the underlying implementation details; they just say Push or Pop and everything simply works. This greatly reduces the chances for error. Also, you could change your mind about the underlying implementation, changing it from a linked list to an array for example, and all the calls to Push and Pop throughout the program would go right on working.
A queue is a data structure where access to the pieces of data works like patrons lined up to enter a movie theater: the first patron to get on line will be the first patron to enter the theatre, and so on. A queue is often described as FIFO (first in, first out). The fundamental operations on a queue are called Queue (append an item to the tail of the queue) and Dequeue (retrieve an item from the front of the queue).
Queues often arise in threaded situations, where pending tasks can pile up while a previous task is being performed. For example, in an email client program, we might allow the user to press the Send button at any time, but we won’t actually perform any new sending until we finish with whatever message we may be sending at the moment.
Implementation of Queue and Dequeue are left as an exercise to the reader; do it both ways, with a linked list and with an array.