Sams Teach Yourself C in 21 Days

Bonus Section: Understanding Linked Lists ......................................................

Alinked listis a useful method of data storage that can easily be implemented in C. Why

are we covering linked lists in a chapter on pointers? Because, as you will soon see,

pointers are central to linked lists.

There are several kinds of linked lists, including single-linked lists, double-linked lists,

and binary trees. Each type is suited for certain types of data storage. The one thing that

these lists have in common is that the links between data items are defined by informa-

tion that is contained in the items themselves, in the form of pointers. This is distinctly

different from arrays, in which the links between data items result from the layout and

storage of the array. This section explains the most fundamental kind of linked list: the

single-linked list (which we refer to as simply a linked list).

Basics of Linked Lists ..................................................................................

Each data item in a linked list is contained in a structure. (You learned about structures

on Day 11, “Implementing Structures, Unions, and TypeDefs.”) The structure contains

the data elements needed to hold the data being stored; these depend on the needs of the

specific program. In addition, there is one more data element—a pointer. This pointer

provides the links in a linked list. Here’s a simple example:

struct person {

char name[20];

struct person *next;

};

This code defines a structure named person. For the data,personcontains only a 20-

element array of characters. You generally wouldn’t use a linked list for such simple data,

but this will serve for an example. The personstructure also contains a pointer to type

416 Day 15

DOremember to use parentheses when

declaring pointers to functions.

Here’s how you declare a pointer to a

function that takes no arguments and

returns a character:

char (*func)();

Here’s how you declare a function that

returns a pointer to a character:

char *func();

DON’Tuse a pointer without first initial-

izing it.

DON’Tuse a function pointer that has

been declared with a different return

type or different arguments than you

need.

DO DON’T

25 448201x-CH15 8/13/02 11:13 AM Page 416