狠狠撸

アルゴリズムとデータ構造
3 章?リスト
1

データ構造とは？
データ構造とは、データを保存しておく形式である。
データ構造の選択によって、計算の効率に影響を与える。
データ構造の例
配列、リスト、スタック、キュー、マップ、ツリー?など
2

リストとは?
データ構造の?種。順序付けられたデータ要素の集合。
特徴としては
?ノードがポインタで前後の位置関係を把握している
?要素の追加や削除、リストの連結、削除が容易にできる
?可変?である。
がある。
3

リストの表現
構造体やクラスを使って作成する。
ノードが前後のノードのポインタとデータを保持。

前前前
後後後
データデータデータ
4

ノードを先頭に追加
リストの先頭に追加したいノードのポインタを設定する
5
追加する
ノード

ノードを途中に追加
追加するノードの前のノード、後ろのノードにポインタを追加
6

ノードを末尾に追加
リストの末尾のノードに追加するノードのポインタを追加
7
追加する
ノード

ノードの削除
1. 除きたいノードの前後のノード同?をつなぐ
8
取り除きたいノード

ノードの削除
2. 切り離したノードを削除する
9

リストのサーチ
リストの中に格納されているデータをサーチする?法は
リニアサーチである。
リニアサーチ
先頭（または末尾）から順にたどっていって、?的のデー
タを持つ要素があるかどうかを調べていく?法
10

リストでのリニアサーチ
リストの中から9のデータを持つ要素を探す。
リストの前から順番に?ていく。
11
1 3 5 9 8 6 2

??組織化探索とは？
??組織化探索
サーチで?つかったデータを先頭に移動させる探索?法
リニアサーチでの探索処理が探索される
リストは??組織化探索に適したデータ構造である
データを先頭に移動させるための計算オーダがO(1)なので
??組織化探索が容易に実装できる
12

リストでの??組織化探索
“apple”の?字列が検索されたとき
13
banana peach orange apple grape
apple banana peach orange grape
先頭へ

リストと配列の違い
14
リスト
?動的にメモリを確保
?データを順番にたどる
?データの追加?削除が容易
?可変?である
配列
?最初にメモリを確保
?とびとびでデータに
アクセス可能
??さが決まっている

リストまとめ
?データ構造の?種
?動的にメモリを確保?解放するので可変?
?データを順番にたどってアクセスする
?ポインタを使って前後の位置関係を把握
?ノードの追加?削除が容易
???組織化探索に向いている

15

3章リスト