次の構造体を考えましょう。
struct s {
int n;
char str[12];
struct s *p;
};
これは int型変数 n，char型配列 str，そして，自己へのポインタ p をメンバにもつ自己参照型構造体です。それら３つのメンバからなるユニットを「データ」と呼ぶことにしましょう。今，データが次のようにあるとします。（角括弧内はアドレスです。）
データ１ データ２ データ３ データ４ [0x442b0] [0x442d0] [0x442f0] [0x44310] n = 0 n = 1 n = 2 n = 3 str = if str = while str = int str = char p = 0x0 p = 0x0 p = 0x0 p = 0x0
現在，どのデータのポインタ p も NULLポインタです。それらを次のようにしてみましょう。データ１のポインタを p = 0x442d0，データ２のポインタを p = 0x442f0，そしてデータ３のポインタを p = 0x44310 としてみます。すると，上の４つのデータは，次のようになります。
データ１ データ２ データ３ データ４ [0x442b0] [0x442d0] [0x442f0] [0x44310] n = 0 n = 1 n = 2 n = 3 str = if str = while str = int str = char p = 0x442d0 p = 0x442f0 p = 0x44310 p = 0x0
このようにすると，データ１を先頭に，ポインタ p によって４つのデータが繋がることになります。このような構造をしたデータを「リスト構造」といい，「連結リスト（linked list）」とか「つなぎリスト」と呼ばれています。
/* Example 11.13 */
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
struct list {
int n;
char str[12];
struct list *next;
};
struct list *createData(int, char *);
int main(void)
{
int i;
char *keywords[10] = {
"\0",
"if",
"while",
"for",
"do",
"switch",
"case",
"break",
"int",
"char"
};
struct list *head, *new, *data;
head = createData(0, keywords[0]);
data = head;
for (i = 1; i < 10; i++)
{
new = createData(i, keywords[i]);
data -> next = new;
data = new;
}
printf("[Address]\tn\tstr\tnext\n");
for (data = head; data != NULL; data = data -> next)
printf("[%p]\t%d\t%s\t%p\n", data, data -> n, data -> str, data -> next);
exit(0);
}
struct list *createData(int num, char *word)
{
struct list *data;
data = (struct list *)malloc(sizeof(struct list));
if(data == NULL) { exit(1); }
data -> n = num;
memcpy(data->str, word, sizeof(data->str)-1);
data -> next = NULL;
return data;
}
ポインタ head は，リストの先頭のアドレスを指すために用意したポインタです。また，ポインタ new は新しいデータを指すためのポインタ，そして，ポインタ data は現在のデータのアドレスを指すために用意したポインタです。関数 createData は「ポインタの関数」と「ポインタ関数」の複合型で，この場合，構造体 list型のポインタが従属変数，構造体のメンバ n と str へ代入するための変数が独立変数（仮引数）となっています。
先ず，リストの先頭となるデータを作ります。そのために，ポインタ head に関数 createData の値を代入します。createData関数は，データを確保するためのメモリ領域を確保し，確保したデータのメンバ n，str，そして next に値を代入し，そのデータを返します。今回，ポインタ以外の構造体変数は，全く用意していません。したがって，ポインタが指すアドレスのメモリ領域を確保する必要があります。そのために，「10.12. ポインタを返す関数」で見た malloc を使っています。
このようにしてリストの先頭データを確定させた後は，for文による繰り返し処理を使ってリストを作成しています。新しいデータを作成し，現在のデータからその新しいデータへリンクさせ，そして，現在のデータをその新しいデータに書き直す処理の繰り返しです。
２つ目の for文は，データを示すポインタが head のアドレスのときに繰り返しが始まり（data = head），データが空でない（NULLポインタでない）限り繰り返しを続け，繰り返すとポインタの値を次のデータに移動させるというものです。実行結果は次の通りです。
[Address] n str next [0x442b0] 0 0x442d0 [0x442d0] 1 if 0x442f0 [0x442f0] 2 while 0x44310 [0x44310] 3 for 0x44330 [0x44330] 4 do 0x44350 [0x44350] 5 switch 0x44370 [0x44370] 6 case 0x44390 [0x44390] 7 break 0x443b0 [0x443b0] 8 int 0x443d0 [0x443d0] 9 char 0x0
ポインタ next が次のデータのアドレスを指している様子が見て取れます。
この結果を見ると「結局，配列が出来上がるのか，然らば最初から配列を使えば良いのでは」といった疑問がでることでしょう。連結リストの利点は，配列のサイズを指定する必要がなく，メモリ消費を最小に済ませることにあります。例えば，
struct list {
int n;
char str[12];
} x[100];
として，構造体変数に配列を指定すると，最初から大きなメモリ領域をとることになります。これに対し，連結リストは，リストの長さが不明な場合にも利用でき，必要なメモリのみを消費します。
