1-1. 連結リスト
2
•順序のあるデータ
•要素の削除，挿入によりサイズが増減する
リストの性質
3
リストの組み立て，要素の挿入，要素の削除
4
リストの組み立て
要素の挿入
４を挿入
要素の削除
８を削除
リストの種類
処理 配列によるリス
ト
連結リスト
要素の末尾への追加 高速 高速
要素の末尾以外への追
加
低速 高速
要素の末尾からの削除 高速 高速
要素の末尾以外からの
追加
低速 高速
添え字による要素アク
セス
高速 低速
・「高速」，「低速」は，配列によるリスト，連結リストを
比べたとき，どちらが相対的に早いかの傾向を示すもの
・連結リストでの要素の追加，削除は，追加，削除すべき
レコードのアドレスが分かっているものとする 5
•配列によるリスト
あらかじめ，ある程度の長さの配列を作り，
その中にリストを格納するもの
•連結リスト
データを格納するためのメモリを挿入のたびに確
保．そして，削除のたびに解放．
6
連結リストとは
レコードを次の２つで構成
•要素を格納するセル
•リスト中の次のレコードを指すポインタを格納す
るセル
7
1-2. 「リスト」を実習できる
オンラインサイトの紹介
8
9
リストとは，順序の付いたデータの並び
「リスト」を実習できる
オンラインサイトの紹介
パソコン演習
④説明が出る．ESC キーを押して，説明を消す
⑤ 左下のメニューで「入れる」をクリックし，
「i = N (After tail), specify v =」を選ぶ
11
パソコン演習
⑥ 値が「80」のように表示されるので，確認した
ら「行く」をクリック
⑦末尾にデータが増えるので，確認する
12
1-3. 実習
13
実習の指示
•資料：１５～２４
•C Tutor に関する次のことを理解
しマスターする
•C Tutor の起動手順
•C Tutor の画面構成
•C Tutor は，オンラインのプログ
ラム開発環境であること
14
実習
①ウェブブラウザを起動する
②C Tutor を使いたいので，次の URL を開く
http://www.pythontutor.com/
※Internet Explorer でうまく動かない場合がある
→ うまく動かないときは Google Chrome を試してください
※途中で「Server Busy・・・」というメッセージが出るこ
とがある．
→ 混雑している．少し（数秒から数十秒）待つと自動で表示
が変わる（変わらない場合には，操作をもう一度行ってみ
る）
※日本語モードはない．英語で使う 15
③ 「C Tutor」をクリック
16
17
「C (gcc4.8, C11)」になっている
エディタ
実行のためのボタン
最初から main メソッドの
ひな形が入っている
実習の指示
•資料：１９～２４
•次のことを理解しマスターする
•連結リストの作成
•要素の末尾への追加
•要素の末尾からの削除
18
連結リストの作成
① 次のプログラムを使う
19
②「Visualize Execution」をクリック．
「Last」をクリック．
結果を確認する．
「Edit this code」をクリックして戻る
20
実行結果
21
レコード
レコード
レコード
③次のようにプログラムを書き換えて，実行し，
結果を確認しなさい．要素を末尾に挿入している
22
④次のようにプログラムを書き換えて，実行し，
結果を確認しなさい．要素を末尾に挿入している
23
課題
次のリストを作成しなさい
24
