メモリの「物理的」特性を考慮して、 「論理的」に扱う方法

アルゴリズムとデータ構造 補足資料 11-2

「線形リスト」

横浜国立大学 理工学部 数物・電子情報系学科 富井尚志

メモリの「物理的」特性を考慮して、

「論理的」に扱う方法

•

Random Access Memory (RAM)

–

– CPU

• それなりに遅い（あまりデータを動かしたくない）

•

–

• OSに、メモリ領域を管理させる。（使うときに「割当て」、終わったら

「解放」）

• 「ポインタ」を使って、「指し示している」とみなす

• メモリ内では、データは極力移動しない。「割当て」「解放」を、アド レスを指定して行う。

–

アドレス（ 32bit ） , 4ア ドレス飛び

中身（ 1記憶単位 =8bitを 4領域まとめて32bitで表 示）

… …

0x 40ea 0800 22

0x 40ea 0804 0x 40ea 0810

0x 40ea 0808 0x 41b7 41b0

0x 40ea 080c 0x 4c6f a750

0x 40ea 0810 23

0x 40ea 0814 0x 0000 0000

0x 40ea 0818 0x 0000 0000

0x 40ea 081c 0x 40ea 082c

0x 40ea 0820 0x 0100 0001

0x 40ea 0824 0x 1011 0111

0x 40ea 0828 0x 0100 0001

0x 40ea 082c 21

0x 40ea 0830 0x 40ea 0800

0x 40ea 0834 0x 0110 1111

0x 40ea 0838 0x 1010 0111

0x 40ea 083c 0x 0101 0000

… …

p

key next key next

key next

どのような状況か？

変数

malloc で 確保された領域

※ malloc は、そのときそのときで

適当な場所を割り当てる。

メモリの

物理的

アドレス（ 32bit ） , 4ア ドレス飛び

中身（ 1記憶単位 =8bitを 4領域まとめて32bitで表 示）

… …

0x 40ea 0800 22

0x 40ea 0804 0x 40ea 0810

0x 40ea 0808 0x 41b7 41b0

0x 40ea 080c 0x 4c6f a750

0x 40ea 0810 23

0x 40ea 0814 0x 0000 0000

0x 40ea 0818 0x 0000 0000

0x 40ea 081c 0x 40ea 082c

0x 40ea 0820 0x 0100 0001

0x 40ea 0824 0x 1011 0111

0x 40ea 0828 0x 0100 0001

0x 40ea 082c 21

0x 40ea 0830 0x 40ea 0800

0x 40ea 0834 0x 0110 1111

0x 40ea 0838 0x 1010 0111

0x 40ea 083c 0x 0101 0000

… …

p

key next key next

key next

どのような状況か？

変数

malloc で 確保された領域

メモリの

物理的

アドレス（ 32bit ） , 4ア ドレス飛び

中身（ 1記憶単位 =8bitを 4領域まとめて32bitで表 示）

… …

0x 40ea 0800 22

0x 40ea 0804 0x 40ea 0810

0x 40ea 0808 0x 41b7 41b0

0x 40ea 080c 0x 4c6f a750

0x 40ea 0810 23

0x 40ea 0814 0x 0000 0000

0x 40ea 0818 0x 0000 0000

0x 40ea 081c 0x 40ea 082c

0x 40ea 0820 0x 0100 0001

0x 40ea 0824 0x 1011 0111

0x 40ea 0828 0x 0100 0001

0x 40ea 082c 21

0x 40ea 0830 0x 40ea 0800

0x 40ea 0834 0x 0110 1111

0x 40ea 0838 0x 1010 0111

0x 40ea 083c 0x 0101 0000

… …

p

key next key next

key next

どのような状況か？

変数

malloc で 確保された領域

メモリの

物理的

アドレス（ 32bit ） , 4ア ドレス飛び

中身（ 1記憶単位 =8bitを 4領域まとめて32bitで表 示）

… …

0x 40ea 0800 22

0x 40ea 0804 0x 40ea 0810

0x 40ea 0808 0x 41b7 41b0

0x 40ea 080c 0x 4c6f a750

0x 40ea 0810 23

0x 40ea 0814 0x 0000 0000

0x 40ea 0818 0x 0000 0000

0x 40ea 081c 0x 40ea 082c

0x 40ea 0820 0x 0100 0001

0x 40ea 0824 0x 1011 0111

0x 40ea 0828 0x 0100 0001

0x 40ea 082c 21

0x 40ea 0830 0x 40ea 0800

0x 40ea 0834 0x 0110 1111

0x 40ea 0838 0x 1010 0111

0x 40ea 083c 0x 0101 0000

… …

p

key next key next

key next

どのような状況か？

変数

malloc で 確保された領域

メモリの

物理的

p

key next key next

NULL

key next

どのような状況か？

変数

malloc で 確保された領域 21

23 22

データ構造の

論理的

論理的には「指し示している」ので、見やすくするために図示を工夫。

物理的にメモリ内で「データが移動」しているわけではない。

key next key next

NULL

key next

どのような状況か？

変数

malloc で 確保された領域 21

23 22

p データ構造の

論理的

論理的には「指し示している」ので、見やすくするために図示を工夫。

物理的にメモリ内で「データが移動」しているわけではない。

key next key

next どのような状況か？

21 22 p

変数 malloc で 確保された領域

NULL

key next

23 データ構造の

論理的

key next

どのような状況か？

21 p

変数 malloc で 確保された領域

NULL

key next

23

key next

22

データ構造の

論理的

どのような状況か？

p

変数 malloc で 確保された領域

NULL

key next

23

key next

22

key next

21

データ構造の

論理的

p ^key

next

key

next NULL

key next

変数 malloc で 確保された領域

21 22 23

どのような状況か？

線形リスト

データ構造の

論理的

アドレス（ 32bit ） , 4ア ドレス飛び

中身（ 1記憶単位 =8bitを 4領域まとめて32bitで表 示）

… …

0x 40ea 0800 22

0x 40ea 0804 0x 40ea 0810

0x 40ea 0808 0x 41b7 41b0

0x 40ea 080c 0x 4c6f a750

0x 40ea 0810 23

0x 40ea 0814 0x 0000 0000

0x 40ea 0818 0x 0000 0000

0x 40ea 081c 0x 40ea 082c

0x 40ea 0820 0x 0100 0001

0x 40ea 0824 0x 1011 0111

0x 40ea 0828 0x 0100 0001

0x 40ea 082c 21

0x 40ea 0830 0x 40ea 0800

0x 40ea 0834 0x 0110 1111

0x 40ea 0838 0x 1010 0111

0x 40ea 083c 0x 0101 0000

… …

p

key next key next

key next

key next

key next

NULL

key next

21

23 22

p

線形リスト

←

アドレス（ 32bit ） , 4ア ドレス飛び

中身（ 1記憶単位 =8bitを 4領域まとめて32bitで表 示）

… …

0x 40ea 0800 22

0x 40ea 0804 0x 40ea 0810

0x 40ea 0808 0x 41b7 41b0

0x 40ea 080c 0x 4c6f a750

0x 40ea 0810 23

0x 40ea 0814 0x 0000 0000

0x 40ea 0818 0x 0000 0000

0x 40ea 081c 0x 40ea 082c

0x 40ea 0820 0x 0100 0001

0x 40ea 0824 0x 1011 0111

0x 40ea 0828 0x 0100 0001

0x 40ea 082c 21

0x 40ea 0830 0x 40ea 0800

0x 40ea 0834 0x 0110 1111

0x 40ea 0838 0x 1010 0111

0x 40ea 083c 0x 0101 0000

… …

p

key next key next

key next

ここで、新たに要素を追加したい

（ただし、変数 newp をつかってよい）

key next

key next

NULL

key next

21

23 22

p

newp

アドレス（ 32bit ） , 4ア ドレス飛び

中身（ 1記憶単位 =8bitを 4領域まとめて32bitで表 示）

… …

0x 40ea 0800 22

0x 40ea 0804 0x 40ea 0810

0x 40ea 0808 0x 41b7 41b0

0x 40ea 080c 0x 4c6f a750

0x 40ea 0810 23

0x 40ea 0814 0x 0000 0000

0x 40ea 0818 0x 0000 0000

0x 40ea 081c 0x 40ea 082c

0x 40ea 0820 0x 0100 0001

0x 40ea 0824 0x 1011 0111

0x 40ea 0828 0x 0100 0001

0x 40ea 082c 21

0x 40ea 0830 0x 40ea 0800

0x 40ea 0834 0x 0110 1111

0x 40ea 0838 0x 1010 0111

0x 40ea 083c 0x 0101 0000

… …

p

key next key next

key next

key next

key next

NULL

key next

21

23 22

p

newp

newp = (struct list *)malloc(sizeof(struct list));

① newp 用にメモリ確保

ここで、新たに要素を追加したい

（ただし、変数 newp をつかってよい）

アドレス（ 32bit ） , 4ア ドレス飛び

中身（ 1記憶単位 =8bitを 4領域まとめて32bitで表 示）

… …

0x 40ea 0800 22

0x 40ea 0804 0x 40ea 0810

0x 40ea 0808 0x 41b7 41b0

0x 40ea 080c 0x 4c6f a750

0x 40ea 0810 23

0x 40ea 0814 0x 0000 0000

0x 40ea 0818 0x 0000 0000

0x 40ea 081c 0x 40ea 082c

0x 40ea 0820 0x 0100 0001

0x 40ea 0824 0x 40ea 0834

0x 40ea 0828 0x 0100 0001

0x 40ea 082c 21

0x 40ea 0830 0x 40ea 0800

0x 40ea 0834 0x 0110 1111

0x 40ea 0838 0x 1010 0111

0x 40ea 083c 0x 0101 0000

… …

p

key next key next

key next

key next

key next

NULL

key next

21

23 22

p

newp

newp = (struct list *)malloc(sizeof(struct list));

① newp 用にメモリ確保 ここで、新たに要素を追加したい

（ただし、変数 newp をつかってよい）

key next

key next

newp

アドレス（ 32bit ） , 4ア ドレス飛び

中身（ 1記憶単位 =8bitを 4領域まとめて32bitで表 示）

… …

0x 40ea 0800 22

0x 40ea 0804 0x 40ea 0810

0x 40ea 0808 0x 41b7 41b0

0x 40ea 080c 0x 4c6f a750

0x 40ea 0810 23

0x 40ea 0814 0x 0000 0000

0x 40ea 0818 0x 0000 0000

0x 40ea 081c 0x 40ea 082c

0x 40ea 0820 0x 0100 0001

0x 40ea 0824 0x 40ea 0834

0x 40ea 0828 0x 0100 0001

0x 40ea 082c 21

0x 40ea 0830 0x 40ea 0800

0x 40ea 0834 30

0x 40ea 0838 0x 1010 0111

0x 40ea 083c 0x 0101 0000

… …

p

key next key next

key next

key next

key next

NULL

key next

21

23 22

p

newp

newp ->key = 30;

② 確保した領域に値を代入 ここで、新たに要素を追加したい

（ただし、変数 newp をつかってよい）

key next

key next

30 newp

アドレス（ 32bit ） , 4ア ドレス飛び

中身（ 1記憶単位 =8bitを 4領域まとめて32bitで表 示）

… …

0x 40ea 0800 22

0x 40ea 0804 0x 40ea 0810

0x 40ea 0808 0x 41b7 41b0

0x 40ea 080c 0x 4c6f a750

0x 40ea 0810 23

0x 40ea 0814 0x 0000 0000

0x 40ea 0818 0x 0000 0000

0x 40ea 081c 0x 40ea 082c

0x 40ea 0820 0x 0100 0001

0x 40ea 0824 0x 40ea 0834

0x 40ea 0828 0x 0100 0001

0x 40ea 082c 21

0x 40ea 0830 0x 40ea 0800

0x 40ea 0834 30

0x 40ea 0838 0x 40ea 082c

0x 40ea 083c 0x 0101 0000

… …

p

key next key next

key next

key next

key next

NULL

key next

21

23 22

p

newp

newp ->next = p;

③ 確保した領域からリストに接続 ここで、新たに要素を追加したい

（ただし、変数 newp をつかってよい）

key next

key next

30 newp

値（アドレス：ポインタ）

をコピー

アドレス（ 32bit ） , 4ア ドレス飛び

中身（ 1記憶単位 =8bitを 4領域まとめて32bitで表 示）

… …

0x 40ea 0800 22

0x 40ea 0804 0x 40ea 0810

0x 40ea 0808 0x 41b7 41b0

0x 40ea 080c 0x 4c6f a750

0x 40ea 0810 23

0x 40ea 0814 0x 0000 0000

0x 40ea 0818 0x 0000 0000

0x 40ea 081c 0x 40ea 082c

0x 40ea 0820 0x 0100 0001

0x 40ea 0824 0x 40ea 0834

0x 40ea 0828 0x 0100 0001

0x 40ea 082c 21

0x 40ea 0830 0x 40ea 0800

0x 40ea 0834 30

0x 40ea 0838 0x 40ea 082c

0x 40ea 083c 0x 0101 0000

… …

p

key next key next

key next

key next

key next

NULL

key next

21

23 22

p

newp

newp ->next = p;

③ 確保した領域からリストに接続 ここで、新たに要素を追加したい

（ただし、変数 newp をつかってよい）

key next

key next

30 newp

値（アドレス：ポインタ）

をコピー

ここがポイント！ →

アドレス（ 32bit ） , 4ア ドレス飛び

中身（ 1記憶単位 =8bitを 4領域まとめて32bitで表 示）

… …

0x 40ea 0800 22

0x 40ea 0804 0x 40ea 0810

0x 40ea 0808 0x 41b7 41b0

0x 40ea 080c 0x 4c6f a750

0x 40ea 0810 23

0x 40ea 0814 0x 0000 0000

0x 40ea 0818 0x 0000 0000

0x 40ea 081c 0x 40ea 0834

0x 40ea 0820 0x 0100 0001

0x 40ea 0824 0x 40ea 0834

0x 40ea 0828 0x 0100 0001

0x 40ea 082c 21

0x 40ea 0830 0x 40ea 0800

0x 40ea 0834 30

0x 40ea 0838 0x 40ea 082c

0x 40ea 083c 0x 0101 0000

… …

p

key next key next

key next

key next

key next

NULL

key next

21

23 22

p

newp

p = newp;

④ リストの先頭を改める ここで、新たに要素を追加したい

（ただし、変数 newp をつかってよい）

key next

key next

30 newp

値（アドレス：ポイン タ）をコピー

アドレス（ 32bit ） , 4ア ドレス飛び

中身（ 1記憶単位 =8bitを 4領域まとめて32bitで表 示）

… …

0x 40ea 0800 22

0x 40ea 0804 0x 40ea 0810

0x 40ea 0808 0x 41b7 41b0

0x 40ea 080c 0x 4c6f a750

0x 40ea 0810 23

0x 40ea 0814 0x 0000 0000

0x 40ea 0818 0x 0000 0000

0x 40ea 081c 0x 40ea 0834

0x 40ea 0820 0x 0100 0001

0x 40ea 0824 0x 40ea 0834

0x 40ea 0828 0x 0100 0001

0x 40ea 082c 21

0x 40ea 0830 0x 40ea 0800

0x 40ea 0834 30

0x 40ea 0838 0x 40ea 082c

0x 40ea 083c 0x 0101 0000

… …

p

key next key next

key next

key next

key next

NULL

key next

21

23 22

p

newp

p = newp;

④ リストの先頭を改める ここで、新たに要素を追加したい

（ただし、変数 newp をつかってよい）

key next

key next

30 newp

値（アドレス：ポイン タ）をコピー

ここがポイント！→

アドレス（ 32bit ） , 4ア ドレス飛び

中身（ 1記憶単位 =8bitを 4領域まとめて32bitで表 示）

… …

0x 40ea 0800 22

0x 40ea 0804 0x 40ea 0810

0x 40ea 0808 0x 41b7 41b0

0x 40ea 080c 0x 4c6f a750

0x 40ea 0810 23

0x 40ea 0814 0x 0000 0000

0x 40ea 0818 0x 0000 0000

0x 40ea 081c 0x 40ea 0834

0x 40ea 0820 0x 0100 0001

0x 40ea 0824 0x 40ea 0834

0x 40ea 0828 0x 0100 0001

0x 40ea 082c 21

0x 40ea 0830 0x 40ea 0800

0x 40ea 0834 30

0x 40ea 0838 0x 40ea 082c

0x 40ea 083c 0x 0101 0000

… …

p

key next key next

key next

key next

key next

NULL

key next

21

23 22

p

newp

完了！

ここで、新たに要素を追加したい

（ただし、変数 newp をつかってよい）

key next

key next

30 newp

アドレス（ 32bit ） , 4ア ドレス飛び

中身（ 1記憶単位 =8bitを 4領域まとめて32bitで表 示）

… …

0x 40ea 0800 22

0x 40ea 0804 0x 40ea 0810

0x 40ea 0808 0x 41b7 41b0

0x 40ea 080c 0x 4c6f a750

0x 40ea 0810 23

0x 40ea 0814 0x 0000 0000

0x 40ea 0818 0x 0000 0000

0x 40ea 081c 0x 40ea 0834

0x 40ea 0820 0x 0100 0001

0x 40ea 0824 0x 40ea 0834

0x 40ea 0828 0x 0100 0001

0x 40ea 082c 21

0x 40ea 0830 0x 40ea 0800

0x 40ea 0834 30

0x 40ea 0838 0x 40ea 082c

0x 40ea 083c 0x 0101 0000

… …

p

key next key next

key next

key next

key next

NULL

key next

21

23 22

p

newp

完了！

ここで、新たに要素を追加したい

key next

key next

30

p ^key

next

key

next NULL

key next

21 22 23

ここで、新たに要素を追加したい

（ただし、変数 newp をつかってよい）

図で、もう 1 回。

p ^key

next

key

next NULL

key next

21 22 23

ここで、新たに要素を追加したい

（ただし、変数 newp をつかってよい）

図で、もう 1 回。

newp = (struct list *)malloc(sizeof(struct list));

① newp 用にメモリ確保

key next

newp

p ^key

next

key

next NULL

key next

21 22 23

ここで、新たに要素を追加したい

（ただし、変数 newp をつかってよい）

図で、もう 1 回。

key next

30 newp

newp ->key = 30;

② 確保した領域に値を代入

p ^key

next

key

next NULL

key next

21 22 23

ここで、新たに要素を追加したい

（ただし、変数 newp をつかってよい）

図で、もう 1 回。

key next

30 newp

newp ->next = p;

③ 確保した領域からリストに接続

値をコピー

p ^key

next

key

next NULL

key next

21 22 23

ここで、新たに要素を追加したい

（ただし、変数 newp をつかってよい）

図で、もう 1 回。

key next

30 newp

p = newp;

④ リストの先頭を改める

値をコピー

p ^key

next

key

next NULL

key next

21 22 23

ここで、新たに要素を追加したい

図で、もう 1 回。

key next

30

完了！

メモリの「物理的」特性を考慮して、

「論理的」に扱う方法

• 物理特性： Random Access Memory (RAM)

• 論理的に扱う：「割当て」「解放」「ポ インタで指し示す」

• 動的データ構造： プログラムが使うメモ リ領域を、必要に応じて増減させる。

– 配列「変数」は、そのスコープが有効な期間 中ずっと確保される。

– 動的「割当て」は、必要に応じて増減させる