The Algorithm Design Manual Second Edition

3.1.2

Pointers and Linked Structures

Pointers are the connections that hold the pieces of linked structures together.

Pointers represent the address of a location in memory. A variable storing a pointer

to a given data item can provide more freedom than storing a copy of the item

itself. A cell-phone number can be thought of as a pointer to its owner as they

move about the planet.

Pointer syntax and power differ significantly across programming languages, so

we begin with a quick review of pointers in C language. A pointer p is assumed to

---

68

3 .

D A T A S T R U C T U R E S

Clinton

Jefferson

Lincoln

NIL

Figure 3.1: Linked list example showing data and pointer fields

All linked data structures share certain properties, as revealed by the following

linked list type declaration:

typedef struct list {

item_type item;

/* data item */

struct list *next;

/* point to successor */

} list;

In particular:

• Each node in our data structure (here list) contains one or more data fields

(here item) that retain the data that we need to store.

• Each node contains a pointer field to at least one other node (here next).

This means that much of the space used in linked data structures has to be

devoted to pointers, not data.

• Finally, we need a pointer to the head of the structure, so we know where to

access it.

The list is the simplest linked structure. The three basic operations supported

by lists are searching, insertion, and deletion. In doubly-linked lists, each node points

both to its predecessor and its successor element. This simplifies certain operations

at a cost of an extra pointer field per node.