Chapter 18

Linked Lists and Pointers

In This Chapter

Pointing at data

Understanding how linked lists work

Creating linked lists

Making data structures with linked lists

When you create an array, you must specify a size for it. If you make your array too small, your program won’t have enough room to store

data unless you increase the array size. Make the array too large, however, and you waste your computer’s valuable memory.

As a compromise, programmers developed something known as a linked list. Like an array, a linked list can store a list of items. But unlike an array, a linked list can grow or shrink as you need it to, so you never need to decide how much space to allocate ahead of time.

Some languages, such as BASIC, can’t create a linked list. Although you can’t make or use linked lists in Liberty BASIC, you still need to know about them. Linked lists are a common data structure that many other programming languages use, such as Java and C/C++.

Starting with a Pointer

An array contains a fixed number of storage units for holding data. If you design an array to hold five numbers but it needs to hold only two numbers, you’re wasting space in the computer’s memory. For small arrays, this situation isn’t much of a problem. But if you’re using a large, multidimensional array, the large amount of memory that the array consumes can actually keep your program from working on computers that don’t contain enough memory.

242 Part IV: Dealing with Data Structures

Another problem is that you can’t easily rearrange data in an array. Suppose, for example, that you have an array containing a list of first names, like the array shown in Figure 18-1. If you want to rearrange the names alphabetically, you must take all the data out and put it back in the array in alphabetical order.

Figure 18-1:		Tom		Dick	Harry		John
To
rearrange
data in an
array, empty
out the
array and		Dick		Harry	John		Tom
then put
data			DIM NameArray(4) AS STRING
back in.

To solve both these problems, programmers create linked lists. A linked list can grow and shrink depending on the amount of data that you store in it, so it uses memory more efficiently than an array does.

In addition, although an array is like a box that you divide into sections so that it can hold data, a linked list is more like a collection of separate boxes (known as a node) that you can tie together, as shown in Figure 18-2.

Figure 18-2:

A linked list		Nodes
consists of
nodes that	Tom	Dick	Harry
contain data
and a			nil
pointer to

	the next
	node in the	Pointers
	list.

The pointer that the last node of a linked list stores points to a special value known as nil. A nil value represents the end of the linked list.

Chapter 18: Linked Lists and Pointers 243

Unlike in an array, you don’t need to remove data just to rearrange it in a linked list. Instead, you can rearrange the data in a linked list by simply rearranging the order of the pointers, as shown in Figure 18-3.

	Tom	Dick	Harry
			nil
Figure 18-3:
To
rearrange
data in a	Tom	Dick	Harry
linked list,
you just
need to			nil
rearrange a
pointer.

Although variables normally contain numbers or strings, a pointer contains a memory address, which works much like a mailing address. By reading the memory address, the computer can find its way to the next chunk of data that you’re storing in a node.

Pointers are a main part of C/C++ programming. Because a pointer represents a memory address, you can really mess up your C/C++ programs if even one pointer contains the wrong memory address. If this happens, your program can directly manipulate your computer’s memory, which is like randomly probing your brain with a long, sharp needle. Using pointers incorrectly (like using brain surgery incorrectly) can mess up your computer’s memory, causing it to crash, freeze up, or simply act erratically.

Defining the parts of a linked list

A linked list consists of one or more nodes, where each node contains the following:

A pointer that points to the next node in your linked list

A record for storing data in the linked list

244 Part IV: Dealing with Data Structures

Liberty BASIC doesn’t offer commands for creating pointers, so the following code examples use the Pascal programming language, which looks enough like English that you can almost certainly understand how it works. If this subject looks too confusing, just browse over the Pascal programs in this chapter and look at the figures in this chapter to get a general idea of how linked lists work.

To create a linked list in Pascal, you must first create a pointer, as follows:

TYPE

PointerName = ^RecordType;

This code tells the computer, “Create the data type PointerName. This data type can hold the memory address that defines the location of the record type RecordType.”

After creating a pointer to a record, you create the actual record itself. The following record, for example, stores the string variable FullName; a second string variable, Address; and the pointer variable Next:

TYPE

PointerName = ^RecordType;

RecordType = RECORD

FullName : string[15];

Address : string[25];

Next : PointerName;

END;

After you define a pointer and a record, the third step is to define a variable to represent your record. This variable creates each node of your linked list, as follows:

VAR

Node : PointerName;

By putting this code all together, you create a program that looks as follows:

PROGRAM LinkedLists;

TYPE

PointerName = ^RecordType;

RecordType = RECORD

FullName : string[15];

Address : string[25];

Next : PointerName;

END;

VAR

Node : PointerName;