DLink 双向双端链表

DLink 实现一个简单的双向双端链表

与Link一样，假定其之存储非负整数，并提供最能反映双向双端链表特征的方法

实现时利用辅助类DNode实现，DNode是双向节点

基本添加删除数据方法

addFirst, addLast, removeFirst, removeLast

遍历方法:

hasNext, next, resetToBeforeFirst

hasPrevious, previous, resetToAfterLast

遍历时插入，删除方法

insertAfter, removeAfter

insertBefore, removeBefore

其她:

getLength, indexOf

class DNode {
	private int value;
	private DNode next;
	private DNode previous;

	DNode(int value) {
		this.value = value;
	}
	
	int getValue() {
		return value;
	}

	void setNext(DNode next) {
		this.next = next;
	}

	DNode getNext() {
		return next;
	}

	void setPrevious(DNode previous) {
		this.previous = previous;
	}

	DNode getPrevious() {
		return previous;
	}
}

 

class DLink {
	private DNode first;
	private DNode last;
	private int length;
	private boolean isBeforeFirst = true;
	private boolean isAfterLast = false;
	private DNode current;

	private static void connect(DNode previous, DNode next) {
		if(previous != null) previous.setNext(next);
		if(next != null) next.setPrevious(previous);
	}

	void addFirst(int value) {
		DNode node = new DNode(value);
		connect(node,first);
		first = node;
		if(last == null) last = node;
		length++;
	}

	void addLast(int value) {
		DNode node = new DNode(value);
		connect(last,node);
		last = node;
		if(first == null) first = node;
		length++;
	}


	int removeFirst() {
		if(first ==  null) return -1;
		int result = first.getValue();
		first = first.getNext();
		connect(null,first);
		if(first == null) last = null;
		length--;
		return result;
	}

	int removeLast() {
		if(last == null) return -1;
		int result = last.getValue();
		last = last.getPrevious();
		connect(last,null);
		if(last == null) first = null;
		length--;
		return result;
	}

	int getLength() {
		return length;
	}

	boolean hasNext() {
		if(isAfterLast) return false;
		else if(isBeforeFirst) return first != null;
		else return current.getNext() != null;
	}

	int next() {
		if(isBeforeFirst) {
			isBeforeFirst = false;
			current = first;
		} else current = current.getNext();
		if (current ==  null) isAfterLast = true;
		return current != null ? current.getValue() : -1;
	}

	void resetBeforeFirst() {
		isBeforeFirst = true;
		isAfterLast = false;
		current = null;
	}

	boolean hasPrevious() {
		if(isBeforeFirst) return false;
		else if(isAfterLast) return last != null;
		else return current.getPrevious() != null; 
	}

	int previous() {
		if(isAfterLast) {
			isAfterLast = false;
			current = last;
		} else current = current.getPrevious();
		if(current == null) isBeforeFirst = true;
		return current != null ? current.getValue() : -1;
	}

	void resetAfterLast() {
		isAfterLast = true;
		isBeforeFirst = false;
		current = null;
	}

	int removeBefore() {
		if(!hasPrevious()) return -1;
		else if (isAfterLast) return removeLast();
		else if (current.getPrevious() ==  first) return removeFirst();
		else {
			int result = current.getPrevious().getValue();
			connect(current.getPrevious().getPrevious(),current);
			length--;
			return result;
		}
	}

	int removeAfter() {
		if(!hasNext()) return -1;
		else if (isBeforeFirst) return removeFirst();
		else if (current.getNext() == last) return removeLast();
		else {
			int result = current.getNext().getValue();
			connect(current,current.getNext().getNext());
			length--;
			return result;
		}
	}

	void insertBefore(int value) {
		if(!hasPrevious()) addFirst(value);
		else if(isAfterLast) addLast(value);
		else {
			DNode node = new DNode(value);
			connect(current.getPrevious(),node);
			connect(node,current);
			length++;
		}
	}

	void insertAfter(int value) {
		if(!hasNext()) addLast(value);
		else if(isBeforeFirst) addFirst(value);
		else {
			DNode node = new DNode(value);
			connect(node,current.getNext());
			connect(current,node);
			length++;
		}
	}
	
	int indexOf(int value) {
		int i = 0;
		DNode node = first;
		while(node != null) {
			if(node.getValue() == value) return i;
			i++;
			node = node.getNext();
		}
		return -1;	
	}

}