JJavaでコパレータで互いに等しいとみなすことのできる線形リストの全ノードを削除するメソッドをつくったのですが、上手く動きません。

Question

学習中のJavaテキストで線形リストについての章があり、その中で
「コパレータcによって互いに等しいとみなすことのできる全ノードを削除する以下のメソッドを作成せよ。
void purge(Comparator<? super E> c)」
という課題がありました。自分でメソッドを作成したのですが、上手く動かないので原因を教えてください。

0. //purgeメソッド以外はテキストに載っていた線形リストを表すクラスです。
1.//purgeメソッドが自分で作ったクラス、purge2メソッドが模範解答です。
2.//ノード
3.class Node<E> {
4.		private E data; // データ
5.		private Node<E> next; // 後続ポインタ(後続ノードへの参照）
6.
7.		// コンストラクタ
8.		Node(E data, Node<E> next) {
9.			this.data = data;
10.			this.next = next;
11.		}
12.	}
13.//線形リストクラス
14.public class LinkedList<E> {
15.	private Node<E> head; // 先頭ノード
16.	private Node<E> crnt; // 着目ノード
17.
18.	// コンストラクタ
19.	public LinkedList() {
20.		head = crnt = null;
21.	}
22.//先頭にノードを挿入
23.public void addFirst(E obj) {
24.		Node<E> ptr = head; // 挿入前の先頭ノード
25.		head = crnt = new Node<E>(obj, ptr); // ノードのデータはobj,後続ポインタの参照先は挿入前の先頭ノード
26.	}
27.//先頭ノードを削除
28.public void removeFirst() {
29.		if (head != null) { // リストが空でなければ
30.			head = crnt = head.next;
31.		}
32.	}
33.//ノードpを削除
34.public void remove(Node<E> p) {
35.		if (head != null) {
36.			if (p == head) // pが先頭ノードであれば
37.				removeFirst(); // 先頭ノードを削除
38.		} else {
39.			Node<E> ptr = head;
40.
41.			while (ptr.next != p) {
42.				ptr = ptr.next;
43.				if (ptr == null) {
44.					return; // pはリスト上に存在しない
45.				}
46.			}
47.			ptr.next = p.next; 
48.			crnt = ptr; // 削除したノードの先行ノードを参照先とする
49.		}
50.	}
51.// コンパレータcによって互いに等しいとみなすことのできる全ノードを削除する
52.public void purge(Comparator<? super E> c) {
53.		Node<E> ptr1 = head; // 比較対象1
54.		Node<E> ptr2; // 比較対象2
55.		Node<E> temp; // 
56.		int counter = 0;
57.
58.		while (ptr1.next != null) {
59.			ptr2 = ptr1.next;
60.			while (ptr2 != null) {
61.				if (c.compare(ptr1.data, ptr2.data) == 0) {
62.					counter++;
63.					temp = ptr2.next;
64.					remove(ptr2); //ここでptr2が削除されない
65.					ptr2 = temp;
66.				} else if (ptr2 != null) {
67.					ptr2 = ptr2.next;
68.				}
69.			}
70.			temp = ptr1.next;
71.			if (counter >= 1) {
72.				remove(ptr1); //ptr1が削除されるときとされない時がある。
73.			}
74.			ptr1 = temp;
75.			counter = 0;
76.		}
77. //模範解答
78.public void purge2(Comparator<? super E> c) {
79.		Node<E> ptr = head; // 比較用1
80.		while (ptr != null) {
81.			int count = 0;
82.			Node<E> ptr2 = ptr; // 比較用2
83.			Node<E> pre = ptr;
84.
85.			while (pre.next != null) {
86.				ptr2 = pre.next;
87.				if (c.compare(ptr.data, ptr2.data) == 0) {
88.					pre.next = ptr2.next;// ptr2はどこからも参照されなくなり削除される
89.					count++;
90.				} else {
91.					pre = ptr2;
92.				}
93.			}
94.			if (count == 0) {
95.				ptr = ptr.next;
96.			} else {
97.				Node<E> temp = ptr;
98.				remove(ptr);
99.				ptr = temp.next;
100.			}
101.		}
102.		crnt = head;
103.	}
104. // 末尾にノードを挿入
105. public void addLast(E obj) {
106.		if (head == null) { // リストが空であれば
107.			addFirst(obj); // 先頭に挿入
108.		} else {
109.			Node<E> ptr = head;
110.			// 末尾ノードを見つける処理
111.			while (ptr.next != null) {
112.				ptr = ptr.next;
113.			}
114.			ptr.next = crnt = new Node<E>(obj, null);
115.		}
116.	}
117.// 全ノードを表示
118.	public void dump() {
119.		Node<E> ptr = head;
120.		while (ptr != null) {
121.			System.out.println(ptr.data);
122.			ptr = ptr.next;
123.		}
124.	}
125.
130.   public static void main(String[] args) {
131.		LinkedList<Data> list = new LinkedList<Data>();
132.		Data d1 = new Data(1, "sayama");
133.		Data d2 = new Data(2, "aki");
134.		Data d3 = new Data(3, "sayama");
135.		Data d4 = new Data(4, "akagi");
136.		Data d5 = new Data(5, "sayama");
137.		list.addFirst(d1);
138.		list.addLast(d2);
139.		list.addLast(d3);
140.		list.addLast(d4);
141.		list.addLast(d5);
142.		System.out.println(Data.NAME_ORDER.compare(d1, d3));
143.		list.dump();
144.		System.out.println("名前でパージします");
145.		list.purge(Data.NAME_ORDER);
146.		System.out.println();
147.		list.dump();
148.	}
149. }

上手く動かない原因は、64行目と72行目のremoveメソッドで削除したいノードを削除できていないからと思っています。

Answer 1

33.//ノードpを削除
34.public void remove(Node<E> p) {
35.        if (head != null) {
36.            if (p == head) // pが先頭ノードであれば
37.                removeFirst(); // 先頭ノードを削除
38.        } else {
39.            Node<E> ptr = head;
40.
41.            while (ptr.next != p) {
42.                ptr = ptr.next;
43.                if (ptr == null) {
44.                    return; // pはリスト上に存在しない
45.                }
46.            }
47.            ptr.next = p.next; 
48.            crnt = ptr; // 削除したノードの先行ノードを参照先とする
49.        }
50.    }

この38行目のelseは、if (head != null)に対するもの、つまりheadがnullの時に入るブロックになります。
対してif (head != null)のブロック中では先頭ノードしか比較していないため、それ以外に対象ノードがあった場合に削除できません。
それ以外にも「等しい」ことを==で比較していたり、突っ込みどころが多すぎます。

Comments

[DAISUKE0549]

ご回答ありがとうございました。自分がテキストに載っていたremoveメソッドを書きか間違えていたことがわかりました。