オブジェクト・プログラミング
第9回
連結リスト
今後の予定
第9回 参照と連結リスト
第10回 オブジェクト指向クラス設計②
データの隠蔽と継承。クラス図
第11回 グラフィカルユーザインターフェースの
設計
第12回 オブジェクトの設計
イベント・ドリブンと状態遷移図
第13回 オブジェクトの相互作用の設計
シーケンス図、コラボレーション図
評価方法
毎回の課題 ６５点
最終課題 ３５点
自動販売機を設計しなさい。UMLで記述して
事務室に提出。
＋発展課題 ２０点
１００点打ち切り
今日の目標
プログラムの動く仕組みを説明できるよう
になる。
参照（ポインタ）とはなにか説明できるようにな
る。
連結リストの概念を説明できるようになる。
連結リストを使ったプログラムが書けるように
なる。
今日のところは本当に難しいです！
心してかかってください！
参照（ポインタ）って何？
問題：
プリントの
PointerQuestion1と
PointerQuestion2が
どのような出力をするか考えなさい。
PointerQuestion1
public static void main(String args[]){
int x;
int y;
x = 3;
y = x;
y = 15;
System.out.println(x);
System.out.println(y);
}
PointerQuesiton2
public static void main(String args[]){
TestClass x;
TestClass y;
x = new TestClass();
x.no = 3;
y = x;
y.no = 15;
System.out.println(x.no);
System.out.println(y.no);
}
class TestClass {
int no;
答え
PointerQuestion1
3
15
PointerQuestion2
15
15
何故そんな結果になるのか？
プログラムは、変数をメモリに格納します。
メモリには、
すべての場所に
番地がついています。
この番地のことを
参照といったり
ポインタといったり
します。
メモリ
番地
100
101
102
103
104
内容
Javaプログラムの動く仕組み(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
Javaプログラムの動く仕組み(2)
メモリ
番地(100)
番地(101)
TestClass x;
TestClass y;
x = new TestClass();
x.no = 3;
y = x;
y.no = 15;
System.out.println(x.no);
System.out.println(y.no);
番地
内容
x
100
1000
null
0(初期値)
y
101
1000
null
オブジェクト用のメモリ
1000
1001
15
3
0(初期値)
Javaプログラムの動く仕組み
（まとめ）
変数を宣言すると、メモリに領域が確保される。
=(代入)記号での代入文は、値のコピーが行わ
れる。
ただし、オブジェクトの場合は、値に参照が入っ
ているため、参照のコピーが行われる。
このとき、オブジェクトのコピーは行われない。
オブジェクトを生成するとオブジェクト用のメモリ
が確保される。
オブジェクト型とプリミティブ型
※これはJavaだけの話です。
プリミティブ型
→値が直接入るタイプ
オブジェクト型
→オブジェクト用のメモリに生成され、参照
が入るタイプ
どうやって見分けたらいいでしょうか？
プリミティブ型を覚えよ。
Javaのプリミティブ型は8種類しかない。
整数が入るもの
boolean
実数（小数）が入るもの
float
double
int
long
short
真偽値が入るもの
文字が入るもの
byte(1バイト文字)
char(2バイト文字)
その他はすべてオブジェクト型
new 演算子でインスタンス化する必要が
あります。
オブジェクト用のメモリ
実は配列も
番地
内容
オブジェクト型です。[0] 1000
0
int[] noArray = new int[5];
メモリ
noArray
[1]
1001
0
[2]
1002
0
番地
内容
[3]
1003
0
101
1000(番地)
[4]
1004
0
参照（ポインタ）まとめ
変数は、メモリに入る。
メモリには、番地がある。
実際の値が入る場合と、参照が入る場合
がある。
難しいですね！
ですが、これを理解できれば、あなたも立派な
Javaプログラマーです！
配列以外のデータ構造
連結リスト
何故連結リストが必要か？
テキストエディタ（メモ帳,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
‘す’
‘ま’
配列での実装の問題点
もし、これが、１万文字のレポートの最初の
所だったらどうなるか？
一文字挿入するごとに、１万回の移動が必要
になります。
だれも使ってくれません。
そんなときは！連結リスト
100番地
102番地
104番地
106番地
108番地
‘お’
‘は’
‘よ’
‘ご’
‘ざ’
102
104
106
108
null
実際のメモリ上では
番地
内容
100
‘お’
101
102
102
‘は’
103
104
104
‘よ’
105
106
106
‘う’
107
null
連結リストへの挿入
移動しなくて済む！
100番地
102番地
104番地
106番地
108番地
‘お’
‘は’
‘よ’
‘ご’
‘ざ’
102
104
106
110
108
null
110番地
‘う’
106
連結リストからの削除
もっと簡単！
100番地
102番地
104番地
106番地
108番地
‘お’
‘は’
‘よ’
‘ご’
‘ざ’
102
104
106
106
108
null
連結リストの利点・欠点
利点
挿入、削除が非常に早い。 O(1)
メモリを確保しておく必要が無い。
配列の時のようにMaxSizeを気にする必要が無い
配列は何も入っていないところはメモリの無駄
欠点
検索が遅い O(N)
最初から順繰りに辿っていかないといけない
番地を保存しておくためのメモリ領域を取る
連結リストを使った実装
第５回の課題を思い出しましょう！
ItemInfoFolderの、挿入、削除、検索、表示メ
ソッドを完成させなさいというものでした。
前回は、配列を使って作りました。
こいつは配列を
使っていた
今日の課題
今日の課題は、第５回の課題と行なう仕事
はまったく変えずに、だけど、中身は違う方
法（連結リストで）作り変えるというのが課
題です。
今日は、
連結リストを使う！
連結リストをJavaで実装する
連結リスト用オブジェクトListObjectを作る
//連結リスト用オブジェクト
class ListObject {
ItemInfo data; //商品情報
ListObject next; //次の要素への参照
}
？？自分で自分を持ってるの？？
連結リストをJavaで実装する
実は参照なので、図のようになります。
//連結リスト用オブジェクト
class ListObject {
ItemInfo data;
ListObject next;
}
100番地
102番地
22(no)
23(no)
コーラ
ソーダ
102番地
null
※
※
※実際にはItemInfoも参照です。
連結リストを使った
ItemInfoFolderクラスの実装
100番地
102番地
104番地
106番地
108番地
2221
2222
2223
2224
2225
コーラ
ソーダ
オレンジ
紅茶
緑茶
102番地
104番地
106番地
108番地
null
first
last
挿入や検索をするために、Folderクラスは、
常にリストの最初の番地(first)と最後の番地(last)
だけは、知っておく必要があります。
連結リストを使った
ItemInfoFolderクラス(挿入①)
public void insert(ItemInfo insItem){
ListObject insList = new ListObject();
insList.data = insItem;
}
last.next = insList;
last = insList;
100番地
102番地
108番地
2221
2222
2223
コーラ
ソーダ
緑茶
102番地
null
108番地
null
first
last
last
null
連結リストを使った
ItemInfoFolderクラス(挿入②)
一番最初の挿入をする場合を考慮すると、、、
102番地
public void insert(ItemInfo insItem){
ListObject insList = new ListObject();
insList.data = insItem;
}
if(first == null){
first = insList;
last = insList;
}else{
last.next = insList;
last = insList;
}
2223
null
緑茶
null
first last
null
first last
連結リストを使った
ItemInfoFolderクラス(検索①)
探したい商品情報が見つかる場合、、、
public ItemInfo search(int searchKey){
ListObject current=first;
while(current!=null){
if(current.data.no==searchKey){
System.out.println(“見つかりました”) ;
return current.data;
}
current=current.next;
}
System.out.println(“見つかりませんでした”);
return null;
}
searchKey 2222
100番地 102番地 104番地
2221
2222
2223
紅茶
緑茶
水
102番地
104番地
null
first currentcurrent
last
連結リストを使った
ItemInfoFolderクラス(検索②)
探したい商品情報が見つからない場合、、、
public ItemInfo search(int searchKey){
ListObject current=first;
while(current!=null){
if(current.data.no==searchKey){
System.out.println(“見つかりました”) ;
return current.data;
}
current=current.next;
}
System.out.println(“見つかりませんでした”);
return null;
}
searchKey 3333
100番地
102番地
2221
2221
紅茶
緑茶
102番地
null
null
first currentcurrent last current
連結リストを使った
ItemInfoFolderクラス(削除①)
削除したい要素が、リストの中央で見つかる場合、、、
public ItemInfo delete(int deleteKey){
ListObject current=first;
ListObject previous;
while(current!=null){
if(current.data.no==deleteKey){
previous.next=current.next;
return current.data;
}
previous=current;
null
current=current.next;
}
}
deleteKey
2222
100番地
102番地
104番地
2221
2222
2223
紅茶
緑茶
水
104番地
null
102番地
104番地
×
current
first
previous previous
current
last
連結リストを使った
ItemInfoFolderクラス(削除②)
削除したい要素が、リストの最初で見つかる場合、、、
public ItemInfo delete(int deleteKey){
ListObject current=first;
ListObject previous;
while(current!=null){
if(current.data.no==deleteKey){
if(corrent==first){
first=current.next;
return current.data;
}
null
}
}
previous
deleteKey
2221
100番地
102番地
104番地
2221
2222
2223
紅茶
緑茶
水
102番地
104番地
null
first
current
first
last
連結リストを使った
ItemInfoFolderクラス(削除③)
削除したい要素が、リストの最後で見つかる場合、、、
public ItemInfo delete(int deleteKey){
deleteKey 2223
ListObject current=first;
ListObject previous;
100番地
102番地
104番地
while(current!=null){
if(current.data.no==deleteKey){
2221
2222
2223
if(corrent==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
}
×
今日もスケルトンを配ります。
課題のスケルトン
VendingMachineMain.java(第５回と同じ)
ItemInfo.java(第５回と同じ)
ItemInfoFolder
ItemInfoFolderのdisplay()メソッドを完成
させなさい。
（今回は答え入りではないはずです。)
発展課題
前回の課題（第８回課題）で、配列で実装
したItemQueueクラスをこれもまったく同じ
仕事をするように連結リストで書き換えなさ
い。（実は配列よりも簡単にできます。）
提出方法
[email protected]宛て。
今回もソースのみを送ってください。
（ただし、ItemInfoFolder(リスト実装版)だけでよ
い。)
Subjectはログイン名を必ず書いてください。
(感想を任意でお願いします。)
ex) t96844ym
余計な[]などをつけないでください。
水曜まで。
© Copyright 2024 ExpyDoc
