線形リスト（あるいは単に，リスト）というデータ構造も，１次元配列と同様に，データの列を扱うためのものである．
配列が特定の型の要素をメモリ上に整然と並べたものであるのに対して，線形リストはデータとポインタとが入ったノードと呼ばれる要素をポインタでつないだものである． また、そのノードはメモリ上に整然と並んでいるとは限らない。
次の図は，３個のノードで構成された線形リストである．
ノードはメモリ上に順番に存在する必要はないが，ノードのポインタは次の要素をきちんと指している必要がある．リスト最後尾の要素にあるポインタの値は，何も指さないポインタ（NULL ポインタ）となっている．
線形リストの各ノードにアクセスするには，リストの先頭を指すポインタから入って，ノードを順にたどって行くことで，行われる．
線形リストと配列とを比べたときの，線形リストの利点と欠点について述べる
ノードを自由に増やせる
通常，各ノードのためのメモリは，必要とされるときにヒープと呼ばれるメモリ領域に確保される．したがって，プログラム実行時に，メモリ容量の許す限りノードの個数を増やすことができる．
ノードの挿入削除が簡単
ポインタでノードがつながっているため，データの削除，挿入をしたとき，そのデータをもつノードとその前のノードとに含まれる，次のノード指すポインタを書き換えるだけで済む．
ノードへのアクセスが面倒
リストにアクセスするには，リストの先頭を指すポインタからリストに入り，ノードを順にたどっていく．したがって，各ノードへのアクセスに手間がかかるのが，欠点である．
NULLポインタとは
NULL は，何も指していないことを意味するポインタ定数として，stdlib.h, stddef.h, stdio.h, string.h,
time.h でマクロ定義されている。 NULLを用いるときには，これらのヘッダファイルのどれか一つ以上をインクルードすればよい。
線形リストは，通常，ヒープを利用して実現されるので，その利用法を知る必要がある．
ヒープ(heap)は，プログラムの実行途中にプログラムから随時利用可能なメモリ領域である。 heap は、積み上げた山、堆積物などの意味の英語である。
ヒープの管理は，malloc, calloc, realloc, free などの関数によってなされている．これらは，ヘッダファイル stdlib.h に宣言された標準ライブラリ関数であるので，使用する際には， それに先だって， 次のようにヘッダファイルを読み込むことが必要である．
#include <stdlib.h>
関数 void * malloc(size_t size) を用いることにより， size バイトの連続したメモリ領域が，ヒープ領域内に割り当てられる．割り当てられた領域の先頭を指すポインタが，この関数の戻り値となる．何らかの理由で割り当てに失敗した場合には， NULL ポインタが戻り値となる．関数名 malloc は memory allocate （メモリ割付）の略である．
int *p;
p = malloc(sizeof (int));
このように実行すると，これ以降，*p を整数型変数として使用することできる．
*p = 3;
malloc によって割り当てられたメモリ領域は，その先頭を指すポインタを関数 void free(void *ptr) の引数に渡すことにより，解放される．解放されたメモリ領域は，その後に malloc が呼ばれたときに（可能であれば）再利用される．
free(p);
これ以降，*p を変数として使うことはできない。使用するようなプログラムを書いた場合，コンパイルエラーにはならないが，そのプログラムは正常に作動しない。
関数 calloc（初期化区画割付）, realloc（再割付） については，C言語参考書等を参考にして欲しい．
線形リストのノードとなる構造体を定義し，線形リストを操作する関数群を用意して，線形リストを構築してみる．
線形リストを構成する，一つひとつのノードは，データと次のノードを指すポインタとでできている．このような，複数個のものが一つにまとまったものを構成するには，構造体を用いると良い．
また，ここでは，ノードが含んでいるデータの型名として， data_t という名前を用いる．これは，ここで作った構造体や関数群を書き直して，他の用途に使うときに，変更が容易であるようにするための配慮である．
typedef int data_t;
typedef struct nodetag {
data_t data;
struct nodetag *next;
} node_t;
この構造体定義について，一つずつ解説しよう．
まず全体が，次のような形になっている。
typedef
.....
node_t;
これは，..... というものを node_t という新しい名前の型として定義する，という意味である．そして，..... は次のようになっている．
struct nodetag {
data_t data;
struct nodetag *next;
}
この struct nodetag は， nodetag というタグ名の構造体の定義であることを表している．そして，それに続く { } の中が構造体の本体である．
data_t data はデータを入れるためのメンバである．
struct nodetag *next は，次のノードにつなげるためのポインタである．ポインタ next が指すものの型は，いま定義している構造体， struct nodetag である．
（もっと詳しい解説）では，このノード構造体を使って線形リストを作ってみよう． ３個のノードだけでできている線形リストである．
main()
{
node_t nd1, nd2, nd3;
node_t *p;
nd1.data = 1;
nd1.next = &nd2;
nd2.data = 2;
nd2.next = &nd3;
nd3.data = 3;
nd3.next = NULL;
p = &nd1;
printf("%d\n", p -> data); /*p は nd1 を指している */
p = p -> next;
printf("%d\n", p -> data); /* p は nd2 を指している */
p = p -> next;
printf("%d\n", p -> data); /* p は nd3 を指している */
}
1 2 3
次の図は，プログラムの途中，p = &nd1 を実行した時点での状態であり， p は nd1 を指している．
ここで p = p -> next を実行すると， p の値は p -> next すなわち nd1.next すなわち &nd2 となるので， p は nd2 を指すことになる．
もう一度 p = p -> next を実行すると， p の値は p -> next すなわち nd2.next すなわち &nd3 となるので， p は nd3 を指すことになる．
これからは，線形リストの各ノードは，次で定義する nodeNew 関数によって，ヒープ領域にメモリ割り当てすることとする。 したがって，ノードのためのメモリの確保は，
node_t nd;
のように，直接， node_t 型変数として宣言されるのではなく， 次のように，ノード型ポインタとして宣言された変数に，nodeNew によって割り当てたメモリを指すポインタ値を代入することにより成される．
node_t *ndptr;
ndptr = nodeNew(...);
もちろん，さきほどのプログラム例のように， node_t nd; と宣言しても，間違いではないが，これでは線形リストの柔軟な性質が生きてこない．
node_t *nodeNew(data_t dt, node_t *nxt)
{
node_t * ndPtr;
ndPtr = malloc(sizeof (node_t));
if (ndPtr == NULL) {
return NULL; /* 割り当て失敗 */
} else {
ndPtr -> data = dt;
ndPtr -> next = nxt;
return ndPtr;
}
}
sizeof (node_t) は，ノード構造体のメモリサイズである．その容量のメモリを malloc で割り当てて，それを指すポインタを ndPtr に代入している．その値が NULL ならば割り当て失敗であるので， NULL を返す．そうでなければ，構造体の各メンバを初期化して，ndPtr の値を返している．
使用例
node_t *ndPtr;
ndPtr = nodeNew(10, NULL);
この例は，10 をデータとして持ち，次に繋がるノードがないノードを作って，そのアドレスを ndPtr に入れている．
コンパイル時に，
warning: assignment makes pointer from integer without a cast
という警告が出るときは，プログラムの先頭に
#include <stdlib.h>
を書き忘れている． malloc はこのヘッダファイルで宣言されている．
線形リスト自体を表す型について説明する．
線形リスト自体は，線形リストを構成するノードの中で最初のものを指すポインタである．したがって，線形リスト型という型を特に定義する必要はない．線形リストを表す list という名前の変数を宣言するには，次のようにすればよい。
node_t *list;
以下，線形リストを表す変数はこのように宣言する．しかし，線形リスト型というものに名前を付けたければ，次のような型名を定義しておくのも一つの方法である．
typedef node_t *list_t;
このようにしておけば，list_t を node_t * の代わりに使用して， 次のように宣言することができる。
list_t list;
Ｃ言語の一つのコーディングスタイルとして，プログラマが定義した型名には _t を名前の最後につける，という書き方がある．その利点には次のことがある．
ノードのためのメモリ割り当て，リスト内のデータの表示，ノードの追加，挿入，削除などの，線形リスト操作のための関数群を定義する．
以下で定義する関数のうち，データ内容の表示を行う listPrint 以外の関数は，リストを変形する関数である．それらの関数の場合，引数の値に与えられたリスト，すなわち node_t * 型の変数を，関数の方で書き換える必要が生じることがある．したがって，これらの関数の引数は，リストを表す node_t * ではなく，リストへのポインタ node_t ** としなくてはならない．
たとえば，リストの先頭に新しいノードを付け加える関数 nodePrepend を例にとって解説しよう．
node_t * 型変数，すなわちノード型ポインタ変数 list が，線形リストの最初のノードを指しているとする．この線形リストの先頭に新しいノードを加えて，その先頭を指すように list の値を変えたいとする．次図では，緑色が操作前のlist の値を，青色が新しいノードと操作後の list の値とを表している．
この操作を nodePrepend という関数にやらせようと思うとき， nodePrepend には， list の値（緑の矢印）を渡したのではどうしようもない．list という変数の値を変更するためには， list の値ではなく， list という変数の場所，すなわち list を指すポインタ（赤の矢印）が必要なのである．list が node_t * すなわちノード型ポインタという型を持っているのであれば，list を指すポインタは node_t ** すなわちノード型ポインタ型ポインタという型になる（これが図の上方から list を指している ndPtrPtr である）。
引数名あるいは変数名に使われている， ndPtr は node pointer, ndPtrPtr は node pointer pointer という意味のつもりである．
最初に，関数値の戻り値をマクロ定数として定義しておく．
#define SUCCESS 1 /* 成功 */ #define FAILURE 0 /* 失敗 */
データ内容の表示
void listPrint(node_t *ndPtr)
{
printf("{ ");
while (ndPtr != NULL) {
printf("%d ", ndPtr->data);
ndPtr = ndPtr -> next;
}
printf("}\n");
}
ndPtr が NULL になるまで，ndPtr が指すノードの next の値で ndPtr の値を置き換えながら，data を表示している．
この関数は線形リストの内容を表示するだけなので，実引数であるリストの先頭を指すポインタ変数の値を変更することはない．従って，引数に渡されるのは，リストの先頭を指すポインタの値であればよい．
データ型 data_t を変更するときには，この関数内の "%d" の部分を実際の型に対応するように書き換える必要がある．
練習問題１： リスト中のノード数を返す関数 int nodeCount(node_t * ndPtr) を作れ．
解答解説
これ以降は，リストを変形するための関数である．リストの始まりを示すポインタ変数 （node_t * 型）の値を，関数内で変更する必要があるので，リストの始まりを示す引数は，さらにそのポインタ変数を指すポインタ node_t ** 型となっている．
まずは，リストの先頭に新しいノードを作って追加をする関数である．
int nodePrepend(node_t **ndPtrPtr, data_t dt)
{
node_t * ndPtr;
ndPtr = nodeNew(dt, *ndPtrPtr);
if (ndPtr == NULL) return FAILURE;
*ndPtrPtr = ndPtr;
return SUCCESS;
}
node_t *list;
と宣言されたノード型ポインタ変数 list が線形リストの先頭ノードを指しているとき， この関数
nodePrepend(dt, &list);
を実行すると，新しいノードがどのように付け加わるかを，次の図式で表した．緑色は操作前のつながり方を表し，青色は操作後の新しいノードとつながり方とを表す．関数の仮引数
ndPtrPtr には， list のアドレスが引き渡されるので， ndPtrPtr は変数 list を指すポインタになる．
新しくできた青いノードの next の値は，以前に先頭であったノードを指す．その値は *ndPtrPtr の値と同じであるので， nodeNew(dt, *ndPtrPtr) として，新しいノードを作ればよい．その後で，list すなわち *ndPtrPtr の値を新しいノードへのポインタ値に変更する．
リストの最後尾に，新しいノードを作って追加する関数である．
int nodeAppend(node_t **ndPtrPtr, data_t dt)
{
node_t * ndPtr;
ndPtr = nodeNew(dt, NULL);
if (ndPtr == NULL) return FAILURE;
while (*ndPtrPtr != NULL) {
ndPtrPtr = &((*ndPtrPtr)->next);
}
*ndPtrPtr = ndPtr;
return SUCCESS;
}
この関数には，さきほどの nodePrepend にはない，次の部分がある。
while (*ndPtrPtr != NULL) {
ndPtrPtr = &((*ndPtrPtr)->next);
}
ここでは，リストの最後尾を見つけるために，*ndPtrPtr の値が NULL になるまで，next を次々とたどっている．
*ndPtrPtr = (*ndPtrPtr)->next;
として，*ndPtrPtr の値を変更しているのではなく，
ndPtrPtr = &((*ndPtrPtr)->next);
として，ndPtrPtr 自身の値を変更していることに注意しよう．
日本語でこの部分を説明すると，「 ndPtrPtr が指していたポインタが指す構造体の nextメンバを指すように，ndPtrPtr の値を変更する」となる．
リストの先頭を指すノード型ポインタ変数 list に対して， nodeAppend(dt, &list) を実行したときの動きを，図示する． ここで， ndPtrPtr が指しているのは，ノードではなくて，ノード内の next メンバであることに注意せよ。
もしも，list が NULL ポインタ，すなわちリストを構成するノードがない場合は， list 自身が書き換わる。
リスト中の指定された場所に，新しいノードを作って挿入する関数を作る。
int nodeInsert(node_t **ndPtrPtr, int n, data_t dt)
{
int i;
node_t * ndPtr;
if (n < 0) return FAILURE;
for (i = 0; i < n && *ndPtrPtr != NULL; i++) {
ndPtrPtr = &((*ndPtrPtr)->next);
}
if (i < n) return FAILURE;
ndPtr = nodeNew(dt, *ndPtrPtr);
if (ndPtr == NULL) return FAILURE;
*ndPtrPtr = ndPtr;
return SUCCESS;
}
for 文は，n 回ループするか，*ndPtrPtr が NULL になれば終了する． for 文の終了時点で i < n が成立しているならば，それは for 文のループ回数が n 回に満たないことを意味し， それは挿入前のリスト長が n 未満であることになり， FAILURE を返している． 新しいノードの next に *ndPtrPtr の値を入れて，*ndPtrPtr に新しいノードのアドレスを入れれば，挿入が達成される．
リスト中の指定されたノードを削除する関数を作る．
int nodeDelete(node_t **ndPtrPtr, int n)
{
node_t * ndPtr;
while (n > 0 && *ndPtrPtr != NULL) {
ndPtrPtr = &((*ndPtrPtr)->next);
n--;
}
if (*ndPtrPtr != NULL) {
ndPtr = (*ndPtrPtr)->next;
free(*ndPtrPtr);
*ndPtrPtr = ndPtr;
return SUCCESS;
} else {
return FAILURE;
}
}
while ループが終了したときに，*ndPtrPtr は， n 番目のノードまたは NULL を指すノード型ポインタ変数となっている．*ndPtrPtr が NULL でなければ，それは n 番目のノードを指すポインタであるから，そのポインタ *ndPtrPtr の値を，そのポインタが指すノードの next メンバの値で置き換える．同時に，そのノードに割り当てられたメモリを解放する．
ノード型ポインタ変数 list で指されたリストに対して，nodeDelete(&list, n) を施したときの動きを図示する．緑色が操作前のつながりで，青色が操作後のつながりである．□はそのn+1番目のノードあるいはNULLポインタ値を表す．
リスト操作関数使用例以上の関数の具体的な使用例を載せておく．
main()
{
node_t *list = NULL;
listPrint(list);
nodeAppend(&list, 1); /* { 1 } */
listPrint(list);
nodeAppend(&list, 2); /* { 1 2 }*/
listPrint(list);
nodePrepend(&list, 3); /* { 3 1 2 } */
listPrint(list);
nodeInsert(&list, 2, 4); /* { 3 1 4 2 } */
listPrint(list);
nodeInsert(&list, 0, 5); /* { 5 3 1 4 2 } */
listPrint(list);
nodeInsert(&list, 5, 6); /* { 5 3 1 4 2 6 } */
listPrint(list);
nodeDelete(&list, 3); /* { 5 3 1 2 6 } */
listPrint(list);
nodeDelete(&list, 0); /* { 3 1 2 6 } */
listPrint(list);
}
{ }
{ 1 }
{ 1 2 }
{ 3 1 2 }
{ 3 1 4 2 }
{ 5 3 1 4 2 }
{ 5 3 1 4 2 6 }
{ 5 3 1 2 6 }
{ 3 1 2 6 }
練習問題２： *ndPtrPtr が指すリストの最後に ndPtr が指すリストを結合して一つのリストにする関数 int listConcaten(node_t ** ndPtrPtr, node_t * ndPtr) を作れ．
解答解説
関数仕様が書かれていないときは，それを考えることも問題です。
List-1 （レベルＡ）
ndPtr から始まる線形リスト中のノードで，データ値が dt であるものを探してそのノードへのポインタを返す関数
node_t * nodeSearch(node_t * ndPtr, data_t dt)
を作れ．
ただし，データ値が dt であるノードが複数個ある場合には，そのうちの先頭に近いノードへポインタを返し，データ値が dt であるノードがない場合には NULL を返すものとする．
List-2 （レベルＢ）
線形リストを複写する関数 int listCopy(node_t * src, node_t ** dest) を作れ． 戻り値は，複写に成功すれば SUCCESS，失敗すれば FAILURE とする．
List-3 （レベルＢ）
線形リスト全体を削除する関数 void listDelete(node_t ** list) を作れ．ノードをすべて削除した後， *list の値を NULLにする．（ノードに割り当てられたメモリを解放することを忘れないように）
List-5 （レベルＢ＋）
本文中で作った nodeInsert を改良して，指定された挿入場所のインデックス n が負のときには，
新しく挿入されたノードがリストの末尾から数えて -n 番目になるようにせよ．
（たとえば，n == -1 のときには，末尾に挿入される）