Linux Programming

連結リスト

今回はＣ言語の簡単な例題として、「連結リスト (linked list)」という基本的なデータ構造を作ってみましょう。

●連結リストとは？

連結リストはデータを一方向につなげたデータ構造です。リストを操作するプログラミング言語では Lisp が有名ですが、Lisp で扱うリストが連結リストです。下図に連結リストの構造を示します。

                  図 : 連結リスト

連結リストはセル (cell) というデータを繋げて作ります。セルにはデータを格納する場所と、次のセルを指し示す場所から構成されます。図でいうと、箱がひとつのセルを表していて、左側にデータを格納し、右側に次のセルへのポインタを格納します。リストの終わりを示すため、最後のセルの右側には特別な値（たとえば NULL）を格納します。そして、図 (1) のように先頭セルへの参照を変数に格納しておけば、この変数を使って連結リストにアクセスすることができます。また、図 (2) のようにヘッダセルを用意する方法もあります。

連結リストの長所は、データの挿入や削除が簡単にできることです。配列でデータの削除や挿入を行う場合、要素を移動しなければいけませんが、連結リストはセルを付け替えるだけで実現できます。逆に、配列はどの要素にも一定の時間でアクセスすることができますが、連結リストはセルを順番にたどっていくため、後ろのデータほどアクセスに時間がかかります。これが連結リストの短所です。

●データ型の定義

それではプログラムを作りましょう。今回は簡単な例題なので、格納するデータ型は int とします。最初に連結リストを格納する構造体 List とセルを表す構造体 Cell を定義します。次のリストを見てください。

リスト : 連結リストの定義

// セル
typedef struct cell {
  int item;
  struct cell *next;
} Cell;

// リスト
typedef struct {
  Cell *top;
} List;

Cell のメンバ変数 item にデータを格納し、next に次のセルへのポインタを格納します。構造体は自分自身を格納することはできませんが、自分自身へのポインタであれば格納することができます。これを「自己参照構造体」といいます。構造体の中で自分自身のデータ型 (struct cell) が必要になるので、タグ名 cell を省略することはできません。List は簡単で、セルを格納するメンバ変数 top を保持するだけです。

あとは、連結リストを操作する関数を定義します。基本的な操作関数を下表に示します。

要素の位置は配列と同様に 0 から数えることにします。位置 n がリストの要素数（長さ）よりも多い場合、nth は *err に false をセットして 0 を返します。リストが空の場合、pop は *err に false をセットして 0 を返します。あとは特に難しいところはないと思います。

上表のように、連結リストの操作関数は引数に List へのポインタを受け取ります。セルを操作する関数は、これらの関数を実現するための作業用関数になります。このような場合、上表の連結リスト操作関数だけをユーザに公開して、作業用の関数は非公開にできると、ユーザが作業用関数を呼び出してしまう間違いを防ぐことができます。Ｃ言語の場合、ファイル単位でアクセス制御を行うことができます。これは「分割コンパイル」を説明するときに試してみましょう。

●連結リストの生成と廃棄

まずは最初にコンストラクタから作ります。

リスト : コンストラクタ

// セルの生成
Cell *make_cell(int val, Cell *cp)
{
  Cell *newcp = malloc(sizeof(Cell));
  if (newcp != NULL) {
    newcp->item = val;
    newcp->next = cp;
  }
  return newcp;
}

// リストの生成
List *make_list(void)
{
  List *ls = malloc(sizeof(List));
  if (ls != NULL) {
    ls->top = make_cell(0, NULL);  // ヘッダセルをセット
    if (ls->top == NULL) {
      free(ls);
      return NULL;
    }
  }
  return ls;
}

関数 make_cell は新しいセルを malloc で取得し、メンバ変数 item と next を引数 val と cp で初期化します。make_list は List 本体を malloc で取得し、ヘッダセルを make_cell で生成してメンバ変数 top にセットします。このとき、ヘッダセルの next は NULL で初期化します。これでリストは空リストになります。なお、ヘッダセルの item の値 (0) はダミーデータになります。

次はリストとセルを廃棄する関数 delete_list と delete_cell を作ります。

リスト : 廃棄

// セルの削除
void delete_cell(Cell *cp)
{
  while (cp != NULL) {
    Cell *temp = cp->next;
    free(cp);
    cp = temp;
  }
}

// リストの削除
void delete_list(List *ls)
{
  delete_cell(ls->top);
  free(ls);
}

関数 delete_cell はセルを順番にたどり、free でセルを解放します。次のセル (next) を変数 temp に退避しておいて、free(cp) を実行したあと、temp を cp にセットします。delete_list は簡単で、delete_cell でヘッダセルから後続のセルを開放してから、free で List 本体を解放します。

●n 番目のセルを求める

次は、セルを操作するときに便利な関数 nth_cell を作ります。nth_cell は n 番目のセルを求めます。

リスト : n 番目のセルを求める

// n 番目のセルを返す
Cell *nth_cell(Cell *cp, int n)
{
  for (int i = -1; cp != NULL; i++, cp = cp->next)
    if (i == n) break;
  return cp;
}

引数 cp にはヘッダセル top を渡します。ヘッダセルから数えるので、変数 i は -1 に初期化します。次に、for ループでセルをたどり、i が n と等しくなったとき、そのセルを return で返します。

セルのたどり方は実に簡単です。次の図を見てください。

  (1) cp = cp->next => cp2
  (2) cp = cp->next => cp3

      図 : セルのたどり方

セル cp1 の next にはセル cp2 へのポインタが格納されています。変数 cp が cp1 の場合、cp = cp->next とすれば、cp の値はセル cp2 になります (図 (1))。さらに cp = cp->next とすれば、cp の値は cp3 になります (図 (2))。nth_cell の場合、for ループでセルをたどっていきますが、途中でセルがなくなった場合、cp の値は NULL になるので for ループを終了して NULL を返します。

●データの参照

次は、n 番目の要素を求める関数 nth を作ります。

リスト : n 番目の要素を求める

int nth(List *ls, int n, bool *err)
{
  Cell *cp = nth_cell(ls->top, n);
  if (cp == NULL) {
    *err = false;
    return 0;
  }
  *err = true;
  return cp->item;
}

関数 nth_cell を呼び出して n 番目のセルを求めます。cp が NULL の場合は *err に false をセットしてから return で 0 を返します。そうでなければ、*err に true をセットして、格納されているデータ cp->item を返します。

●データの挿入

次は、データの挿入を行う関数 insert_nth を作ります。データの挿入はセルの next を書き換えることで実現できます。次の図を見てください。セル (1) とセル (2) の間に、セル (3) を挿入します。

              図 : データの挿入

セル (1) の後ろにセル (3) を挿入する場合、セル (1) の next にはセル (2) へのポインタがセットされているので、この値をセル (3) の next にセットします。これで、セル (3) とセル (2) がリンクされます。次に、セル (1) の next にセル (3) へのポインタをセットします。これで、セル (1) とセル (2) の間に、セル (3) を挿入することができます。

プログラムは次のようになります。

リスト : データの挿入

bool insert_nth(List *ls, int n, int x)
{
  Cell *cp = nth_cell(ls->top, n - 1);
  if (cp == NULL) return false;
  cp->next = make_cell(x, cp->next);
  return true;
}

// 先頭に追加
bool push(List *ls, int x)
{
  return insert_nth(ls, 0, x);
}

連結リストにデータを挿入する場合、挿入する位置のひとつ手前のセルが必要になります。nth_cell で n - 1 番目のセルを求めます。セル cp が見つかれば、cp の後ろに x を挿入します。n が 0 の場合、nth_cell はヘッダセルを返すので、リストの先頭にデータが挿入されることになります。

make_cell(x, cp->next) で x を格納する新しいセルを生成します。第 2 引数に cp->next を指定することで、新しいセルの後ろに、cp の次のセルを接続することができます。そして、cp->next の値を新しいセルに書き換えます。これで cp の後ろに新しいセルを挿入することができます。最後に true を返します。先頭にデータを追加する関数 push は insert_nth を呼び出すだけです。

●データの削除

次は、データを削除する関数 delete_nth を作ります。

        図 : データの削除

データを削除する場合も、セルを付け替えるだけで済ますことができます。上図を見てください。セル (1) の後ろにあるセル (2) を削除する場合、セル (1) の next をセル (3) へのポインタに書き換えればいいのです。セル (3) はセル (2) の next から求めることができます。たとえば、セル (1) を保持する変数を cp とすると、セル (3) は cp->next->next で求めることができます。とても簡単ですね。

プログラムは次のようになります。

リスト : データの削除

// n 番目の要素を削除
bool delete_nth(List *ls, int n)
{
  Cell *cp = nth_cell(ls->top, n - 1);
  if (cp == NULL || cp->next == NULL) return false;
  Cell *temp = cp->next;
  cp->next = cp->next->next;
  free(temp);
  return true;
}

// 先頭から要素を取り出す
int pop(List *ls, bool *err)
{
  int x = nth(ls, 0, err);
  if (*err) delete_nth(ls, 0);
  return x;
}

データを削除する場合も、削除する位置のひとつ手前のセルが必要になります。nth_cell で n - 1 番目のセルを求めます。次に、削除するセルがあるか cp->next の値をチェックします。値が NULL でなければ、cp->next の値を cp->next->next に書き換えるだけです。これで連結リストから n 番目の要素を削除することができます。なお、標準のＣ言語ではガベージコレクション (GC) がないので、削除したセルは free で解放することを忘れないでください。

関数 pop は簡単です。nth で先頭要素の値を参照して変数 x にセットします。エラーがなければ delete_nth で先頭セルを削除して、return で x を返します。エラーが発生した場合、*err には false、変数 x には 0 がセットされているので、x をそのまま返すだけで OK です。

あとのプログラムは簡単なので説明は割愛します。詳細は プログラムリスト１ をお読みください。

●実行例

それでは実行してみましょう。

リスト : 簡単な実行例

int main(void)
{
  List *ls = make_list();
  bool err;
  for (int i = 0; i < 8; i++) {
    push(ls, i + 10);
    print_list(ls);
  }
  insert_nth(ls, 3, 100);
  print_list(ls);
  insert_nth(ls, 9, 200);
  print_list(ls);
  for (int i = 0; i < 11; i++) {
    int x = nth(ls, i, &err);
    printf("%d, %d\n", x, err);
  }
  delete_nth(ls, 0);
  print_list(ls);
  delete_nth(ls, 5);
  print_list(ls);
  delete_nth(ls, 7);
  print_list(ls);
  while (!empty_list(ls)) {
    int x = pop(ls, &err);
    printf("%d, %d\n", x, err);
    print_list(ls);
  }
  delete_list(ls);
  return 0;
}

$ clang linklist0.c
$ ./a.out
( 10 )
( 11 10 )
( 12 11 10 )
( 13 12 11 10 )
( 14 13 12 11 10 )
( 15 14 13 12 11 10 )
( 16 15 14 13 12 11 10 )
( 17 16 15 14 13 12 11 10 )
( 17 16 15 100 14 13 12 11 10 )
( 17 16 15 100 14 13 12 11 10 200 )
17, 1
16, 1
15, 1
100, 1
14, 1
13, 1
12, 1
11, 1
10, 1
200, 1
0, 0
( 16 15 100 14 13 12 11 10 200 )
( 16 15 100 14 13 11 10 200 )
( 16 15 100 14 13 11 10 )
16, 1
( 15 100 14 13 11 10 )
15, 1
( 100 14 13 11 10 )
100, 1
( 14 13 11 10 )
14, 1
( 13 11 10 )
13, 1
( 11 10 )
11, 1
( 10 )
10, 1
( )

正常に動作していますね。

●分割コンパイル

Ｃ言語で大きいプログラムを作る場合、ソースファイルを機能単位 (または他の基準) で複数のファイルに分割して管理することがよく行われます。Ｃ言語の場合、分割したファイルを個別にコンパイルすることが可能で、そのあとオブジェクトファイル (拡張子が .o のファイル) をリンクで結合すれば、実行ファイルを生成することができます。これを「分割コンパイル (separate compilation)」といいます。

プログラムのテスト段階になると、不具合を見つけては修正し、またテストを行うということを繰り返します。ソースファイルを修正したあと再コンパイルするのですが、ファイルが大きいとコンパイルに時間がかかります。ファイルを分割しておけば、修正したファイルだけコンパイルすればいいので、コンパイル時間を短縮することができるわけです。

簡単な例として、今回作成した連結リスト (プログラムリスト) を main.c と linklist.c に分割してみましょう。ファイルを分割する場合、linklist.c に定義されているデータ型や関数などの情報を main.c に知らせる必要があります。これにはヘッダファイルを使います。

Ｃ言語ユーザならば、標準ライブラリを使用するときにヘッダファイルをインクルードしているはずです。ヘッダファイルには、そのライブラリで使用できる関数のプロトタイプ宣言、マクロ、構造体の定義などが格納されています。たとえば、stdio.h では FILE 構造体が定義され、fgetc や fputc などの入出力関数のプロトタイプ、stdin, stdout, stderr などのマクロが宣言されています。

プロトタイプは、関数の引数と返り値の型を前もって宣言することです。そうすることで、コンパイル時において型チェックを行うことができます。ANSI C 規格 (C89/C90) 以前のコンパイラにはこの機能がないので、引数の型が間違っていてもそのままコンパイルされてしまい、不具合の原因になることがあったようです。

●ヘッダファイルの定義

それでは、ヘッダファイルを書いてみましょう。

リスト : linklist.h

#ifndef _LINKLIST_H_
#define _LINKLIST_H_

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

// セル
typedef struct cell {
  int item;
  struct cell *next;
} Cell;

// リスト
typedef struct {
  Cell *top;
} List;

// 関数宣言
List *make_list(void);
void delete_list(List *ls);
int nth(List *ls, int n, bool *err);
bool insert_nth(List *ls, int n, int x);
bool delete_nth(List *ls, int n);
bool push(List *ls, int x);
int pop(List *ls, bool *err);
bool empty_list(List *ls);
void print_list(List *ls);

#endif

#ifndef はプリプロセッサ指令です。

#ifndef マクロ
  処理１
#else
  処理２
#endif

マクロが定義されていなければ、処理 1 の展開を行い、定義されていれば処理 2 の展開を行います。linklist.h の場合、_LINKLIST_H_ が定義されていなければ _LINKLISH_H_ を定義します。それから、必要なヘッダファイルの読み込みと構造体の定義と関数宣言を行います。_LINKLIST_H_ が定義されている場合は何も行いません。

標準ライブラリ のヘッダファイルも同様な処理がなされていて、stdio.h ならば _STDIO_H のマクロをチェックしています。これは、ヘッダファイルを何回読み込んでもコンパイルできるようにするためです。たとえば、linklist.h では stdbool.h を読み込んでいますね。ほかのヘッダファイルでも stdbool.h を読み込んでいるものがあるかもしれません。単純に読み込むだけでは、stdbool.h での定義は二重に定義されたとしてコンパイルエラーになってしまいます。

それでは、linklist.h で stdbool.h の読み込み (インクルード) をやめればいいはずです。しかし、今度は stdbool.h をインクルードしないヘッダファイルといっしょに使用する場合に困ってしまいます。linklist.h を使う場合は、ほかのヘッダファイルを調べてから stdbool.h をインクルードしてください、というのではとても使いにくいですね。ヘッダファイル側で二重定義にならないように工夫されているので、ほかのヘッダファイルの内容まで考えなくて済むのです。

ヘッダファイルは、ユーザにとってそのライブラリの顔を意味しています。ヘッダファイルを見れば、そのライブラリの機能概要や使い方がわかるように、きちんと書いておくといいでしょう。

●static 宣言

次は linklist.c を修正します。プログラムリスト３ を見てください。関数 make_cell, delete_cell, nth_cell の前に static が付いています。関数名の前にある static は、関数名がこのファイルの中だけ有効であることを示します。プロトタイプ宣言されていないので、他のファイルでこれらの関数を呼び出すとワーニングが表示されます。それを無視してコンパイルすると、リンクでエラーが発生して実行ファイルは作成できません。

static は関数だけではなく変数にも宣言することができます。ソースファイルがひとつの場合には、関数や変数を static 宣言する必要はありませんが、大きなプログラムを複数のソースファイルに分けて作る場合、関数や変数の static 宣言はとても重要になります。変数の static 宣言は必要になったら説明することにしましょう。

●実行ファイルの作成

最後に main.c を作ります。

リスト : main.c 

#include <stdio.h>
#include "linklist.h"

int main(void)
{
  List *ls = make_list();
  bool err;
  for (int i = 0; i < 8; i++) {
    push(ls, i + 10);
    print_list(ls);
  }
  insert_nth(ls, 3, 100);
  print_list(ls);
  insert_nth(ls, 9, 200);
  print_list(ls);
  for (int i = 0; i < 11; i++) {
    int x = nth(ls, i, &err);
    printf("%d, %d\n", x, err);
  }
  delete_nth(ls, 0);
  print_list(ls);
  delete_nth(ls, 5);
  print_list(ls);
  delete_nth(ls, 7);
  print_list(ls);
  while (!empty_list(ls)) {
    int x = pop(ls, &err);
    printf("%d, %d\n", x, err);
    print_list(ls);
  }
  delete_list(ls);
  return 0;
}

#include 命令で "..." を指定すると、カレントディレクトリからヘッダファイルを探します。見つからない場合は、標準ライブラリのヘッダファイルと同じディレクトリを探します。一般に、ユーザが定義したヘッダファイルはソースファイル (.c) と同じディレクトリに置き、#include "..." でインクルートします。main.c で printf を使っているので stido.h もインクルードしていますが、二重定義でエラーが発生することはありません。

分割したファイルをコンパイルするのは簡単です。今回のように小さなプログラムでは、次のように複数のソースファイルを指定するだけで十分です。

clang -o linklist main.c linklist.c

これで実行ファイル linklist を生成することができます。

ソースファイルを個別にコンパイルすることもできます。この場合、コンパイルオプションに -c を追加してリンクを実行しないようにします。

$ clang -c main.c
$ clang -c linklist.c
$ ls *.o
linklist.o  main.o

オブジェクトファイル main.o と linklist.o が出力されます。オブジェクトファイルだけでは実行ファイルを作ることはできません。ライブラリから実行ファイルを作るのに必要な関数を探して、その関数を結合しないといけません。この作業が「リンク」です。リンクも簡単で、コンパイラにオブジェクトファイルを指定すれば、そのファイルをリンクしてくれます。

$ clang -o linklist main.o linklist.o
$ ls linklist
linklist

オブジェクトファイルをリンクによって結合し、それでも足りない関数があれば、ライブラリから探して結合します。リンク作業が正常に終了すると、実行ファイルが完成します。この作業によく使用されるツールが make です。

make は、ソースファイルの日付と実行ファイルもしくはオブジェクトファイルの日付を比較して、ソースファイルが変更されていれば、指定した処理（コンパイルやリンク）を自動的に行ってくれるツールです。Makefile というファイルに必要な処理を記述しておけば、make を起動するだけで、その処理を行ってくれます。ちょっと大きなプログラムを作る場合、make はなくてはならない必須ツールです。

最近は Makefile を自分で作るのではなく、自動的に生成するツールを使うことが多いようですが、M.Hiroi は勉強不足でよくわかりません。make だけならば、それほど難しいことはないので、使うときに説明することにしましょう。

●プログラムリスト１

/*
 * linklist0.c : 連結リスト
 *
 *              Copyright (C) 2015-2023 Makoto Hiroi
 */
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

// セル
typedef struct cell {
  int item;
  struct cell *next;
} Cell;

// リスト
typedef struct {
  Cell *top;
} List;

// コンストラクタ
Cell *make_cell(int val, Cell *cp)
{
  Cell *newcp = malloc(sizeof(Cell));
  if (newcp != NULL) {
    newcp->item = val;
    newcp->next = cp;
  }
  return newcp;
}

List *make_list(void)
{
  List *ls = malloc(sizeof(List));
  if (ls != NULL) {
    ls->top = make_cell(0, NULL);  // ヘッダセルをセット
    if (ls->top == NULL) {
      free(ls);
      return NULL;
    }
  }
  return ls;
}

// 解放
void delete_cell(Cell *cp)
{
  while (cp != NULL) {
    Cell *temp = cp->next;
    free(cp);
    cp = temp;
  }
}

void delete_list(List *ls)
{
  delete_cell(ls->top);
  free(ls);
}

// n 番目のセルを返す
Cell *nth_cell(Cell *cp, int n)
{
  for (int i = -1; cp != NULL; i++, cp = cp->next)
    if (i == n) break;
  return cp;
}

// n 番目の要素を返す
int nth(List *ls, int n, bool *err)
{
  Cell *cp = nth_cell(ls->top, n);
  if (cp == NULL) {
    *err = false;
    return 0;
  }
  *err = true;
  return cp->item;
}

// n 番目に x を挿入
bool insert_nth(List *ls, int n, int x)
{
  Cell *cp = nth_cell(ls->top, n - 1);
  if (cp == NULL) return false;
  cp->next = make_cell(x, cp->next);
  return true;
}

// n 番目の要素を削除
bool delete_nth(List *ls, int n)
{
  Cell *cp = nth_cell(ls->top, n - 1);
  if (cp == NULL || cp->next == NULL) return false;
  Cell *temp = cp->next;
  cp->next = cp->next->next;
  free(temp);
  return true;
}

// 先頭に追加
bool push(List *ls, int x)
{
  return insert_nth(ls, 0, x);
}

// 先頭から要素を取り出す
int pop(List *ls, bool *err)
{
  int x = nth(ls, 0, err);
  if (*err) delete_nth(ls, 0);
  return x;
}

// リストは空か
bool empty_list(List *ls)
{
  return ls->top->next == NULL;
}

// リストの表示
void print_list(List *ls)
{
  printf("( ");
  for (Cell *cp = ls->top->next; cp != NULL; cp = cp->next)
    printf("%d ", cp->item);
  printf(")\n");
}

int main(void)
{
  List *ls = make_list();
  bool err;
  for (int i = 0; i < 8; i++) {
    push(ls, i + 10);
    print_list(ls);
  }
  insert_nth(ls, 3, 100);
  print_list(ls);
  insert_nth(ls, 9, 200);
  print_list(ls);
  for (int i = 0; i < 11; i++) {
    int x = nth(ls, i, &err);
    printf("%d, %d\n", x, err);
  }
  delete_nth(ls, 0);
  print_list(ls);
  delete_nth(ls, 5);
  print_list(ls);
  delete_nth(ls, 7);
  print_list(ls);
  while (!empty_list(ls)) {
    int x = pop(ls, &err);
    printf("%d, %d\n", x, err);
    print_list(ls);
  }
  delete_list(ls);
  return 0;
}

●プログラムリスト２

/*
 * linklist.h : 連結リスト
 *
 *              Copyright (C) 2015-2023 Makoto Hiroi
 */
#ifndef _LINKLIST_H_
#define _LINKLIST_H_

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

// セル
typedef struct cell {
  int item;
  struct cell *next;
} Cell;

// リスト
typedef struct {
  Cell *top;
} List;

// 関数宣言
List *make_list(void);
void delete_list(List *ls);
int nth(List *ls, int n, bool *err);
bool insert_nth(List *ls, int n, int x);
bool delete_nth(List *ls, int n);
bool push(List *ls, int x);
int pop(List *ls, bool *err);
bool empty_list(List *ls);
void print_list(List *ls);

#endif

●プログラムリスト３

/*
 * linklist.c : 連結リスト
 *
 *              Copyright (C) 2015-2023 Makoto Hiroi
 */
#include "linklist.h"

// コンストラクタ
static Cell *make_cell(int val, Cell *cp)
{
  Cell *newcp = malloc(sizeof(Cell));
  if (newcp != NULL) {
    newcp->item = val;
    newcp->next = cp;
  }
  return newcp;
}

List *make_list(void)
{
  List *ls = malloc(sizeof(List));
  if (ls != NULL) {
    ls->top = make_cell(0, NULL);  // ヘッダセルをセット
    if (ls->top == NULL) {
      free(ls);
      return NULL;
    }
  }
  return ls;
}

// 解放
static void delete_cell(Cell *cp)
{
  while (cp != NULL) {
    Cell *temp = cp->next;
    free(cp);
    cp = temp;
  }
}

void delete_list(List *ls)
{
  delete_cell(ls->top);
  free(ls);
}

// n 番目のセルを返す
static Cell *nth_cell(Cell *cp, int n)
{
  for (int i = -1; cp != NULL; i++, cp = cp->next)
    if (i == n) break;
  return cp;
}

// n 番目の要素を返す
int nth(List *ls, int n, bool *err)
{
  Cell *cp = nth_cell(ls->top, n);
  if (cp == NULL) {
    *err = false;
    return 0;
  }
  *err = true;
  return cp->item;
}

// n 番目に x を挿入
bool insert_nth(List *ls, int n, int x)
{
  Cell *cp = nth_cell(ls->top, n - 1);
  if (cp == NULL) return false;
  cp->next = make_cell(x, cp->next);
  return true;
}

// n 番目の要素を削除
bool delete_nth(List *ls, int n)
{
  Cell *cp = nth_cell(ls->top, n - 1);
  if (cp == NULL || cp->next == NULL) return false;
  Cell *temp = cp->next;
  cp->next = cp->next->next;
  free(temp);
  return true;
}

// 先頭に追加
bool push(List *ls, int x)
{
  return insert_nth(ls, 0, x);
}

// 先頭から要素を取り出す
int pop(List *ls, bool *err)
{
  int x = nth(ls, 0, err);
  if (*err) delete_nth(ls, 0);
  return x;
}

// リストは空か
bool empty_list(List *ls)
{
  return ls->top->next == NULL;
}

// リストの表示
void print_list(List *ls)
{
  printf("( ");
  for (Cell *cp = ls->top->next; cp != NULL; cp = cp->next)
    printf("%d ", cp->item);
  printf(")\n");
}