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;
	}
}

データ構造 〜 第2章 連結リスト 問題2-1

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

問題2-1.

ソートされていない連結リストから、重複する要素を削除する。

下記方法で書いた。

１．再帰
２．HashMapを使用して、登場済みの数字を記憶しておく。

1.再帰を使ったコード。

public Node deleteDuplicatedNode(Node head){
		if(head == null){
			return head;
		}
		
		int tmp = head.data;
		Node node = head;
		while(node.next != null){
			if(node.next.data == tmp){
				head = head.next;
				return deleteDuplicatedNode(head);
			}
			node = node.next;
		}
		return head;
	}

Nodeクラス。

package intro.linkedList;

public class Node {
	public Node next = null;
	public int data;
	
	public Node(int d){
		data = d;
	}
	
	//ノードの追加
	public void appendToTail(int d){
		Node end = new Node(d);
		Node node = this;
		while(node.next != null){
			node = node.next;
		}
		node.next = end;
	}
	
	//特定の値を保持するノード削除する
	public 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;
	}
	
	//特定の値を保持するノードを削除する
	public 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;
	}
	
	//ソートされていない連結リストから重複する要素を削除するメソッド
	public Node deleteDuplicatedNode(Node head){
		if(head == null){
			return head;
		}
		
		int tmp = head.data;
		Node node = head;
		while(node.next != null){
			if(node.next.data == tmp){
				head = head.next;
				return deleteDuplicatedNode(head);
			}
			node = node.next;
		}
		return head;
	}
	
}

確認用。

package problem2_1;

import intro.linkedList.Node;

public class Solve2_1 {

	public static void main(String[] args) {
		Node node1 = new Node(1);
		node1.appendToTail(2);
		node1.appendToTail(3);
		node1.appendToTail(4);
		node1.appendToTail(5);
		node1.appendToTail(4);
		node1.appendToTail(3);
		node1.appendToTail(2);
		node1.appendToTail(1);
	
		
		Node node = node1;
		while(node != null){
			System.out.println(node.data);
			node = node.next;
		}
		System.out.println("**********");
		
		node = node1;
		Node tmpNode = node.deleteDuplicatedNode(node);
		while(tmpNode != null){
			System.out.println(tmpNode.data);
			tmpNode = tmpNode.next;
		}
	}
	
}

２．HashMapを使用する方法

//ソートされていない連結リストから重複する要素を削除するメソッド
	public Node deleteDuplicatedNode1(Node head){
		HashMap<Integer, Boolean> map = new HashMap<Integer, Boolean>();
		
		Node node = head;
		Node before = head;
		while(node != null){
			if(map.containsKey(node.data)){
				before.next = node.next;
			}else{
				map.put(node.data, true);
				before = node;
			}
			node = node.next;
		}
		return head;
	}

データ構造 〜 第2章 連結リスト 「ランナー」テクニック

ランナーテクニックとは、連結リストの最初から順に巡回するポインタと、そのポインタより先を巡回するポインタの２種類を同時に使用する方法。

「データ構造　〜　第2章　連結リスト　問題2-1」で扱った連結リストから重複する要素を削除する問題を、ランナーテクニックを使用して解く。

//ソートされていない連結リストから重複する要素を削除するメソッド
	public Node deleteDuplicatedNodeByRunner(Node head){
		if(head == null){
			return head;
		}
		
		Node node = head;
		while(node != null){
			Node runner = node;
			while(runner.next != null){
				if(runner.next.data == node.data){
					runner.next = runner.next.next;
				}else{
					runner = runner.next;
				}
			}
			node = node.next;
		}
		//headは、nodeの最初の要素を指したままで変わらない。
		return head;
	}

データ構造 〜 第3章 スタックとキュー

スタックの実装。

package intro;

public class Stack {
	Node top;
	
	Object pop(){
		if(top != null){
			Object item = top.data;
			top = top.next;
			return item;
		}
		return null;
	}
	
	void push(Object item){
		Node t = new Node(item);
		t.next = top;
		top = t;
	}
	
	Object peek(){
		return top.data;
	}
}

キューの実装。

package intro;

public class Queue {
	Node first, last;
	
	void enqueue(Object item){
		if(first == null){
			last =  new Node(item);
			first = last;
		}else{
			last.next = new Node(item);
			last = last.next;
		}
	}
	
	Object dequeue(){
		if(first != null){
			Object item = first.data;
			first = first.next;
			return item;
		}
		return null;
	}
}

確認。

package intro;

public class Test {

	public static void main(String[] args) {
		Stack stack = new Stack();
		String str = "a";
		stack.push(str);
		stack.push(str+"1");
		stack.push(str+"2");
		
		System.out.println(stack.pop());
		System.out.println(stack.pop());
		System.out.println(stack.pop());
		
		System.out.println();
		
		Queue queue = new Queue();
		queue.enqueue(str);
		queue.enqueue(str+"1");
		queue.enqueue(str+"2");
		
		System.out.println(queue.dequeue());
		System.out.println(queue.dequeue());
		System.out.println(queue.dequeue());
	}

}