【Java】ポインタによる線形リスト

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

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

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

線形リスト

package chap08;

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;
		}
	}
	
	// 変数の宣言
	private Node<E> head;    // 先頭ポインタ（先頭ノードへの参照）
	private Node<E> crnt;    // 着目ポインタ（着目ノードへの参照）
	
	//--- コンストラクタ ---//
	public LinkedList() {
		
		// 初期化
		crnt = null;
		head = crnt;
		//head = crnt = null;と同義
	}
	
	
	//--- ノードを探索 ---//
	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;    // 探索失敗
	}
	
	
	//--- 先頭にノードを挿入 ---//
	public void addFirst(E obj) {
		
		Node<E> ptr = head;    // 挿入前の先頭ノード
		crnt = new Node<E>(obj, ptr);
		head = crnt;
		//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) {
				
				ptr = ptr.next;
			}
			
			crnt     = new Node<E>(obj, null);
			ptr.next = crnt;
			// ptr.next = crnt = new Node<E>(obj, null);と同義
		}
	}
	
	
	//--- 先頭ノードを削除 ---//
	public void removeFirst() {
		
		// リストが空でないとき
		if (head != null) {
			crnt = head.next;
			head = crnt;
			// 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;
					ptr = ptr.next;
				}
				
				pre.next = null;
				crnt     = pre;
			}
		}
	}
	
	
	//--- ノードpを削除 ---//
	public void remove(Node p) {
		
		if (head != null) {
			
			// p が先頭ノードであるとき
			if (p == head) {
				
				// 先頭ノードを削除
				removeFirst();
			} 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);
		}
	}
	
	
	//--- 全ノードを表示 ---//
	public void dump() {
		
		Node<E> ptr = head;
		
		while (ptr != null) {
			System.out.println(ptr.data);
			ptr = ptr.next;
		}
	}
}

学習内容まとめ

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

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