第５回連結リストを使ったプログラム

(1)

第５回　連結リストを使ったプログラム

～配列以外のデータ構造に挑戦！～

(2)

学習目標



Java における参照の仕組みを説明できる

 基本データ型と参照型の違いを説明できる



連結リストを使ったプログラムが書ける

 連結リストを使う利点を説明できる

 連結リストの概念を説明できる

 連結リストへの追加、削除、検索のプログラムを

Java

を使って書ける

(3)

5.1 参照の仕組み



参照の仕組み練習問題



5.1.1 Java における参照の仕組み



① メモリと番地



② 参照とメモリの仕組み



③ 基本データ型と参照型

(4)

参照の仕組み練習問題



テキスト (5.1) の



リスト「参照練習問題 1 」



リスト「参照練習問題 2 」

がどのような出力をするか考えなさい

。

(5)

参照練習問題 1

public static void main(String args[]){

int x;

int y;

x = 3;

y = x;

y = 15;

System.out.println(x);

System.out.println(y);

}

(6)

参照練習問題 2

public static void main(String args[]){

TestClass x;

TestClass y;

x = new TestClass();

x.id = 3;

y = x;

y.id = 15;

System.out.println(x.id);

System.out.println(y.id);

}

class TestClass {

(7)

答え



参照練習問題 1 3

15



参照練習問題 2 15

15

(8)

① メモリと番地



プログラムは、変数をメモリに格納します。



メモリには、

すべての場所に

番地がついています。



この番地のことを参照といったりします。

番地内容

100 101 102 103

メモリ

(9)

② 参照とメモリの仕組み (1)

int x;

int y;

x = 3;

y = x;

y = 15;

System.out.println(x);

System.out.println(y);

番地内容

101 102 103 104

メモリ

100

番地

(100)

100 x 100 0(

初期値

)

番地

(101)

100 101 100

x 100 0(

初期値

)

0(

初期値

) y

内容番地

(101)

x 0(

初期値

)

0(

初期値

) y

x 3

0(

初期値

) y

内容

x

0(

初期値

)

y 101

100 x 100 0(

初期値

)

101 100

x 100 0(

初期値

)

0(

初期値

)

y 101

100 x 100 0(

初期値

)

101 100

x 100 3

y 101 101 101 3

x 3

0(

初期値

) y 101 101

x y 3

x 3

y 15

x 3

y 3

内容

x 3

0(

初期値

) y

内容

x

y 15

(10)

② 参照とメモリの仕組み (2)

TestClass x;

TestClass y;

x = new TestClass();

x.id = 3;

y = x;

y.id = 15;

System.out.println(x.id);

System.out.println(y.id);

番地内容

100

101 1000

メモリ

オブジェクト用のメモリ番地

(100)

x 0(

初期値

null )

x y null

番地

(101)

null

番地内容

100 101

1000

0(

初期値

) x

y null

null

0(

初期値

) TestClass x;

TestClass y;

x = new TestClass();

x.id = 3;

y = x;

y.id = 15;

System.out.println(x.id);

System.out.println(y.id);

番地内容

100

101 1000

0(

初期値

) x

y null

1000

0(

初期値

)

オブジェクト用のメモリ

メモリ

3 null

0(

初期値

) null

1000

3

内容

TestClass x;

TestClass y;

x = new TestClass();

x.id = 3;

y = x;

y.id = 15;

System.out.println(x.id);

System.out.println(y.id);

番地内容

100

101 1000

メモリ

1000

3 x 0(

初期値

null )

x

y 1000

1000

33 x 0(

初期値

null )

x

y 1000

1000

15

(11)

③ 基本データ型と参照型



基本データ型

→値が直接入るタイプ



参照型

→オブジェクト用のメモリに生成され

、参照が入るタイプ



どうやって見分けたらいいでしょうか？

※ これは

Java

だけの話です。

(12)

基本データ型を覚えよ



Java の基本データ型は 8 種類しかない

。



整数が入るもの



int



long



short



真偽値が入るもの



boolean



小数が入るもの



float



double



文字が入るもの



byte(1

バイト文字

)



char(2

バイト文字

)

(13)

その他はすべて参照型



new 演算子でインスタンス化する必要があるもの



実は配列も

参照型です。 ₁₀₀₀

^番地 ^内容

1001 0

[0] 0

1002 0

1003 0

1004 0

[1]

[2]

[3]

[4]

int[] idArray = new int[5];

番地内容

101 1000(

番地

)

メモリ

idArray

(14)

まとめ Java における参照の仕組み



変数を宣言すると、メモリに領域が確保される

。



=( 代入 ) 記号での代入文は、値のコピーが行われる。



ただし、オブジェクトの場合は、値に参照が入っているため、参照のコピーが行われる。

 このとき、インスタンスのコピーは行われない。



インスタンスを生成するとオブジェクト用のメ

モリが確保される。

(15)

5.2 連結リスト



5.2.1 配列にこだわる必要はない



5.2.2 連結リストとは？

(16)

5.2.1 配列にこだわる必要はない



配列は使いやすいのですが、問題点もあります。



考えてみましょう

(17)

配列は大きさが決まっている



配列は、作るときに大きさを決める必要があります。



その大きさ以上要素を入れることができません。



また、要素が入っていないと、メモリの無

駄になります。

(18)

間に割り込んで

挿入するのが大変



テキストエディタ（メモ帳 , mule… _）

を作ることを考えましょう。



機能：



文字を挿入する



文字を削除する

(19)

配列で作ったとすると、、、

番地内容

1000

1001

‘ は’

‘ お’

[0]

1002

‘ よ’

1003

‘ う’

1004

‘ ざ’

[1]

[2]

[3]

[4]

1005

‘ い’

[5]

1006

‘ ま’

[6]



一文字一文字を

配列にいれて

管理します。

(20)

挿入はどうするか？

番地内容

1000

1001

‘ は’

‘ お’

[0]

1002

‘ よ’

1003

‘ う’

1004

‘ ざ’

[1]

[2]

[3]

[4]

1005

‘ い’

[5]

‘ ご’を挿入したい

‘ ざ’

‘ ご’

(21)

配列での実装の問題点



もし、これが、１万文字のレポートの最初の所だったらどうなるか？



一文字挿入するごとに、１万回の移動が必要

 遅すぎてだれも使ってくれません

(22)

5.2.2 連結リストとは？

102

‘ お’

104

‘ は’

106

‘ よ’

108

‘ ご’

null

‘ ざ’

100

番地

102

番地

104

番地

106

番地

108

番地

(23)

実際のメモリ上では

番地内容

100 101 102

‘ お’

102

‘ は’

103 104

104

‘ よ’

105 106

106

‘ う’

(24)

① 連結リストの特徴

(1) 連結リストへの挿入



移動しなくて済む

102

‘ お’

104

‘ は’

106

‘ よ’

108

‘ ご’

null

‘ ざ’

100

番地

102

番地

104

番地

106

番地

108

番地

110

番地

110

(25)

106

‘ よ’

104

番地

(2) 連結リストからの削除



もっと簡単

102

‘ お’

104

‘ は’

108

‘ ご’

null

‘ ざ’

100

番地

102

番地

106

番地

108

番地

106

‘ よ’

104

番地

106

(26)

③ 連結リストの利点･欠点



考えてみましょう

(27)

③ 連結リストの利点・欠点



利点

 メモリをあらかじめ確保しておく必要が無い

 必要十分な量だけその都度確保できる

 メモリの許す限り大きくできる

 挿入、削除が非常に早い



欠点

 番地を保存しておくためのメモリ領域を取る

 検索が遅い

 最初から順繰りに辿っていかないといけない

 配列ならば、バイナリサーチ（第 8 回）などの早い検索方法がある

(28)

5.3 連結リストを実装する



5.3.1 連結リストの実装



① 連結リストの実装例



② クラス設計



5.3.2 連結リストのアルゴリズム



① 追加アルゴリズム



② 検索アルゴリズム



③ 削除アルゴリズム

(29)

① 連結リストの実装例

 前回作ったプログラムを連結リストで作り直す



ItemType

クラスは変更なし

 （前回の配列バージョンも残しておいてください）

 例題

5-1-(

複数のクラスで一つのプログラムです

)



「 Example5_1.java 」



「 ItemType.java 」



「 ItemTypeList.java 」



「 LinkObject.java 」



「 LinkTerminal.java 」

(30)

② クラス設計



前回同様、 Example クラスと

ItemTypeList クラスを分離します

Example{

main();

}

ItemTypeList{

add();

delete();

search();

display();

(31)

② クラス設計

(1)LinkObject クラス

// 連結リスト用オブジェクト

class LinkObject {

ItemType data; //

商品種類

LinkObject next; //

次の要素への参照 }



連結リスト用オブジェクト LinkObject を作る

？？自分で自分を持ってるの？？

例題5-1

(Example5_1.java)

(32)

(1)LinkObject クラス



実は参照なので、図のようになります

。

// 連結リスト用オブジェクト

class LinkObject {

ItemType data;

LinkObject next;

}

102 番地コーラ

22(id)

null ソーダ

23(id)

※ ※

100 番地 102 番地

(33)

(2)LinkTerminal クラス

追加や検索をするために、

Example

クラスは、

常にリストの最初の番地

(first)

と最後の番地

(last)

102 番地 100 番地

コーラ 2221

104 番地 102 番地

ソーダ 2222

106 番地 104 番地

オレンジ 2223

108 番地 106 番地

紅茶 2224

null 108 番地

緑茶 2225

last first

(34)

(2)LinkTerminal クラス



今回は引数として、配列ではなく、最初の番地 (first) と最後の番地 (last) を渡す必要があります

Example{

main();

}

ItemTypeList{

add();

delete();

search();

display();

•

最初の番地

•

最後の番地

(35)

(2)LinkTerminal クラス



引数用オブジェクト LinkTerminal を作り、それを渡すことにします

// 連結リストの始点と終点をもつクラス public class LinkTerminal {

LinkObject first;// 始点 LinkObject last;// 終点

} Example

{

main();

ItemTypeList{

add();

delete();

search();

display();

LinkTerminal

オブジェクト

(36)

5.3.2 連結リストのアルゴリズム



① 追加アルゴリズム



② 検索アルゴリズム



③ 削除アルゴリズム

(37)

追加 (1) 一般的な追加

public void add(LinkTerminal linkTerminal,ItemType addItemType){

//追加する連結オブジェクトを生成する

LinkObject addLink = new LinkObject();

addLink.data = addItemType;

linkTerminal.last.next = addLink;

linkTerminal.last = addLink;

} }

first last

102 番地 100 番地

コーラ 2221

102 番地

ソーダ 2222

null 108 番地

null

緑茶 2223

null 108 番地

last

(38)

追加 (2) 一番最初の追加

public void insert(LinkTerminal linkTerminal , ItemType

addItemType ){

LinkObject addLink = new LinkObject();

addLink.data = addItem;

if(linkTerminal.first == null){

linkTerminal. first = addLink;

linkTerminal. last = addLink;

}else{

linkTerminal.last.next = addLink;

linkTerminal.last = addLink;

null

^null

102 番地

null

緑茶 2223

(39)

2222

currentcurrent searchId

検索 (1)

商品種類が見つかる場合

public ItemType search(int searchId,

LinkTerminal linkTerminal){

LinkObject current=linkTerminal.first;

while(current!=null){

if(current.data.id==searchId){

System.out.println(“ 見つかりました” ) ;

return current.data;

}

current=current.next;

} System.out.println(“ 見つかりませんでした” );

102

^番

地

2221

紅茶

104

^番

地

2222

緑茶

null 2223

水

100

番地

102

番地

104

番地

first last

(40)

searchId 3333

検索 (2)

商品種類が見つからない場合

public ItemType search(int searchId,

LinkTerminal linkTerminal){

LinkObject current= linkTerminal.first;

if(current.data.id==searchId){

System.out.println(“ 見つかりました” ) ; return current.data;

}

System.out.println(“ 見つかりませんでした” );

return null;

102

番地

2221

紅茶

100

番地

null 2221

緑茶

102

番地

null

(41)

削除 (1)

リストの中央で見つかる場合

public ItemType delete(int deleteId, LinkTerminal linkTerminal){

LinkObject current=linkTerminal.first;

LinkObject previous;

if(current.data.id==deleteId){

previous.next=current.next;

}

previous=current;

}

102 番地 100 番地

deleteId

紅茶 2221

104 番地 102 番地

緑茶 2222

null 104 番地

水 2223 2222

104 番地

×

null

(42)

削除 (2)

リストの最初で見つかる場合

LinkObject current=first;

if(currrent==first){

first=current.next;

} }}

102 番地 100 番地

deleteId

紅茶 2221

104 番地 102 番地

緑茶 2222

null 104 番地

水 2223 2221

null

(43)

削除 (3)

リストの最後で見つかる場合

LinkObject current= linkTerminal.first;

if(corrent== linkTerminal.last){

last=previous;

last.next=null;

}

previous=current;

}

102 番地 100 番地

deleteId

紅茶 2221

104 番地 102 番地

緑茶 2222

null 104 番地

水 2223 2223

null

×

null

(44)

ガベージ･コレクション



削除するときに無駄なメモリが残ってしまうきがするのですが？

103

‘ よ’

102

番地

101

‘ お’

102

‘ は’

104

‘ ご’

null

‘ ざ’

100

番地

101

番地

103

番地

104

番地

103

‘ よ’

102

番地

Java

では、いらないメモリを常に見張っている「ガベージコレクタ」

第５回 連結リストを使った プログラム