Chapter 18: Linked Lists and Pointers 249

Making Data Structures with Linked Lists

The simplest linked list is a single-linked list, in which each node contains data and one pointer that points to another node in the linked list (refer to Figure 18-2).

The trouble with a single-linked list is that each node points only to the next node. If you want to find the previous node, you can’t. In Figure 18-2, for example, the middle node (containing the name Dick) points only to the node containing the name Harry. But you can’t tell which name appears before Dick. In this case, an array is much simpler, because an array can identify which data appears before and which data appears after a specific array location.

You can arrange linked lists in a variety of ways to create different types of data structures. Because data structures do nothing more than hold data, choosing the right data structure can make your program easier to write.

(And choosing the wrong data structure can make your program harder to write.)

A personal organizer program that stores names and addresses, for example, may use a linked list of records. The program can expand or shrink the linked list, depending on the number of names and addresses the user stores. The type of program that you’re writing can determine the type of data structure you need (or should use). That’s what makes linked lists so powerful — they can create a variety of different data structures.

Don’t worry about the details of creating different data structures with linked lists. Just remain aware that different data structures exist — and you usually run into these different data structures later on if you continue learning about computer programming.

Double-linked lists

The problem with a single-linked list is that each node can identify only the next node but not the preceding node. To solve this problem, you can create a double-linked list, in which each node contains data and two pointers. One pointer points to the next node in the linked list, and the second pointer points to the previous node in the linked list, as shown in Figure 18-7.

250 Part IV: Dealing with Data Structures

Figure 18-7:
A double-
linked list
uses two
pointers to	Tom	Dick	Harry
point at	nil
nodes that
			nil
appear
before and
after each
linked node.

A personal-organizer program is likely to use a double-linked list to enable the user to scroll forward and backward through the linked list to view all the names and addresses that you store in the personal-organizer program.

Creating a double-linked list means writing instructions to manage twice as many pointers, which essentially doubles the chances that you may leave a pointer dangling (that is, pointing to a nonexistent node) or pointing to the wrong node. In either case, incorrect pointers can cause subtle, yet serious bugs in your program, so use pointers sparingly.

Circular-linked lists

A typical double-linked list looks like a long rectangle with a beginning and an end (refer to Figure 18-7). But instead of creating an artificial end and beginning, you can link both ends of a single-linked list or a double-linked list to create a circular-linked list, as shown in Figure 18-8.

	Figure 18-8:
	A circular-	Tom	Dick	Harry
	linked list
	displays no
	beginning or
	ending.

A circular-linked list may prove useful for a presentation program that needs to display information continuously, such as a presentation in a museum kiosk. In this case, the presentation program may display information one screen at a time and then begin again after it reaches the end of the presentation.

Chapter 18: Linked Lists and Pointers 251

Stacks

A stack is a special single-linked list that enables you to add and remove nodes only at the beginning of the linked list (see Figure 18-9). In the real world, the most common implementation of a stack occurs as you stack plates. If you want to store a new plate, you simply add it to the top of the stack. If you want to remove a plate, you take it off the top of the stack as well.

One common use for stacks is for calculating formulas by using a method known as Reverse Polish Notation (RPN), which is a method of calculation that many Hewlett-Packard calculators use. If you want to calculate the formula (1 + 2) * 3 by using RPN, you type the following:

1 2 + 3 *

Formula: (1 + 2) * 3

Reverse Polish Notation: 1 2 + 3 *

			1		2		3		3		9
					1				3
Figure 18-9:
A stack
adds data to
and
removes
data from
the top of a
stack (linked
			Step 1		Step 2		Step 3		Step 4		Step 5
list).

Figure 18-9 shows how a stack stores the five steps that you need to calculate the formula (1 + 2) * 3 by using Reverse Polish Notation. Here’s how it works:

1.The first step pushes the number 1 to the top of the stack.

2.The second step pushes the number 2 to the top of the stack and pushes the number 1 underneath.

3.The third step pops the number 2 off the stack, pops the number 1 off the stack, and adds the two numbers together to get the number 3. Then it stores the number 3 back on top of the stack.

4.The fourth step pushes the number 3 (from the formula) to the top of the stack and pushes the calculated value of 3 farther down the stack.

252 Part IV: Dealing with Data Structures

5.The fifth step pops the first number 3 off the stack, pops the second number 3 off the stack, and multiplies the two number 3s to get the number 9. Then it stores the number 9 back on top of the stack.

Stacks are often referred to as LIFO (which stands for Last In, First Out) linked lists. This term means that the last data that you store in a stack is the first data that you remove from the stack (just as in stacking and removing plates).

Don’t worry if you don’t understand the logic behind Reverse Polish Notation. Just understand how stacks work and leave Reverse Polish Notation for the engineers at Hewlett-Packard.

Queues

A queue is a special linked list that follows two rules. The first rule is that you can add nodes only to the end of the linked list. The second rule is that you can remove nodes only from the beginning of the linked list.

You often refer to queues as FIFO (which stands for First In, First Out) linked lists. This term means that the first data that you store in the queue is the first data that you remove from the queue. A queue mimics a line of people waiting to board an airplane or see a science-fiction movie. In both cases, the first person (data) put in the queue is the first person (data) who leaves it, as shown in Figure 18-10.

			Step 1				Front
			Tom		Dick	Harry	John
					Step 2
					Tom	Dick	Harry
Figure 18-10:
						Step 3
A queue
stores new						Tom	Dick
data at the
end and
removes the					Step 4
oldest data
from the					Mike	Tom	Dick
front.