|
下図のように、先頭ノードへの参照head に加えて末尾ノードへの参照tail を導入すると、末尾ノードが容易に探索できるようになる。このようにして実現する線形リストクラスLinkedListT <E >を作成せよ。 LinkedList <E >が提供するメソッドと同じメソッドをすべて作成すること。  |
// 演習9-3 // 線形リストクラス（末尾ノードへのポインタも管理） import java.util.Comparator; public class LinkedListT<E> { //--- ノード ---// class Node<E> { private E data; // データ private Node<E> next; // 後続ポインタ（後続ノードへの参照） //--- コンストラクタ ---// Node(E data, Node<E> next) { this.data = data; this.next = next; } } private Node<E> head; // 先頭ノード private Node<E> tail; // 末尾ノード private Node<E> crnt; // 着目ノード //--- コンストラクタ ---// public LinkedListT() { head = tail = crnt = null; } //--- ノードを探索 ---// public E search(E o, Comparator<? super E> c) { Node<E> ptr = head; // 現在走査中のノード while (ptr != null) { if (c.compare(o, ptr.data) == 0) { // 探索成功 crnt = ptr; return ptr.data; } ptr = ptr.next; // 後続ノードに着目 } return null; // 探索失敗 } //--- 先頭にノードを挿入 ---// public void addFirst(E o) { boolean empty = (tail == null); Node<E> ptr = head; // 挿入前の先頭ノード head = crnt = new Node<E>(o, ptr); if (empty) tail = crnt; } //--- 末尾にノードを挿入 ---// public void addLast(E o) { if (head == null) // リストが空であれば addFirst(o); // 先頭に挿入 else { tail.next = crnt = new Node<E>(o, null); tail = crnt; } } //--- 先頭ノードを削除 ---// public void removeFirst() { if (head != null) { // リストが空でなければ head = crnt = head.next; if (head == null) tail = null; } } //--- 末尾ノードを削除 ---// 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; ptr = ptr.next; } pre.next = null; // preは削除後の末尾ノード tail = crnt = pre; } } } //--- ノードpを削除 ---// public void remove(Node<E> p) { if (head != null) { if (p == head) // pが先頭ノードであれば removeFirst(); // 先頭ノードを削除 else if (p == tail) // pが末尾ノードであれば removeLast(); // 末尾ノードを削除 else { Node<E> ptr = head; while (ptr.next != p) { ptr = ptr.next; if (ptr == null) return; // pはリスト上に存在しない } ptr.next = p.next; crnt = ptr; } } } //--- 着目ノードを削除 ---// 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; } //--- 着目ノードを表示 ---// public void printCurrentNode() { if (crnt == null) System.out.println("着目ノードはありません。"); else System.out.println(crnt.data.toString()); } //--- 全ノードを表示 ---// public void dump() { Node<E> ptr = head; while (ptr != null) { System.out.println(ptr.data.toString()); ptr = ptr.next; } } //------------------------------ 演習9-1 ------------------------------// //--- コンパレータcによって互いに等しいとみなせるノードをすべて削除 ---// public void purge(Comparator<? super E> c) { Node<E> ptr = head; while (ptr != null) { int count = 0; Node<E> ptr2 = ptr; Node<E> pre = ptr; while (pre.next != null) { ptr2 = pre.next; if (c.compare(ptr.data, ptr2.data) == 0) { pre.next = ptr2.next; count++; } else pre = ptr2; } if (count == 0) ptr = ptr.next; else { Node<E> temp = ptr; remove(ptr); ptr = temp.next; } } crnt = head; } //------------------------------ 演習9-2 ------------------------------// //--- 先頭からn個後ろのノードのデータへの参照を返却 ---// public E retrieve(int n) { Node<E> ptr = head; while (n >= 0 && ptr != null) { if (n-- == 0) { crnt = ptr; return (ptr.data); /* 探索成功 */ } ptr = ptr.next; /* 後続ノードに着目 */ } return (null); } }
// 演習9-3 // 線形リストクラスLinkedListT<E>の利用例 import java.util.Scanner; import java.util.Comparator; public class LinkedListTTester { 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; // 氏名 //--- 文字列表現を返す ---// 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); } } } //--- メニュー列挙型 ---// public enum Menu { ADD_FIRST( "先頭にノードを挿入"), ADD_LAST( "末尾にノードを挿入"), RMV_FIRST( "先頭ノードを削除"), RMV_LAST( "末尾ノードを削除"), RMV_CRNT( "着目ノードを削除"), CLEAR( "全ノードを削除"), SEARCH_NO( "番号で探索"), SEARCH_NAME("氏名で探索"), NEXT( "着目ノードを進める"), PRINT_CRNT( "着目ノードを表示"), PURGE_NO( "同一番号のノードを削除"), PURGE_NAME( "同一氏名のノードを削除"), RETRIEVE( "任意のノードを表示"), DUMP( "全ノードを表示"), TERMINATE( "終了"); private final String message; // 表示用文字列 static Menu MenuAt(int idx) { // 序数がidxである列挙を返す for (Menu m : Menu.values()) if (m.ordinal() == idx) return m; return null; } 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(); // 読込み用データ LinkedListT<Data> list = new LinkedListT<Data>(); // リストを生成 do { switch (menu = SelectMenu()) { 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; 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; 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; case PURGE_NO : // 同一番号のノードを削除 list.purge(Data.NO_ORDER); break; case PURGE_NAME : // 同一氏名のノードを削除 list.purge(Data.NAME_ORDER); break; case RETRIEVE : { // 任意のノードを表示 System.out.print("先頭から何番目："); int no = stdIn.nextInt() - 1; ptr = list.retrieve(no); if (ptr == null) System.out.println("データは存在しません。"); else System.out.println("データは" + ptr.toString() + "です。"); } } } while (menu != Menu.TERMINATE); } }
