線形リストとは - BohYoh.com

282
9-2
ポインタによる線形リスト
本節では、後続ノードを指す《ポインタ》を各ノードにもたせることによって実現する線形
リストを学習します。
ポインタによる線形リスト
リストにデータを挿入する際にノードを生成して、削除する際にノードを破棄すれば、
記憶域を無駄に使うことがなくなります。
そのようなノードを実現するのが、Fig.9-4 に示すクラス Node<E> です。データ用の
フィールドである data とは別に、自分自身
型
指
ための
参照用フィールド next をもちます。
一般に、このようなクラスの構造は自己参照（self-referential）型と呼ばれます。
class Node<E> {
E data;
Node<E> next;
}
// データへの参照
// 後続ノードへの参照
Node<E>
Node<E>
data
next
自分と同じ型のインスタンスへの参照
Fig.9-4 線形リスト用のノード
Node<E> はジェネリックに実現されていますので、データの型 E としては、任意のクラ
ス型が許されます（利用する側で自由に型を指定できます）。
なお、フィールド data の型である E は参
照型ですから、Node<E> をもう少し厳密に図
示すると、Fig.9-5 のようになります。
クラス型変数である data は、データその
ものではなく、あくまでもデータへの《参照》
であることに注意しましょう（p.67）。
▼
線形リスト
9
同
後続ノードを指す矢印に加えて、データを
E
Node<E>
data
next
データ
後続ノード
Node<E>
指す矢印を図示すると、煩雑になるため、以
降の図では、データを指す矢印は省略します。
Fig.9-5 Node<E>のイメージ
後続ノードへの参照である next を、後続ポインタと呼ぶことにします。各ノードの
フィールド next に格納するのは、そのノードの後続ノードへの参照です。ただし、後続
ノードが存在しない《末尾ノード》の後続ポインタの値は、空参照 null とします。
283
ノードの型がクラス Node<E> 型である線形リストを、クラス LinkedList<E> として実現
したプログラムを List 9-1 に示します。
List 9-1 [ A ]
Chap09/LinkedList.java
// 線形リストクラス
import java.util.Comparator;
public class LinkedList<E> {
//--- ノード ---//
class Node<E> {
private E data;
private Node<E> next;
// データ
// 後続ポインタ（後続ノードへの参照）
//--- コンストラクタ ---//
Node(E data, Node<E> next) {
this.data = data;
this.next = next;
}
9-2
private Node<E> head;
private Node<E> crnt;
// 先頭ノード
// 着目ノード
➡
ノードクラス Node<E>
ノードクラス Node<E> には、二つのフィールドとコンストラクタがあります。
■ フィールド
既に説明したとおり、ノードクラス Node<E> には、データへの参照である data と、後
続ポインタ（後続ノードへの参照）である next の二つのフィールドがあります。
■ コンストラクタ
Node<E> のコンストラクタは、引数として受け取った data と next を、対応するフィー
ルドに設定します。
線形リストクラス LinkedList<E>
クラス LinkedList<E> には二つのフィールドがあります。
・head
先頭ノードへの参照です。
・crnt
4
4
したノードに着目した直後に、それ
を
削除
▼
現在着目しているノードへの参照です。探索
コンストラクタやメソッドを実行した後に、crnt の値がどのように更新されるかを、p.294 に
する、といった用途で利用します。
まとめています。
ポインタによる線形リスト
}
284
List 9-1 [ B ]
Chap09/LinkedList.java
//--- コンストラクタ ---//
public LinkedList() {
head = crnt = null;
}
➡
コンストラクタ：LinkedList
線形リストクラス LinkedList<E> のコンストラクタでは、先頭ノードを参照するための
変数 head に空参照 null を代入します。その結果、ノードが一つも存在しない空
線形
が生成されます（Fig.9-6）。
Node<E> 型の変数 head が、先頭
、先頭
ことに注意してください。空の線形リストでは、ノードが存在しないため、head の参
4
4
照先はない（参照すべきノードが存在しない）のです。
4
▼
線形リスト
9
参照
4
4
4
4
4
4
なお、crnt にも null を代入します（いかなる要素にも着目していないことにします）。
null（ノードを参照しない）
head
Fig.9-6 空の線形リスト
■ 空の線形リスト
この図から、線形リストが空である（ノードが 1 個も存在しない）かどうかを、以下の
式で調べられることが分かりますね。
head == null
// 線形リストは空か？
■ ノードが１個の線形リスト
Fig.9-7 に示すのは、線形リストにノードが１個だけ存在する線形リストです。
Node<E> 型の変数 head の参照先は、先頭ノードＡです。その先頭ノードＡは、リスト
の末尾ノードでもあるため、その後続ポインタの値は空参照 null です。
head が参照するノードがもっている後続ポインタの値が空参照 null ですから、線形リ
スト上に存在するノードが１個のみであるかどうかの判定は、以下の式で調べられること
になります。
head.next == null
// ノードは１個だけか？
285
head
先頭ノードかつ末尾ノード
A
head.next
Fig.9-7 ノードが１個の線形リスト
なお、ノード中のフィールド data は、データそのものではなく、データへの参照です
から（p.282）、ノードＡのデータへの参照を表す式は、head.data となります。
■ ノードが２個の線形リスト
9-2
末尾ノードはノードＢです。
このとき、head が参照するノードＡがもっている後続ポインタ next が、ノードＢを参
照しています（すなわち、head.next の参照先がノードＢとなっています）。
末尾ノードＢの後続ポインタは空参照 null ですから、線形リスト上に存在するノード
が２個であるかどうかの判定は、以下の式で調べられることになります。
head.next.next == null
// ノードは２個か？
また、ノードＡのデータへの参照を表す式は head.data となり、ノードＢのデータへの
参照を表す式は head.next.data となります。
head
A
B
head.next
head.next.next
Fig.9-8 ノードが２個の線形リスト
■ 末尾ノードの判定
Node<E> 型の変数 p が、リスト上のノードを参照しているとします。変数 p が参照して
いるノードが、線形リストの末尾ノードであるかどうかの判定は、以下の式によって行え
ます。
p.next == null
// pが参照するノードは末尾ノードか？
ポインタによる線形リスト
Fig.9-8 に示すのは、ノードが２個存在する線形リストです。先頭ノードはノードＡで、
286
探索：search
任意の条件を満たすノードを探索するメソッドです。
探索アルゴリズムは線形探索です。Fig.9-9 に示すように、目的とするノードに出会う
まで、先頭ノードから順に走査します。
リスト内のノードを
先頭から順に走査。
head
①
A
線形リスト
9
②
B
③
④
C
D
E
F
Fig.9-9 ノードの探索（線形探索）
ノードの走査は、以下に示す条件のいずれか一方が成立したときに終了します。
探索条件を満たすノードが見つからず末尾ノードを通り越しそうになった。
探索条件を満たすノードを見つけた。
なお、本メソッドが受け取る引数は、以下に示す二つです。
・第 1 引数 obj … 探索のキーとなるデータを格納したオブジェクト。
・第 2 引数 c …
第 1 引数で与えられた obj と線形リスト上の個々のノード内データと
（p.96）。
を比較するための
コンパレータ c によって、obj と着目ノードのデータとを比較した結
果が 0 であれば、探索条件が成立しているとみなします。
＊
具体的な探索の様子を示した Fig.9-10 と対比しながら、プログラムを理解しましょう。
走査中のノードを参照するための変数 ptr を head で初期化します。図
に示すように、
ptr の参照先は、head が参照している先頭ノードＡとなります。
終了条件
の判定を行います。ptr の値が null でなければ、ループ本体（
・
）
を実行します。ptr の値が null であれば、走査すべきノードが存在しないということ
です。while 文の実行を終了して
終了条件
に進みます。
の判定を行います。データ obj と、走査中ノードのデータ ptr.data とを
コンパレータ c によって比較します。compare メソッドが返す値が 0 であれば、終了条
件が成立して探索成功です。crnt に ptr を代入するとともに、見つけたノードのデー
タである ptr.data を返却します。
287
List 9-1 [ C ]
Chap09/LinkedList.java
//--- ノードを探索 ---//
public E search(E obj, Comparator<? super E> c) {
Node<E> ptr = head;
// 現在走査中のノード
}
while (ptr != null) {
if (c.compare(obj, ptr.data) == 0) {
crnt = ptr;
return ptr.data;
}
ptr = ptr.next;
}
return null;
// 探索成功
// 後続ノードに着目
// 探索失敗
➡
ptr に ptr.next を代入することによって、走査を次のノードへと進めます。
▼
らノードＢへと更新されるからです。
プログラムの流れがここに到達するのは、探索に失敗したときです。探索失敗である
ことを示す null を返します。
ptrはheadが参照するノードＡを参照。
ptr = head;
ptrが参照して
いるノード
head
A
ptr = ptr.next;
B
C
D
E
F
ptrはノードＡの後続ポインタが参照しているノードＢを参照。
head
A
ptr = ptr.next;
B
C
D
E
F
ptrはノードＢの後続ポインタが参照しているノードＣを参照。
head
A
Fig.9-10 ノードの探索
B
C
D
E
F
9-2
ポインタによる線形リスト
ptr がノードＡを参照している図の状態で ptr = ptr.next の代入を実行すると、図となり
ます。後続ノードＢへの参照である ptr.next が ptr に代入された結果、ptr の参照先がノードＡか
288
先頭へのノードの挿入：addFirst
リストの先頭にノードを挿入するメソッドです。
挿入の手続きを Fig.9-11 に示す具体例で考えましょう。図
▼
ノードＧを挿入した後の状態が図
に示すリストの先頭に
です。
黒い矢印が、挿入によって追加・変更されるポインタです（これ以降の図も同様です。ノードの
挿入や削除に伴って追加・変更されるポインタを黒矢印で示します）。
挿入前の先頭ノードＡを指すポインタを ptr に保存しておきます。
挿入するノードＧを new Node<E>(obj, ptr) によって生成します。ノードのデータは
obj となり、後続ポインタの参照先は ptr（挿入前の先頭ノードＡ）となります。
線形リスト
9
▼
それから、生成したノードを参照するように head を更新します。
crnt の参照先も、新しく挿入したノードとなるように更新します（メソッド addLast も同様です）。
挿入前
挿入前
head
挿入後
A
B
C
D
E
F
挿入後
挿入されたノードを参照。
head
G
Ａ
挿入前の先頭ノードを参照。
Ｂ
Ｃ
Ｄ
Ｅ
Ｆ
ptr
Fig.9-11 先頭へのノードの挿入
末尾へのノードの挿入：addLast
リストの末尾にノードを挿入するメソッドです。リストが空であるか（head == null が
成立するか）どうかで異なる処理をします。
・リストが空のとき
先頭へのノード挿入と同じことを行うことになりますので、メソッド addFirst に挿入
処理をゆだねます。
・リストが空でないとき
挿入の手続きを Fig.9-12 に示す具体例で考えましょう。図
ノードＧを挿入した後の状態が図
です。
に示すリストの末尾に
289
List 9-1 [ D ]
Chap09/LinkedList.java
//--- 先頭にノードを挿入 ---//
public void addFirst(E obj) {
Node<E> ptr = head;
// 挿入前の先頭ノード
head = crnt = new Node<E>(obj, ptr);
}
//--- 末尾にノードを挿入 ---//
public void addLast(E obj) {
if (head == null)
// リストが空であれば
addFirst(obj);
// 先頭に挿入
else {
Node<E> ptr = head;
while (ptr.next != null)
while文終了時、ptrは末尾ノードへの参照となる。
ptr = ptr.next;
ptr.next = crnt = new Node<E>(obj, null);
}
}
➡
ノードを先頭から順に走査します。ptr.next の参照先が null となったら while 文が終
了します。
このとき、ptr の参照先は末尾ノードＦとなります。
挿入するノードＧを new Node<E>(obj, null) によって生成します。生成されたノー
ドＧのデータは obj となり、後続ポインタの参照先は null となります
▼
4 4
4
4
後続ポインタを null にするのは、末尾ノードがいかなるノードも参照しないようにするためです。
ノードＦの後続ポインタ ptr.next の参照先が、新しく挿入されたノードＧとなるよ
うに更新します。
挿入前
head
ptr
Ａ
Ｂ
Ｃ
Ｄ
Ｅ
Ａ
Ｂ
Ｃ
Ｄ
Ｅ
挿入前
Ｆ
挿入後
挿入後
head
ptr
挿入後の末尾ノードを参照。
Fig.9-12 末尾へのノード挿入
Ｆ
Ｇ
null
ポインタによる線形リスト
ここで行うのは、末尾ノードを見つける処理です。先頭ノードを参照するように初
期化された ptr の参照先を、その後続ポインタに更新する処理を繰り返すことによって、
9-2
290
先頭ノードの削除：removeFirst
先頭ノードを削除するメソッドです。削除処理を行うのは、リストが空でない（すなわ
ち head != null が成立する）ときのみです。
削除の手続きを Fig.9-13 に示す具体例で考えましょう。図
ノードＡを削除した後の状態が図
に示すリストから先頭
です。
先頭ノードへの参照である head に対して、先頭から 2 番目のノードＢへの参照である
▼
head.next を代入することによって、head の参照先をノードＢに更新します。
着目ノード crnt の参照先もノードＢとなります。
その結果、削除前の先頭ノードＡは、どこからも参照されなくなり、その記憶域は自動
▼
的に解放されます。
線形リスト
9
どこからも参照されなくなったオブジェクト（配列とクラスインスタンス）の領域は、ガーベジ
コレクション（garbage collection）の働きによって、自動的に解放されることになっています。
削除前
削除前
head
削除後
A
B
C
D
E
F
削除後
削除前に先頭ノードが参照していたノードを参照。
head
A
B
C
D
E
F
どこからも参照されない。
▼
Fig.9-13 先頭ノードの削除
リスト上にノードが 1 個しかない場合（Fig.9-7：p.285）でも、正しく削除処理が行われてリ
ストは空になります。削除前の先頭ノードは末尾ノードでもあるため、その後続ポインタ head.
next の値は null です。その null が head に代入されると、リストは空になります。
末尾ノードの削除：removeLast
末尾ノードを削除するメソッドです。削除処理を行うのは、リストが空でないときのみ
です。リストに存在するノードが１個だけであるかどうかで異なる処理をします。
・リスト上にノードが１個だけ存在するとき
先頭ノードを削除するわけですから、メソッド removeFirst に処理をゆだねます。
・リスト上にノードが 2 個以上存在するとき
削除の手続きを Fig.9-14 に示す具体例で考えましょう。
291
List 9-1 [ E ]
Chap09/LinkedList.java
//--- 先頭ノードを削除 ---//
public void removeFirst() {
if (head != null)
head = crnt = head.next;
}
// リストが空でなければ
//--- 末尾ノードを削除 ---//
public void removeLast() {
if (head != null) {
if (head.next == null)
removeFirst();
else {
Node<E> ptr = head;
Node<E> pre = head;
// ノードが一つだけであれば
// 先頭ノードを削除
while (ptr.next != null) {
pre = ptr;
while文終了時、ptrは末尾ノードへの参照となり、
ptr = ptr.next;
preは末尾から２番目のノードへの参照となる
}
pre.next = null;
// preは削除後の末尾ノード
crnt = pre;
9-2
}
}
➡
ここで行うのは、《末尾ノード》と《末尾から 2 番目のノード》を見つける処理です。
そのための走査は、メソッド addLast（p.289）の
とほぼ同じです。ただし、現在走
査中のノードの《先行ノード》を参照する変数 pre が追加されています。
図に示す例であれば、while 文が終了したときには、pre の参照先はノードＥ、ptr
の参照先はノードＦとなります。
末尾から 2 番目のノードＥの後続ポインタに null を代入します。その結果、どこか
▼
らも参照されなくなるノードＦの記憶域は自動的に解放されます。
着目ノード crnt の参照先は、削除後の末尾ノード pre となります。
削除前
削除前
削除前
head
A
B
C
D
A
B
C
D
pre
ptr
E
F
pre
ptr
E
F
削除後
削除後
head
null
Fig.9-14 末尾ノードの削除
どこからも参照されない。
ポインタによる線形リスト
}
// 走査中のノード
// 走査中のノードの先行ノード
292
List 9-1 [ F ]
Chap09/LinkedList.java
//--- ノードpを削除 ---//
public void remove(Node p) {
if (head != null) {
if (p == head)
removeFirst();
else {
Node<E> ptr = head;
}
線形リスト
9
}
}
// pが先頭ノードであれば
// 先頭ノードを削除
while (ptr.next != p) {
ptr = ptr.next;
if (ptr == null) return;
}
ptr.next = p.next;
crnt = ptr;
// pはリスト上に存在しない
//--- 着目ノードを削除 ---//
public void removeCurrentNode() {
remove(crnt);
}
//--- 全ノードを削除 ---//
public void clear() {
while (head != null)
removeFirst();
crnt = null;
}
// 空になるまで
// 先頭ノードを削除
//--- 着目ノードを一つ後方に進める ---//
public boolean next() {
if (crnt == null || crnt.next == null)
return false;
// 進めることはできなかった
crnt = crnt.next;
return true;
}
➡
ノードの削除：remove
任意のノードを削除するメソッドです。削除処理を行うのは、リストが空でなく、引数
で指示されたノード p が存在するときのみです。
・p が先頭ノードのとき
先頭ノードを削除することになりますので、メソッド removeFirst に処理をゆだねます。
・p が先頭ノードでないとき
削除の手続きを Fig.9-15 に示す具体例で考えましょう。図
照しているノードＤを削除した後の状態が図
に示すリストから p が参
です。
4 4
ここで行うのは、ノード p の先行ノードを見つける処理です。
while 文は、走査を先頭ノードから開始して、着目ノード ptr の後続ポインタ ptr.
next が p と等しくなるまで繰り返されます。
ただし、途中で null を見つけた場合は、p が参照するノードが存在しないというこ
とです。削除処理を行うことなく、return によってメソッドを終了します。
293
削除前
削除前
head
削除後
Ａ
Ｂ
ptr
p
Ｃ
Ｄ
Ｅ
Ｆ
削除後
head
どこからも参照されない。
ptr
Ａ
Ｂ
Ｃ
Ｄ
Ｅ
Ｆ
削除前の次の次のノードを参照。
9-2
ptr.next が p と等しくなると while 文は終了します。このとき、ptr の参照先は、削
除するノードＤの先行ノードであるノードＣとなっています。
ノードＤの後続ポインタ p.next をノードＣの後続ポインタ ptr.next に代入すること
によって、ノードＣの後続ポインタの参照先を、ノードＥに更新します。
▼
その結果、どこからも参照されなくなるノードＤの記憶域は自動的に解放されます。
着目ノード crnt の参照先は、削除したノードの先行ノード（この図ではノードＣ）となるよう
に更新されます。
着目ノードの削除：removeCurrentNode
現在着目しているノードを削除するメソッドです。remove メソッドに crnt を渡して処
▼
理をゆだねます。
本メソッドの実行によって、着目ノード crnt の参照先は、削除したノードの先行ノードに更新
されます。
全ノードの削除：clear
すべてのノードを削除するメソッドです。線形リストが空になる（head が null になる）
▼
まで、先頭要素の削除を繰り返して全ノードを削除します。
リストが空になりますから、着目ノード crnt の値も null に更新します。
着目ノードを一つ後方に進める：next
着目ノードを一つ後方に進めるメソッドです。リストが空でなく、着目ノードに後続
ノードが存在するときのみ、着目ノードを一つ進めます。
着目ノードを進めたときは true を、そうでないときは false を返します。
ポインタによる線形リスト
Fig.9-15 ノードの削除
294
List 9-1 [ G ]
Chap09/LinkedList.java
//--- 着目ノードを表示 ---//
public void printCurrentNode() {
if (crnt == null)
System.out.println("着目ノードはありません。");
else
System.out.println(crnt.data);
}
//--- 全ノードを表示 ---//
public void dump() {
Node<E> ptr = head;
while (ptr != null) {
System.out.println(ptr.data);
ptr = ptr.next;
}
}
}
着目ノードの表示：printCurrentNode
着目ノードを表示するメソッドです。crnt が参照するノードのデータ crnt.data（に対
して暗黙裏に toString メソッドが呼び出された結果得られる文字列）を表示します。
ただし、着目ノードが存在しない場合は（crnt が null であれば）、その旨を『着目ノー
ドはありません。』と表示します。
全ノードの表示：dump
リスト順に全ノードを表示するメソッドです。
先頭ノードから末尾ノードまで走査しながら、各ノードのデータ ptr.data（に対して
暗黙裏に toString メソッドが呼び出された結果得られる文字列）を表示します。
▼
線形リスト
9
なお、このメソッドは crnt の値を更新しません。
＊
各メソッド実行後の crnt の値をまとめると、以下のようになります。
コンストラクタ
null。
search
addFirst
addLast
removeFirst
removeLast
remove
removeCurrentNode
clear
next
printCurrentNode
dump
探索に成功すれば見つけたノード。
挿入した先頭ノード。
挿入した末尾ノード。
削除後の先頭ノード（リストが空になれば null）。
削除後の末尾ノード（リストが空になれば null）。
削除したノードの先行ノード。
削除したノードの先行ノード。
null。
移動後の着目ノード。
（更新しない）
（更新しない）
295
線形リストを利用するプログラム
線形リストクラス LinkedList<E> を利用するプログラム例を List 9-2 に示します。
List 9-2 [ A ]
Chap09/LinkedListTester.java
// 線形リストクラスLinkedList<E>の利用例
import java.util.Scanner;
import java.util.Comparator;
public class LinkedListTester {
static Scanner stdIn = new Scanner(System.in);
//--- データ（会員番号＋氏名） ---//
static class Data {
static final int NO
= 1;
// 番号を読み込むか？
static final int NAME = 2;
// 氏名を読み込むか？
ポインタによる線形リスト
private Integer no;
private String name;
9-2
// 会員番号
// 氏名
//--- 文字列表現を返す ---//
public String toString() {
return "(" + no + ") " + name;
}
//--- データの読込み ---//
void scanData(String guide, int sw) {
System.out.println(guide + "するデータを入力してください。");
}
if ((sw & NO) == NO) {
System.out.print("番号：");
no = stdIn.nextInt();
}
if ((sw & NAME) == NAME) {
System.out.print("名前：");
name = stdIn.next();
}
//--- 会員番号による順序付けを行うコンパレータ ---//
public static final Comparator<Data> NO_ORDER =
new NoOrderComparator();
private static class NoOrderComparator implements Comparator<Data> {
public int compare(Data d1, Data d2) {
return (d1.no > d2.no) ? 1 : (d1.no < d2.no) ? -1 : 0;
}
}
//--- 氏名による順序付けを行うコンパレータ ---//
public static final Comparator<Data> NAME_ORDER =
new NameOrderComparator();
}
private static class NameOrderComparator implements Comparator<Data> {
public int compare(Data d1, Data d2) {
return d1.name.compareTo(d2.name);
}
}
➡
296
List 9-2 [ B ]
Chap09/LinkedListTester.java
//--- メニュー列挙型 ---//
enum Menu {
ADD_FIRST( "先頭にノードを挿入"),
ADD_LAST(
"末尾にノードを挿入"),
RMV_FIRST( "先頭ノードを削除"),
RMV_LAST(
"末尾ノードを削除"),
RMV_CRNT(
"着目ノードを削除"),
CLEAR(
"全ノードを削除"),
SEARCH_NO( "番号で探索"),
SEARCH_NAME("氏名で探索"),
NEXT(
"着目ノードを進める"),
PRINT_CRNT( "着目ノードを表示"),
DUMP(
"全ノードを表示"),
TERMINATE( "終了");
線形リスト
9
private final String message;
// 表示用文字列
static Menu MenuAt(int idx) {
for (Menu m : Menu.values())
if (m.ordinal() == idx)
return m;
return null;
}
// 序数がidxである列挙を返す
Menu(String string) {
message = string;
}
// コンストラクタ
String getMessage() {
return message;
}
// 表示用文字列を返す
}
//--- メニュー選択 ---//
static Menu SelectMenu() {
int key;
do {
for (Menu m : Menu.values()) {
System.out.printf("(%d) %s ", m.ordinal(), m.getMessage());
if ((m.ordinal() % 3) == 2 &&
m.ordinal() != Menu.TERMINATE.ordinal())
System.out.println();
}
System.out.print("：");
key = stdIn.nextInt();
} while (key < Menu.ADD_FIRST.ordinal() ||
key > Menu.TERMINATE.ordinal());
return Menu.MenuAt(key);
}
public static void main(String[] args) {
Menu menu;
// メニュー
Data data;
// 追加用データ参照
Data ptr;
// 探索用データ参照
Data temp = new Data();
// 読込み用データ
LinkedList<Data> list = new LinkedList<Data>();
do {
switch (menu = SelectMenu()) {
// リストを生成
297
case ADD_FIRST :
// 先頭にノードを挿入
data = new Data();
data.scanData("先頭に挿入", Data.NO | Data.NAME);
list.addFirst(data);
break;
case ADD_LAST :
// 末尾にノードを挿入
data = new Data();
data.scanData("末尾に挿入", Data.NO | Data.NAME);
list.addLast(data);
break;
case RMV_FIRST :
list.removeFirst();
break;
// 先頭ノードを削除
case RMV_LAST :
list.removeLast();
break;
// 末尾ノードを削除
case RMV_CRNT :
list.removeCurrentNode();
break;
// 着目ノードを削除
9-2
case SEARCH_NAME :
// 氏名で探索
temp.scanData("探索", Data.NAME);
ptr = list.search(temp, Data.NAME_ORDER);
if (ptr == null)
System.out.println("その名前のデータはありません。");
else
System.out.println("探索成功：" + ptr);
break;
}
}
case NEXT :
list.next();
break;
// 着目ノードを後方に進める
case PRINT_CRNT :
list.printCurrentNode();
break;
// 着目ノードのデータを表示
case DUMP :
list.dump();
break;
// 全ノードをリスト順に表示
case CLEAR :
list.clear();
break;
// 全ノードを削除
}
} while (menu != Menu.TERMINATE);
ポインタによる線形リスト
case SEARCH_NO :
// 会員番号で探索
temp.scanData("探索", Data.NO);
ptr = list.search(temp, Data.NO_ORDER);
if (ptr == null)
System.out.println("その番号のデータはありません。");
else
System.out.println("探索成功：" + ptr);
break;
298
実行例
先頭にノードを挿入 (1) 末尾にノードを挿入 (2) 先頭ノードを削除
末尾ノードを削除 (4) 着目ノードを削除 (5) 全ノードを削除
番号で探索 (7) 氏名で探索 (8) 着目ノードを進める
着目ノードを表示 (10) 全ノードを表示 (11) 終了：0 Ÿ
先頭に挿入するデータを入力してください。
番号：1 Ÿ
名前：赤尾 Ÿ
(0)
(3)
(6)
(9)
先頭にノードを挿入 (1) 末尾にノードを挿入 (2) 先頭ノードを削除
末尾ノードを削除 (4) 着目ノードを削除 (5) 全ノードを削除
番号で探索 (7) 氏名で探索 (8) 着目ノードを進める
着目ノードを表示 (10) 全ノードを表示 (11) 終了：1 Ÿ
末尾に挿入するデータを入力してください。
番号：5 Ÿ
名前：武田 Ÿ
{
赤尾 }を先頭に挿入。
{
武田 }を末尾に挿入。
{
小野 }を先頭に挿入。
{
鈴木 }を末尾に挿入。
{
神崎 }を先頭に挿入。
(0)
(3)
(6)
(9)
先頭にノードを挿入 (1) 末尾にノードを挿入 (2) 先頭ノードを削除
末尾ノードを削除 (4) 着目ノードを削除 (5) 全ノードを削除
番号で探索 (7) 氏名で探索 (8) 着目ノードを進める
着目ノードを表示 (10) 全ノードを表示 (11) 終了：0 Ÿ
先頭に挿入するデータを入力してください。
番号：10 Ÿ
名前：小野 Ÿ
(0)
(3)
(6)
(9)
線形リスト
9
先頭にノードを挿入 (1) 末尾にノードを挿入 (2) 先頭ノードを削除
末尾ノードを削除 (4) 着目ノードを削除 (5) 全ノードを削除
番号で探索 (7) 氏名で探索 (8) 着目ノードを進める
着目ノードを表示 (10) 全ノードを表示 (11) 終了：1 Ÿ
末尾に挿入するデータを入力してください。
番号：12 Ÿ
名前：鈴木 Ÿ
(0)
(3)
(6)
(9)
先頭にノードを挿入 (1) 末尾にノードを挿入 (2) 先頭ノードを削除
末尾ノードを削除 (4) 着目ノードを削除 (5) 全ノードを削除
番号で探索 (7) 氏名で探索 (8) 着目ノードを進める
着目ノードを表示 (10) 全ノードを表示 (11) 終了：0 Ÿ
先頭に挿入するデータを入力してください。
番号：14 Ÿ
名前：神崎 Ÿ
(0)
(3)
(6)
(9)
(0)
(3)
(6)
(9)
先頭にノードを挿入 (1) 末尾にノードを挿入 (2) 先頭ノードを削除
末尾ノードを削除 (4) 着目ノードを削除 (5) 全ノードを削除
番号で探索 (7) 氏名で探索 (8) 着目ノードを進める
着目ノードを表示 (10) 全ノードを表示 (11) 終了：3 Ÿ
先頭にノードを挿入 (1) 末尾にノードを挿入 (2) 先頭ノードを削除
末尾ノードを削除 (4) 着目ノードを削除 (5) 全ノードを削除
番号で探索 (7) 氏名で探索 (8) 着目ノードを進める
着目ノードを表示 (10) 全ノードを表示 (11) 終了：7 Ÿ
探索するデータを入力してください。
名前：鈴木 Ÿ
その名前のデータはありません。
末尾の{
鈴木 }を削除。
(0)
(3)
(6)
(9)
先頭にノードを挿入 (1) 末尾にノードを挿入 (2) 先頭ノードを削除
末尾ノードを削除 (4) 着目ノードを削除 (5) 全ノードを削除
番号で探索 (7) 氏名で探索 (8) 着目ノードを進める
着目ノードを表示 (10) 全ノードを表示 (11) 終了：6 Ÿ
探索するデータを入力してください。
番号：10 Ÿ
探索成功：(10) 小野
{ 鈴木 }を探索／失敗。
(0)
(3)
(6)
(9)
(0) 先頭にノードを挿入 (1) 末尾にノードを挿入 (2) 先頭ノードを削除
(3) 末尾ノードを削除 (4) 着目ノードを削除 (5) 全ノードを削除
(6) 番号で探索 (7) 氏名で探索 (8) 着目ノードを進める
(9) 着目ノードを表示 (10) 全ノードを表示 (11) 終了：9 Ÿ
(10) 小野
(0)
(3)
(6)
(9)
先頭にノードを挿入 (1) 末尾にノードを挿入 (2) 先頭ノードを削除
末尾ノードを削除 (4) 着目ノードを削除 (5) 全ノードを削除
番号で探索 (7) 氏名で探索 (8) 着目ノードを進める
着目ノードを表示 (10) 全ノードを表示 (11) 終了：8 Ÿ
(0)
(3)
(6)
(9)
先頭にノードを挿入 (1) 末尾にノードを挿入 (2) 先頭ノードを削除
末尾ノードを削除 (4) 着目ノードを削除 (5) 全ノードを削除
番号で探索 (7) 氏名で探索 (8) 着目ノードを進める
着目ノードを表示 (10) 全ノードを表示 (11) 終了：9 Ÿ
{
}を探索／成功。
着目ノードは{
小野 }。
着目ノードを進める。
299
着目ノードは{
(1) 赤尾
(0) 先頭にノードを挿入 (1) 末尾にノードを挿入 (2) 先頭ノードを削除
(3) 末尾ノードを削除 (4) 着目ノードを削除 (5) 全ノードを削除
(6) 番号で探索 (7) 氏名で探索 (8) 着目ノードを進める
(9) 着目ノードを表示 (10) 全ノードを表示 (11) 終了：10 Ÿ
(14) 神崎
(10) 小野
(1) 赤尾
(5) 武田
(0)
(3)
(6)
(9)
先頭にノードを挿入 (1) 末尾にノードを挿入 (2) 先頭ノードを削除
末尾ノードを削除 (4) 着目ノードを削除 (5) 全ノードを削除
番号で探索 (7) 氏名で探索 (8) 着目ノードを進める
着目ノードを表示 (10) 全ノードを表示 (11) 終了：4 Ÿ
(0) 先頭にノードを挿入 (1) 末尾にノードを挿入 (2) 先頭ノードを削除
(3) 末尾ノードを削除 (4) 着目ノードを削除 (5) 全ノードを削除
(6) 番号で探索 (7) 氏名で探索 (8) 着目ノードを進める
(9) 着目ノードを表示 (10) 全ノードを表示 (11) 終了：10 Ÿ
(14) 神崎
(10) 小野
(5) 武田
全ノードを順に表示。
着目ノードを削除。
全ノードを順に表示。
先頭にノードを挿入 (1) 末尾にノードを挿入 (2) 先頭ノードを削除
末尾ノードを削除 (4) 着目ノードを削除 (5) 全ノードを削除
番号で探索 (7) 氏名で探索 (8) 着目ノードを進める
着目ノードを表示 (10) 全ノードを表示 (11) 終了：11 Ÿ
□ 演習 9-1
コンパレータ c によって互いに等しいとみなすことのできる全ノードを削除する以下のメソッド
を作成せよ。
void purge(Comparator<? super E> c)
□ 演習 9-2
先頭から n 個後ろのノードのデータへの参照（n が 0 であれば先頭ノードのデータへの参照、n
が 1 であれば 2 番目のノードのデータへの参照、…）を返す以下のメソッドを作成せよ。なお、n
が負の値かノード数以上であれば null を返すこと。
E retrieve(int n)
□ 演習 9-3
下図のように、先頭ノードへの参照 head に加えて末尾ノードへの参照 tail を導入すると、末尾
ノードが容易に探索できるようになる。このようにして実現する線形リストクラス LinkedListT<E>
を作成せよ。
LinkedList<E> が提供するメソッドと同じメソッドをすべて作成すること。
tail
head
Ａ
Ｂ
Ｃ
Ｄ
Ｅ
Ｆ
9-2
ポインタによる線形リスト
(0)
(3)
(6)
(9)
赤尾 }。

Download Report