本节内容

双向链表，实现入队出队

特征

比单向链表多了一个before指针，指向其上级。
如此，可以从任意节点倒推。
以前遍历，只能从前往后，现在可以从后往前。

结构

public class LinkedQueue2 {
	private final Node head = new Node("");

	class Node {
		private String data;
		private Node next;
		private Node before;

		public Node(String data) {
			this.data = data;
		}
	}

节点加入

public LinkedQueue2 addOne(String s) {
	Node temp = new Node(s);
	Node last = getLast();
	
	//握手
	last.next = temp;
	temp.before = last;
	
	System.out.println(this);
	return this;
}

节点删除

public Node removeOne() {
	if (head.next == null) {
		throw new RuntimeException("没啦");
	} else {
		Node temp = head.next;
		//失忆
		temp.before = null;
		if (temp.next == null) {
			//只有一个节点
			//失忆
			head.next = null;
		} else {
			//有多个节点
			Node next = temp.next;
			//失忆
			next.before = head;
			head.next = next;
		}
		System.out.println(this);
		return temp;
	}
}

全部代码

public class LinkedQueue2 {
	private final Node head = new Node("");

	public static void main(String[] args) {
		LinkedQueue2 queue = new LinkedQueue2();
		queue.addOne("A").addOne("B").addOne("C").addOne("D");
		queue.removeOne();
		queue.removeOne();
		queue.removeOne();
		queue.removeOne();
	}

	class Node {
		private String data;
		private Node next;
		private Node before;

		public Node(String data) {
			this.data = data;
		}

		@Override
		public String toString() {
			return "[" + data + "]=>" + next;
		}
	}

	@Override
	public String toString() {
		return head.toString();
	}

	public LinkedQueue2 addOne(String s) {
		Node temp = new Node(s);
		Node last = getLast();
		last.next = temp;
		temp.before = last;
		System.out.println(this);
		return this;
	}

	public Node removeOne() {
		if (head.next == null) {
			throw new RuntimeException("没啦");
		} else {
			Node temp = head.next;
			//清除节点的记忆
			temp.before = null;
			if (temp.next == null) {
				//只有一个节点
				//清除节点的记忆
				head.next = null;
			} else {
				//有多个节点
				Node next = temp.next;
				//清除节点的记忆
				next.before = head;
				head.next = next;
			}
			System.out.println(this);
			return temp;
		}
	}

	private Node getLast() {
		Node temp = head;
		while (temp.next != null) {
			temp = temp.next;
		}
		return temp;
	}
}

测试：入5出5