【Java】循環・重連結リスト

この記事は、「新・明解Javaで学ぶアルゴリズムとデータ構造」を読んで学んだことを、個人的な備忘録目的でまとめています。

ただし、本を参考にして自分なりに構成やコードを変更しているためご注意ください。
アルゴリズムの詳細や解説は是非参考書をお手に取って読まれてください。

【リンク紹介】
・Javaで学ぶアルゴリズムとデータ構造
・これまで書いたシリーズ記事一覧

循環・重連結リスト

package chap08;

import java.util.Comparator;

// 循環・重連結リストクラス
public class DoubleLinkedList<E> {
	
	//--- ノード ---//
	class Node<E> {
		private E data;          // データ
		private Node<E> prev;    // 先行ポインタ
		private Node<E> next;    // 後続ポインタ
		
		//--- コンストラクタ ---//
		Node() {
			data = null;
			prev = next;
			next = this;
			// 参考書では次のように記述
			// prev = next = this;
		}
		
		//--- コンストラクタ ---//
		Node(E obj, Node<E> prev, Node<E> next) {
			data = obj;
			this.prev = prev;
			this.next = next;
		}
	}
	
	private Node<E> head;    // 先頭ポインタ（参照先はダミーノード）
	private Node<E> crnt;    // 着目ポインタ
	
	//--- コンストラクタ（ノードの挿入や削除の処理を円滑に行うためのもの） ---//
	public DoubleLinkedList() {
		crnt = new Node<E>();    // ダミーノードを生成。自分自身のノードを参照するように初期化される
		head = crnt;
		// 参考書では次のように記述
		// head = crnt = new Node<E>();
	}
	
	//--- リストは空か ---//
	public boolean isEmpty() {
		return head.next == head;
	}
	
	//--- ノードを探索 ---//
	public E search(E obj, Comparator<? super E> c) {
		Node<E> ptr = head.next;    // 現在走行中のノード
		
		while (ptr != head) {
			if (c.compare(obj, ptr.data) == 0) {
				crnt = ptr;
				return ptr.data;    // 探索成功
			}
			ptr = ptr.next;         // 後続ノードに着目
		}
		return null;                // 探索失敗
	}
	
	//--- 着目ノードを表示 ---//
	public void printCurrentNode() {
		if (isEmpty()) {
			System.out.println("着目ノードはありません。");
		} else {
			System.out.println(crnt.data);
		}
	}
	
	//--- 全ノードを表示 ---//
	public void dump() {
		Node<E> ptr = head.next;    // ダミーノードの後続ノード
		
		while (ptr != head) {
			System.out.println(ptr.data);
			ptr = ptr.next;
		}
	}
	
	//--- 全ノードを逆順に表示 ---//
	public void dumpReverse() {
		Node<E> ptr = head.prev;    // ダミーノードの先行ノード
		
		while (ptr != head) {
			System.out.println(ptr.data);
			ptr = ptr.prev;
		}
	}
	
	//--- 着目ノードを一つの後方に進める ---//
	public boolean next() {
		if (isEmpty() || crnt.next == head) {
			return false;    // 進めることができなかった
		}
		
		crnt = crnt.next;
		return true;
	}
	
	//--- 着目ノードを一つ前方に進める ---//
	public boolean prev() {
		if (isEmpty() || crnt.prev == head) {
			return false;    // 進めることができなかった
		}
		
		crnt = crnt.prev;
		return true;
	}
	
	//--- 着目ノードの直後にノードを挿入 ---//
	public void add(E obj) {
		Node<E> node = new Node<E>(obj, crnt, crnt.next);
		crnt.next = crnt.next.prev = node;
		crnt = node;
	}
	
	//--- 先頭にノードを挿入 ---//
	public void addFirst(E obj) {
		crnt = head;    // ダミーノードheadの直後に挿入
		add(obj);
	}
	
	//--- 末尾にノードを挿入 ---//
	public void addLast(E obj) {
		crnt = head.prev;    // 末尾ノードhead.prevの直後に挿入
		add(obj);
	}
	
	//--- 着目ノードを削除 ---//
	public void removeCurrentNode() {
		if (!isEmpty()) {
			crnt.prev.next = crnt.next;
			crnt.next.prev = crnt.prev;
			crnt = crnt.prev;
			if (crnt == head) crnt = head.next;
		}
	}
	
	//--- ノードpを削除 ---//
	public void remove(Node p) {
		Node<E> ptr = head.next;
		
		while (ptr != head) {
			
			// pをみつけたとき
			if (ptr == p) {
				crnt = p;
				removeCurrentNode();
				break;
			}
			ptr = ptr.next;
		}
	}
	
	//--- 先頭ノードを削除 ---//
	public void removeFirst() {
		crnt = head.next;          // 先頭ノードhead.nextを削除
		removeCurrentNode();
	}

	//--- 末尾ノードを削除 ---//
	public void removeLast() {
		crnt = head.prev;          // 末尾ノードhead.nextを削除
		removeCurrentNode();
	}
	
	//--- 全ノードを削除 ---//
	public void clear() {
		while (!isEmpty()) {       // 空になるまで
			removeFirst();         // 先頭ノードを削除
		}
	}

}

学習内容まとめ

eclipse操作時に役立つショートカットまとめ
https://qiita.com/toshi0383/items/1d2a990392998789062c

$\bf{\textcolor{red}{記事が役に立った方は「いいね」を押していただけると、すごく喜びます \ 笑}}$
ご協力のほどよろしくお願いします。