双方向リストの構造と操作方法、C言語による実装
【学習内容の構成】
1. 双方向リストの構造：要素を格納するセルと、
前後のレコードを指す2つのポインタで構成
2. 連結リストとの違い：前方向への要素挿入が可
能
3. C Tutorによる実習：双方向リストの作成、末尾
要素の削除、末尾への要素挿入
• 前提：C言語の基礎、連結リストの理解
• 意義：柔軟なデータ操作が可能なデータ構造の習
得
2
双方向リストとは
レコードを次の２つで構成
• 要素を格納するセル
• リスト中の次のレコードを指すポインタを格納す
るセル
• リスト中の前のレコードを指すポインタを格納す
るセル
3
双方向リストと連結リストの違い
リスト内のあるレコードのアドレス A が分かってい
るとする．
• 連結リスト
A の次に要素を挿入することは簡単．
A の前に要素を挿入することはできない．
• 双方向リスト
A の次に要素を挿入することは簡単．
A の前に要素を挿入することも簡単．
4
1-2. 実習
5
実習の指示
• 資料：６～１２
• 次のことを理解しマスターする
• 双方向リスト
6
実習
① ウェブブラウザを起動する
② C Tutor を使いたいので，次の URL を開く
http://www.pythontutor.com/
※ Internet Explorer でうまく動かない場合がある
→ うまく動かないときは Google Chrome を試してください
※ 途中で「Server Busy・・・」というメッセージが出るこ
とがある．
→ 混雑している．少し（数秒から数十秒）待つと自動で表示
が変わる（変わらない場合には，操作をもう一度行ってみ
る）
※ 日本語モードはない．英語で使う
7
③ 「C Tutor」をクリック
8
9
「C (gcc4.8, C11)」になっている
エディタ
実行のためのボタン
最初から main メソッドの
ひな形が入っている
双方向リストの作成
④ 次のプログラムを使う
10
②「Visualize Execution」をクリック．
「Last」をクリック．
結果を確認する．
「Edit this code」をクリックして戻る
11
実行結果
12
レコード
レコード
レコード
実習
• いまのプログラムで
末尾の要素（値は16）を削除するプログラム
を書き加えなさい
・いまのプログラムで，
末尾に新しい要素（値は 24）を挿入する
プログラムを書き加えなさい
13
