Article Preview
Buy Now
FEATURE
Linked Lists
Mind Your Stacks and Queues
Issue: 1.1 (August/September 2002)
Author: Matt Neuburg
Author Bio: Matt Neuburg is the author of
Article Description: The linked list data structure
Article Length (in bytes): 10,102
Starting Page Number: 34
Article Number: 1009
Resource File(s):
1009.zip Updated: 2013-03-10 15:07:10
Related Link(s): None
Excerpt of article text...
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, as 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. 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).
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).
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).
...End of Excerpt. Please purchase the magazine to read the full article.