第5回連結リストの利用

第５回連結リストを使ったプロ
グラム
～配列以外のデータ構造に挑戦！～
学習目標

Javaにおける参照の仕組みを説明できる


基本データ型と参照型の違いを説明できる
連結リストを使ったプログラムが書ける



連結リストを使う利点を説明できる
連結リストの概念を説明できる
連結リストへの追加、削除、検索のプログラム
をJavaを使って書ける
5.1 参照の仕組み


参照の仕組み練習問題
5.1.1 Javaにおける参照の仕組み



①メモリと番地
②参照とメモリの仕組み
③基本データ型と参照型
参照の仕組み練習問題

テキスト(5.1)の


リスト「参照練習問題1」
リスト「参照練習問題2」
がどのような出力をするか考えなさい。
参照練習問題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);
}
参照練習問題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 {
int id;
}
答え


参照練習問題1
3
15
参照練習問題2
15
15
①メモリと番地

プログラムは、変数をメモリに格納します。


メモリには、
すべての場所に
番地がついています。
この番地のことを
参照といったり
します。
メモリ
番地
100
101
102
103
104
内容
②参照とメモリの仕組み(1)
メモリ
番地(100)
番地(101)
int x;
int y;
x = 3;
y = x;
y = 15;
System.out.println(x);
System.out.println(y);
x
y
番地
内容
100
3
0(初期値)
101
15
3
0(初期値)
102
103
104
②参照とメモリの仕組み(2)
メモリ
番地(100)
番地(101)
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);
番地
内容
x
100
1000
null
0(初期値)
y
101
1000
null
オブジェクト用のメモリ
1000
1001
15
3
0(初期値)
③基本データ型と参照型


基本データ型
※これはJavaだけの話です。
→値が直接入るタイプ
参照型
→オブジェクト用のメモリに生成され、参照
が入るタイプ

どうやって見分けたらいいでしょうか？
基本データ型を覚えよ

Javaの基本データ型は8種類しかない。

整数が入るもの




boolean
小数が入るもの
float
double
int
long
short
真偽値が入るもの




文字が入るもの
byte(1バイト文字)
char(2バイト文字)

その他はすべて参照型


new 演算子でインスタンス化する必要が
あるもの
オブジェクト用のメモリ
実は配列も
番地
内容
参照型です。
[0]
1000
0
int[] idArray = new int[5];
メモリ
idArray
[1]
1001
0
[2]
1002
0
番地
内容
[3]
1003
0
101
1000(番地)
[4]
1004
0
まとめ
Javaにおける参照の仕組み



変数を宣言すると、メモリに領域が確保される。
=(代入)記号での代入文は、値のコピーが行わ
れる。
ただし、オブジェクトの場合は、値に参照が入っ
ているため、参照のコピーが行われる。


このとき、インスタンスのコピーは行われない。
インスタンスを生成するとオブジェクト用のメモリ
が確保される。
5.2 連結リスト


5.2.1 配列にこだわる必要はない
5.2.2 連結リストとは？
5.2.1
配列にこだわる必要はない

配列は使いやすいのですが、問題点もあ
ります。

考えてみましょう
配列は大きさが決まっている

配列は、作るときに大きさを決める必要が
あります。


その大きさ以上要素を入れることができませ
ん。
また、要素が入っていないと、メモリの無駄に
なります。
間に割り込んで
挿入するのが大変


テキストエディタ（メモ帳,mule…）
を作ることを考えましょう。
機能：


文字を挿入する
文字を削除する
配列で作ったとすると、、、

一文字一文字を
配列にいれて
管理します。
番地
内容
[0]
1000
‘お’
[1]
1001
‘は’
[2]
1002
‘よ’
[3]
1003
‘う’
[4]
1004
‘ざ’
[5]
1005
‘い’
[6]
1006
‘ま’
[7]
1007
‘す’
挿入はどうするか？
‘ご’を挿入したい
番地
内容
[0]
1000
‘お’
[1]
1001
‘は’
[2]
1002
‘よ’
[3]
1003
‘う’
[4]
1004
‘ご’
‘ざ’
[5]
1005
‘い’
‘ざ’
[6]
1006
‘い’
‘ま’
[7]
1007
‘す’
‘ま’
配列での実装の問題点

もし、これが、１万文字のレポートの最初の
所だったらどうなるか？

一文字挿入するごとに、１万回の移動が必要

遅すぎてだれも使ってくれません
5.2.2 連結リストとは？
100番地
102番地
104番地
106番地
108番地
‘お’
‘は’
‘よ’
‘ご’
‘ざ’
102
104
106
108
null
実際のメモリ上では
番地
内容
100
‘お’
101
102
102
‘は’
103
104
104
‘よ’
105
106
106
‘う’
107
①連結リストの特徴
(1)連結リストへの挿入

移動しなくて済む
100番地
102番地
104番地
106番地
108番地
‘お’
‘は’
‘よ’
‘ご’
‘ざ’
102
104
106
110
108
null
110番地
‘う’
106
(2)連結リストからの削除

もっと簡単
100番地
102番地
104番地
106番地
108番地
‘お’
‘は’
‘よ’
‘ご’
‘ざ’
102
104
106
106
108
null
③連結リストの利点･欠点

考えてみましょう
③連結リストの利点・欠点

利点

メモリをあらかじめ確保しておく必要が無い




必要十分な量だけその都度確保できる
メモリの許す限り大きくできる
挿入、削除が非常に早い
欠点


番地を保存しておくためのメモリ領域を取る
検索が遅い


最初から順繰りに辿っていかないといけない
配列ならば、バイナリサーチ（第8回）などの早い検索方法が
ある
5.3 連結リストを実装する

5.3.1 連結リストの実装



①連結リストの実装例
②クラス設計
5.3.2 連結リストのアルゴリズム



①追加アルゴリズム
②検索アルゴリズム
③削除アルゴリズム
①連結リストの実装例

前回作ったプログラムを連結リストで作り直す



ItemTypeクラスは変更なし
（前回の配列バージョンも残しておいてください）
例題5-1-(複数のクラスで一つのプログラムです)





「Example5_1.java」
「ItemType.java」
「ItemTypeList.java」
「LinkObject.java」
「LinkTerminal.java」
②クラス設計

前回同様、ExampleクラスとItemTypeList
クラスを分離します
ItemTypeList{
add();
Example{
delete();
main();
search();
}
display();
}
②クラス設計
(1)LinkObjectクラス

連結リスト用オブジェクトLinkObjectを作る
例題5-1
(Example5_1.java)
//連結リスト用オブジェクト
class LinkObject {
ItemType data;
//商品種類
LinkObject next; //次の要素への参照
}
？？自分で自分を持ってるの？？
(1)LinkObjectクラス

実は参照なので、図のようになります。
//連結リスト用オブジェクト
class LinkObject {
ItemType data;
LinkObject next;
}
100番地
102番地
22(id)
23(id)
コーラ
ソーダ
102番地
null
※
※
※実際にはItemTypeも参照です。
(2)LinkTerminalクラス
100番地
102番地
104番地
106番地
108番地
2221
2222
2223
2224
2225
コーラ
ソーダ
オレンジ
紅茶
緑茶
102番地
104番地
106番地
108番地
null
first
last
追加や検索をするために、Exampleクラスは、
常にリストの最初の番地(first)と最後の番地(last)
だけは、知っておく必要があります。
(2)LinkTerminalクラス

今回は引数として、配列ではなく、最初の
番地(first)と最後の番地(last)を渡す必要
があります
ItemTypeList{
add();
Example{
main();
}
delete();
•最初の番地
•最後の番地
search();
display();
}
(2)LinkTerminalクラス

引数用オブジェクトLinkTerminalを作り、そ
れを渡すことにします
//連結リストの始点と終点をもつクラス
public class LinkTerminal {
ItemTypeList{
LinkObject first;//始点
LinkObject last;//終点
}
Example
{
main();
}
add();
delete();
LinkTerminal
オブジェクト
search();
display();
}
5.3.2 連結リストのアルゴリズム



①追加アルゴリズム
②検索アルゴリズム
③削除アルゴリズム
追加(1)一般的な追加
public void add(LinkTerminal linkTerminal,ItemType addItemType){
100番地
102番地
108番地
addLink.data = addItemType;
2221
2222
2223
linkTerminal.last.next = addLink;
コーラ
ソーダ
緑茶
102番地
null
108番地
null
first
last
last
//追加する連結オブジェクトを生成する
LinkObject addLink = new LinkObject();
null
linkTerminal.last = addLink;
}
}
追加(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;
}
102番地
2223
null
緑茶
null
first last
null
first last
検索(1)
商品種類が見つかる場合
public ItemType search(int searchId,
LinkTerminal linkTerminal){ searchId 2222
LinkObject current=linkTerminal.first;
while(current!=null){
100番地 102番地
if(current.data.id==searchId){
System.out.println(“見つかりました”) ;
2221
2222
return current.data;
}
紅茶
緑茶
current=current.next;
}
102番地
104番地
System.out.println(“見つかりませんでした”);
return null;
}
first currentcurrent
104番地
2223
水
null
last
検索(2)
商品種類が見つからない場合
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(“見つかりませんでした”);
return null;
}
searchId
3333
100番地
102番地
2221
2221
紅茶
緑茶
102番地
null
null
first currentcurrent last current
削除(1)
リストの中央で見つかる場合
public ItemType delete(int deleteId,
deleteId 2222
LinkTerminal linkTerminal){
LinkObject current=linkTerminal.first;
100番地
102番地
LinkObject previous;
while(current!=null){
2221
2222
if(current.data.id==deleteId){
previous.next=current.next;
紅茶
緑茶
return current.data;
}
previous=current;
102番地
104番地
null 104番地
current=current.next;
}
}
current
first
current
previous previous
×
104番地
2223
水
null
last
削除(2)
リストの最初で見つかる場合
public ItemType delete(int deleteId,
LinkTerminal linkTerminal){
LinkObject current=first;
LinkObject previous;
while(current!=null){
if(current.data.id==deleteId){
if(currrent==first){
first=current.next;
return current.data;
}
null
}
}
previous
deleteId
2221
100番地
102番地
104番地
2221
2222
2223
紅茶
緑茶
水
102番地
104番地
null
first
current
first
last
削除(3)
リストの最後で見つかる場合
public ItemType delete(int deleteId,
LinkTerminal linkTerminal){
deleteId 2223
LinkObject current= linkTerminal.first;
LinkObject previous;
100番地
102番地
104番地
while(current!=null){
if(current.data.id==deleteId){
2221
2222
2223
if(corrent== linkTerminal.last){
last=previous;
紅茶
緑茶
水
last.next=null;
return current.data;
}
null
null
104番地
null 102番地
previous=current;
current=current.next;
}
}
current
first
last
current current last
previous previous previous
}
×
ガベージ･コレクション

削除するときに無駄なメモリが残ってしまう
きがするのですが？
100番地
101番地
102番地
103番地
104番地
‘お’
‘は’
‘よ’
‘ご’
‘ざ’
101
102
103
104
null
Javaでは、いらないメモリを常に見張っている「ガベージコレクタ」
というすばらしい機能が標準でついています。
誰からも参照されていないオブジェクトを自動的にメモリから消します。

Download Report