アルゴリズムと
データ構造
第13回
線形リスト
線形リスト

リスト
 データが順序付けて並べられたデータ構造
 最も単純なもの：線形リスト、連結リスト

単連結リスト、単方向リスト、一方向リストとも
 ノード（要素）
線形リスト上の個々のデータ
 最初のノードは先頭ノード、最後のノードは末尾ノード
 1つ前のノードは先行ノード、1つ後のノードは後続ノード

線形リスト

線形リストの実現（配列版）
 実現方法
用意した配列の先頭からデータを順次格納
 後続ノードへの着目は添え字をインクリメント

 問題点
データを挿入・削除する際、配列内の要素ブロックを移
動する必要あり
 あらかじめ用意した配列の要素数以上のデータは格納
できない

ポインタによる線形リスト

実現方法
 本来のデータと、次のノードを示すポインタを用意

自分自身と同じ構造体型を指すポインタを含む構造体：
自己参照構造体
 データが追加される時点で動的にデータ格納用構
造体を確保

確保した構造体を、次のノードを示すポインタで指す
ポインタによる線形リスト

自己参照構造体によるノード
typedef struct __node {
Menber data;
struct __node *next;
} Node;
/* データを格納する構造体 */
/* 後続ノードへのポインタ */
・ 後続ノードがない場合、nextはNULL
ポインタによる線形リスト

List型構造体
typedef struct {
Node *head;
Node *crnt;
} List;
/*先頭ノードへのポインタ */
/* 現在着目中のノードへのポインタ */
・ headは必須、データがない場合NULL
・ crntは便宜上用意、なくてもよい
ポインタによる線形リスト

ノードの探索
 線形探索でデータを探索
先頭ノードから目的値を持つノードを探索
 探索すべき値と等しい要素を持つノードを見つけたら探
索成功
 探索すべき値が見つからず末尾までいったら探索失敗

ポインタによる線形リスト

ノードの探索
H
・
G
C
N
A
・
B
・
N
成功
を探索：失敗
N
C
・
N
D
・
N
E
・
ポインタによる線形リスト

先頭へのノードの挿入

新規ノードを生成後、ポインタの付け替え
1.
2.
3.
現先頭ノードのポインタを保存
新規ノードを先頭ノードへ
新規ノードの後続ノードを、保存してあったポインタで
置き換え
ポインタによる線形リスト

先頭へのノードの挿入
H
・
N
A
・
N
G
・
N
B
・
P
・
N
C
・
N
D
・
N
E
・
ポインタによる線形リスト

末尾へのノードの挿入

新規ノードを生成後、ポインタの付け替え
1.
2.
3.
headがNULL（データなし）なら先頭にノード挿入
headから、後続ノード（next）がない（NULL）ノードまで
探索
新規ノードを生成し、探索したノードの後続ノードに接
続
ポインタによる線形リスト

末尾へのノードの挿入
H
・
N
A
・
N
B
・
P
・
N
C
・
N
D
・
N
G
・
N
E
・
ポインタによる線形リスト

先頭ノードの削除

先頭ノードを、先頭の後続ノードへ
1.
2.
3.
現先頭ノードの後続ノードへのポインタを保存
先頭ノードを削除
保存してあったポインタを先頭ノードとして置き換え
ポインタによる線形リスト

先頭ノードの削除
H
・
N
A
・
N
B
・
P
・
N
C
・
N
D
・
N
E
・
ポインタによる線形リスト

末尾ノードの削除

末尾ノードの先行ノードに、後続ノードがない状
態に
1.
2.
3.
4.
ノードが1つだけなら先頭ノードの削除処理
末尾から2番目のノードを探索
末尾ノードを削除
末尾から2番目の後続ノード（next）をなし（NULL）に
更新
ポインタによる線形リスト

末尾ノードの削除
H
・
N
A
・
Pre
・
N
B
・
Ptr
・
N
C
・
N
D
・
N
E
・
ポインタによる線形リスト

着目ノードの削除

着目ノードの先行ノードの後続ノードを、着目ノー
ドの後続ノードに付け替え
1.
2.
3.
4.
ノードが1つだけなら先頭ノードの削除処理
着目ノードの先行ノードを探索
探索したノードの後続ノードを着目ノードの後続ノード
に更新
着目ノードを削除
ポインタによる線形リスト

着目ノードの削除
H
・
N
A
・
N
B
・
Ptr
・
N
C
・
N
D
・
N
E
・
ポインタによる線形リスト

全ノードの削除
 線形リストが空になるまで先頭要素の削除の繰
り返し

全ノードの表示
 先頭ノードから順に内容表示
 後続ノードがなくなったら終了
カーソルによる線形リスト

実現方法
 配列を利用し、後続ノードが格納されている配列
内の位置（添え字）を記憶：カーソル
カーソルを追うことで後続ノードをたどる
 カーソルが-1になったら後続ノードなし

 要素の追加や削除に伴う配列要素の移動不要

カーソルを付け替えることで追加や削除を実現
カーソルによる線形リスト

カーソルによる線形リストの実現
N
A
・
N
B
・
N
C
・
D
・
N
0
1
2
3
4
E
-1
A
4
C
3
D
0
B
2
5
N
6
E
・
7
カーソルによる線形リスト

配列内の空き要素
 削除に伴う問題点

要素の削除があると、その部分の配列要素は未使用

頻繁に削除が行われると配列がスカスカに
カーソルによる線形リスト

削除に伴う問題点
N
A
・
N
B
・
N
C
・
D
・
N
0
1
2
3
4
E
-1
A
4
C
3
D
0
B
2
3
5
N
6
E
・
7
カーソルによる線形リスト

フリーリスト
 削除に伴い配列がスカスカになるのを防止
 削除が行われた際、削除された要素の添え字を
線形リストで管理：フリーリスト
フリーリスト用の先頭ノードを用意（deleted）
 各ノードに、フリーリスト上の後続ノードも持たせる
（Dnext）

 挿入の際、フリーリストから使用
カーソルによる線形リスト

フリーリスト
データの挿入
データの削除
0
n
Dn
G
1
B
6
5
h
2
Dh
3
1
7
2
3
4
A
0
G
-1
1
E
-1
3
5
-1
6
7
C
7
4
D
4
1
循環・重連結リスト

循環リスト
 線形リストの末尾ノードが先頭ノードを指すリスト

重連結（双方向）リスト
 後続ノードへのポインタだけでなく、先行ノードへ
のポインタも備えたリスト

循環・重連結リスト
 循環リストと重連結リストの両方を併せ持つリスト
循環・重連結リスト

循環・重連結リストの実現
 実現方法

本来のデータと、先行ノード、後続ノードを示す2つのポ
インタを備えたノードを用意
 リストの初期化

データがなくてもダミーとして1つノードを作成

ノードの追加や削除を円滑に行うため
循環・重連結リスト

循環・重連結リストの実現
 ノードの探索

線形探索でデータを探索
ダミーノードの次のノードから目的値を持つノードを探索
 探索すべき値と等しい要素を持つノードを見つけたら探索成功
 探索すべき値が見つからずダミーノードまで戻ったら探索失敗

循環・重連結リスト

循環・重連結リストの実現
ノードの探索
・
G
B
成功
を探索：失敗
P
・
（ダミー）
N
・
・
A
・
P
H
N
N
・
B
・
P
N
・
C
・
P
N
・
D
・
P
循環・重連結リスト

循環・重連結リストの実現
 ノードの挿入

新規ノードと、挿入すべき前後のノードでポインタの付け
替え（4つ）
 先頭へのノードの挿入

ダミーノードの直後へノードを挿入
 末尾へのノードの挿入

ダミーノードの直前へノードを挿入
循環・重連結リスト

循環・重連結リストの実現
ノードの挿入
・
G
・
N
N
・
A
・
P
N
・
B
・
P
N
P
・
C
・
P
循環・重連結リスト

循環・重連結リストの実現
 ノードの削除

削除するノードの記憶域を開放し、前後のポインタを適
宜付け替え
 先頭ノードの削除

ダミーノードの直後のノードを削除
 末尾ノードの削除

ダミーノードの直前のノードを削除
循環・重連結リスト

循環・重連結リストの実現
ノードの削除
N
・
A
・
P
N
・
B
・
P
N
・
C
・
P

アルゴリズムと データ構造

アルゴリズムと データ構造

アルゴリズムと データ構造