「アルゴリズムとデータ構造」資料 5連結リスト
鴨 浩靖

2009 年 10 月 27 日 初版
2011 年 10 月 25 日 第二版改2013 年 10 月 22 日 第三版
2019 年 10 月 30 日 第四版

1 / 49配列の長所と短所

配列の長所▶ どの要素もほぼ同じ時間でアクセスできる▶ メモリ効率が良い
配列の短所▶ 挿入・削除に時間がかかる▶ 途中で大きさが変更できない

2 / 49配列への要素の挿入
矢印の位置に挿入したい

α β γ δ ε ζ η θ ι

3 / 49配列への要素の挿入 (つづき 1)
まず、最後の要素をずらす

α β γ δ ε ζ η θ ι

ι

4 / 49配列への要素の挿入 (つづき 2)
次に、最後の一つ前の要素をずらす

α β γ δ ε ζ η θ θ ι

5 / 49配列への要素の挿入 (つづき 3)
さらに、要素をずらす

α β γ δ ε ζ η η θ ι

6 / 49配列への要素の挿入 (つづき 4)
さらに、要素をずらす

α β γ δ ε ζ ζ η θ ι7 / 49

配列への要素の挿入 (つづき 5)
さらに、要素をずらす

α β γ δ ε ε ζ η θ ι8 / 49

配列への要素の挿入 (つづき 6)
さらに、要素をずらす

α β γ δ δ ε ζ η θ ι

9 / 49配列への要素の挿入 (つづき 7)
最後に、空いたところに入れる

α β γ ω δ ε ζ η θ ι

10 / 49

配列への要素の挿入の時間計算量
最悪 O(n)
平均 O(n)
ただし、配列の大きさを n とする。

11 / 49

配列からの要素の削除
矢印の位置の要素を削除したい

α β γ δ ε ζ η θ ικ

12 / 49

配列からの要素の削除 (つづき 1)
矢印の位置に次の要素をずらす

α β γ ε ε ζ η θ ικ

13 / 49

配列からの要素の削除 (つづき 2)
さらに、要素をずらす

α β γ ε ζ ζ η θ ικ

14 / 49

配列からの要素の削除 (つづき 3)
さらに、要素をずらす

α β γ ε ζ η η θ ικ15 / 49

配列からの要素の削除 (つづき 4)
さらに、要素をずらす

α β γ ε ζ η θ θ ικ16 / 49

配列からの要素の削除 (つづき 5)
さらに、要素をずらす

α β γ ε ζ η θ ιικ

17 / 49

配列からの要素の削除 (つづき 6)
さらに、要素をずらす

α β γ ε ζ η θ ικ κ18 / 49

配列からの要素の削除 (つづき 7)
ゴミが残るのは放置

α β γ ε ζ η θ ικ κ

19 / 49

配列からの要素の削除の時間計算量
最悪 O(n)
平均 O(n)
ただし、配列の大きさを n とする。

20 / 49

単方向線形リストの長所と短所

単方向線形リストの長所▶ 挿入・削除が一定の時間でできる▶ 大きさが自由に変更できる
単方向線形リストの短所▶ ランダムアクセスができない▶ 逆向きアクセスができない▶ メモリのオーバヘッドがちょっとある

21 / 49

単方向線形リストへの要素の挿入
矢印のセルの次に挿入したい

αβγ

δεζηθι

κ

22 / 49

単方向線形リストへの要素の挿入 (つづき 1)
新しいセルを生成する

αβγ

δεζ

η

θι

κ

ω

23 / 49

単方向線形リストへの要素の挿入 (つづき 2)
リンクをはる

αβγ

δεζ

ηθικ

ω

24 / 49

単方向線形リストへの要素の挿入 (つづき 3)
リンクをつけかえる

αβγδεζηθικω

25 / 49

単方向線形リストへの要素の挿入の時間計算量
最悪 O(1)
平均 O(1)
ただし、リストの大きさを n とする。

26 / 49

単方向線形リストからの要素の削除
矢印のセルの次のセルを削除したい

αβγ

δ

εζ

η

θ

ι

κ

27 / 49

単方向線形リストからの要素の削除 (つづき 1)
リンクを退避する

αβγ

δεζ

ηθ

ι

κ

28 / 49

単方向線形リストからの要素の削除 (つづき 2)
リンクをつけかえる

αβγ

δ

εζ

η

θι

κ

29 / 49

単方向線形リストからの要素の削除 (つづき 3)
不要なセルを消去する

αβγ

εζ

ηθ

ι

κ

30 / 49

単方向線形リストからの要素の削除の時間計算量
最悪 O(1)
平均 O(1)
ただし、リストの大きさを n とする。

31 / 49

単方向線形リストの先頭への挿入・先頭の削除
説明した方法では、先頭への挿入や先頭の削除はできない。
良く使われる対策は以下のとおり：⋆ 先頭に挿入する関数と先頭を削除する関数を別途作成する。
⋆ 先頭のセルはダミーとする。
⋆ ポインタへのポインタを巧妙に使う。
状況に応じて使い分けること。

32 / 49

単方向線形リストの先頭への要素の挿入
先頭に挿入したい

αβγ

δεζ

ηθι

κ

33 / 49

単方向線形リストの先頭への要素の挿入 (つづき 1)
新しいセルを生成する

αβγ

δεζ

ηθικ

ω

34 / 49

単方向線形リストの先頭への要素の挿入 (つづき 2)
リンクをはる

αβγ

δεζηθικω

35 / 49

単方向線形リストの先頭への要素の挿入 (つづき 3)
リンクをつけかえる

αβγ

δεζηθικω

36 / 49

実装例 1struct head {struct cell};struct cell {struct cellintdouble};*first;*next;
index;
value;

37 / 49

実装例 2struct datum {intdouble};
struct head {struct cell};struct cell {struct cellstruct datum};index;
value;*first;*next;*datum_ptr;

38 / 49

単方向線形リスト

実装例

struct head {struct cell};struct cell {struct cellintdouble};*first;*next;
index;
value;

39 / 49

単方向線形リスト—指定されたセルの次に挿入 実装例
struct cell *slist_insert_after(struct slist *list, struct cell *p,int index, double value){
struct cell*q = malloc(sizeof(struct cell));/* 新しいセルを生成する */q->index = index;/* データをセットする */q->value = value;/* データをセットする */q->next = p->next; /* リンクをはる */p->next = q;/* リンクをつなぎかえる */return q;}

40 / 49

単方向線形リスト—指定されたセルの次のセルを削除
実装例
void
slist_delete_after(struct slist *list, struct cell *p){
struct cell*q = p->next;/* リンクを退避する */p->next = q->next;/* リンクをつなぎかえる */free(q);/* 不要なセルを削除する */}41 / 49

単方向線形リスト—先頭に挿入 実装例

struct cell *slist_insert_first(struct slist *list, int index, double va{
struct cell*q = malloc(sizeof(struct cell));/* 新しいセルを生成する */q->index = index;/* データをセットする */q->value = value;/* データをセットする */q->next = list->first; /* リンクをはる */list->first = q;/* リンクをつなぎかえる */return q;}

42 / 49

単方向線形リスト—先頭のセルを削除 実装例
void
slist_delete_after(struct slist *list){
struct cell*q = list->first;/* リンクを退避する */list->first = q->next; /* リンクをつなぎかえる */free(q);/* 不要なセルを削除する */}43 / 49

単方向線形リストの変種—末尾つき単方向線形リスト

実装例

struct head {struct cellstruct cell};struct cell {struct cellintdouble};*first;*last;*next;
index;
value;

44 / 49

単方向線形リストの変種—単方向循環リスト

実装例

struct head {struct cell};struct cell {struct cellintdouble};*first;*next;
index;
value;

45 / 49

双方向線形リスト

実装例

struct head {struct cell};struct cell {struct cellstruct cellintdouble};*first;*next;*prev;
index;
value;

46 / 49

双方向線形リストの変種—末尾つき実装例

struct head {struct cellstruct cell};struct cell {struct cellstruct cellintdouble};*first;*last;*next;*prev;
index;
value;

47 / 49

双方向線形リストの変種—循環実装例

struct head {struct cell};struct cell {struct cellstruct cellintdouble};*first;*next;*prev;
index;
value;

48 / 49

まとめ▶ 単方向線形リスト▶ 末尾つき単方向線形リスト▶ 単方向循環リスト▶ 双方向線形リスト▶ 末尾つき双方向線形リスト▶ 双方向循環リスト

49 / 49