Listについて

世界で闘うプログラミング力を鍛える150問 ~トップIT企業のプログラマになるための本~

片方向連結リストの表現。

ノードクラス。

package intro.linkedList;

public class Node {
	Node next = null;
	int data;
	
	public Node(int d){
		data = d;
	}
	
	void appendToTail(int d){
		Node end = new Node(d);
		Node node = this;
		while(node.next != null){
			node = node.next;
		}
		node.next = end;
	}
}

確認コード。

package intro.linkedList;

public class Test {

	public static void main(String[] args) {
		Node node1 = new Node(1);
		Node node2 = new Node(2);
		Node node3 = new Node(3);
		
		//node1の次のノードにnode2を指定する
		node1.next = node2;
		//node1から始めるリストに値9を保持するノードを加える
		node1.appendToTail(9);
		
		//ノードの末尾に別のノード(node2)を加えるために、線形探索を行う
		Node node = node1;
		while(node.next != null){
			node = node.next;
		}
		node.next = node3;

		//結果の表示
		node = node1;
		while(node != null){
			System.out.println(node.data);
			node = node.next;
		}
	}

}

循環リストにするには、最後のノードが指す次のノード(null)を、最初のノード(node1)に変更すると良い。

//最後のノードが指す次のノードを最初のノードにして、連結リストにする
node.next.next = node1;

確認コード。

package intro.linkedList;

public class Test {

	public static void main(String[] args) {
		Node node1 = new Node(1);
		Node node2 = new Node(2);
		Node node3 = new Node(3);
		
		//node1の次のノードにnode2を指定する
		node1.next = node2;
		//node1から始めるリストに値9を保持するノードを加える
		node1.appendToTail(9);
		
		//ノードの末尾に別のノード(node2)を加えるために、線形探索を行う
		Node node = node1;
		while(node.next != null){
			node = node.next;
		}
		node.next = node3;
		
		//最後のノードが指す次のノードを最初のノードにして、循環リストにする
		node.next.next = node1;

		//結果の表示
		node = node1;
		
		for(int i=0; i<8; ++i){
			System.out.println(node.data);
			node = node.next;
		}
	}

}

特定の値を保持するノードを削除するメソッドを追加した場合のNodeクラス。

package intro.linkedList;

public class Node {
	Node next = null;
	int data;
	
	public Node(int d){
		data = d;
	}
	
	//ノードの追加
	void appendToTail(int d){
		Node end = new Node(d);
		Node node = this;
		while(node.next != null){
			node = node.next;
		}
		node.next = end;
	}
	
	//特定の値を保持するノード削除する
	Node deleteNode(Node head, int d){
		Node node = head;
		
		if(node.data == d){
			//先頭が削除対象の場合、先頭を次のノードに変更する
			return head.next;
		}
		
		while(node.next != null){
			if(node.next.data == d){
				node.next = node.next.next;
				return head;
			}
			node = node.next;
		}
		
		return node;
	}
	
	//特定の値を保持するノードを削除する
	Node deleteNode(int d){
		Node node = this;
		
		if(node.data == d){
			//先頭が削除対象の場合、先頭を次のノードに変更する
			return this.next;
		}
		
		while(node.next != null){
			if(node.next.data == d){
				node.next = node.next.next;
				return this;
			}
			node = node.next;
		}
		
		return this;
	}
}