双方向チェーン学習ノート

1.チェーンテーブルインタフェースの定義

package com.ncs.datastructure.linklist;

public interface ILinkList {

	/**
	 *       
	 * @return
	 */
	public abstract boolean isEmpty();

	/**
	 *               
	 * @param data
	 */
	public abstract void addToHead(Object data);

	/**
	 *               
	 * @param data
	 */
	public abstract void addToTail(Object data);

	/**
	 *            
	 * @return
	 */
	public abstract Object deleteFromHead();

	/**
	 *             
	 * @return
	 */
	public abstract Object deleteFromTail();

	/**
	 *             
	 * @param data
	 * @return
	 */
	public abstract boolean isContains(Object data);

	/**
	 *        
	 * @param data
	 */
	public abstract void deleteNode(Object data);

}

2.双方向チェーンテーブルの簡単な実現

package com.ncs.datastructure.linklist;

import com.ncs.datastructure.linklist.SingleLinkList.Node;


/**
 *          
 * @author yuanli
 *
 */
public class DoubleLinkList implements ILinkList {
	
	/**
	 *          ，                ，           
	 * @author yuanli
	 *
	 */
	public class Node {
		
		//   
		private Object data;
		
		//    
		private Node prev;
		
		//    
		private Node next;

		public Node() {
			super();
		}

		public Node(Object data) {
			this(data, null, null);
		}
		
		public Node(Object data, Node prev, Node next) {
			super();
			this.data = data;
			this.prev = prev;
			this.next = next;
		}

		public Object getData() {
			return data;
		}

		public void setData(Object data) {
			this.data = data;
		}

		public Node getPrev() {
			return prev;
		}

		public void setPrev(Node prev) {
			this.prev = prev;
		}

		public Node getNext() {
			return next;
		}

		public void setNext(Node next) {
			this.next = next;
		}
		
		
	}
	
	//          
	protected Node head;
	
	//           
	protected Node tail;

	public void addToHead(Object data) {
		if (this.head == null) {
			this.head = new Node(data);
			if (this.tail == null ) this.tail = this.head;
		} else {
			Node temp = new Node(data,null,this.head);
			this.head.prev = temp;
			this.head = temp;
		}
	}

	public void addToTail(Object data) {
		if (!isEmpty()) {
			this.tail = new Node(data, this.tail, null);
			this.tail.prev.next = this.tail;
		} else {
			this.tail = this.head = new Node(data); 
		}
	}

	public Object deleteFromHead() {
		Node delete = null;
		if (this.head == this.tail) {
			delete = this.head;
			this.head = this.tail = null;
		} else {
			delete = this.head;
			this.head = this.head.next;
			this.head.prev = null;
		}
		return delete;
	}

	public Object deleteFromTail() {
		Node delete = null;
		if (this.head == this.tail) {
			delete = this.head;
			this.head = this.tail = null;
		} else {
			delete = this.tail;
			this.tail = this.tail.prev;
			this.tail.next = null;
		}
		return delete;
	}

	public void deleteNode(Object data) {
		if (!isEmpty()) {
			//        
			if (this.head == this.tail) {
				this.head = this.tail = null;
				return;
			}
			//          
			if (this.head.data.equals(data)) {
				this.deleteFromHead();
				return;
			}
			
			//           
			if (this.tail.data.equals(data)) {
				this.deleteFromTail();
				return;
			}
			
			//      
			for (Node temp = this.head; temp.next != null; temp = temp.next) {
				if (temp.data.equals(data)) {
//					Node prev = temp.prev;
//					Node next = temp.next;
//					prev.next = next;
//					next.prev = prev;
					temp.prev.next = temp.next;
					temp.next.prev = temp.prev;
				}
			}
		}
	}

	public boolean isContains(Object data) {
		if (!isEmpty()) {
			Node temp = this.head;
			for (; temp.next != null; temp = temp.next) {
				if (temp.data.equals(data)) {
					return true;
				}
			}
		}
		return false;
	}

	public boolean isEmpty() {
		return this.head == null;
	}

	/**
	 *          ，          
	 */
	public void printAll() {
		Node temp = this.head;
		for (; temp != null; temp = temp.next) {
			System.out.println("node data is " + temp.data);
		}
	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {

		//           
		DoubleLinkList dll = new DoubleLinkList();
		
		//          
		dll.addToHead("node1");
		dll.addToTail("node2");
		dll.addToTail("node3");
		dll.addToTail("node4");
		dll.addToTail("node5");
		
		//        
		dll.printAll();
		
		//       
		dll.deleteFromHead();
		
		//        
		dll.deleteFromTail();
		
		//        
		dll.printAll();

		//            
		boolean isExsist = dll.isContains("node11");
		System.out.println(isExsist);
		
		//       
		dll.deleteNode("node3");
		dll.printAll();
	}
}

3.まとめ
双方向チェーンテーブルは、一方向チェーンテーブルの不足を補い、最後のノードを削除するときにチェーンテーブル全体を巡回する必要がなく、最後のノードを直接操作するなど、隣接するノードを双方向に取得することができます.