1，双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。
2,构建节点类
public class DNode<E> {Object item;DNode<E> prev;DNode<E> next;public DNode(){}public DNode(DNode<E> prev,Object item,DNode<E> next){this.item = item;this.prev = null;this.next = null;} }
3，构建链表类，以增加节点和删除节点为例
public class DLink<E> {int size;DNode<E> first;DNode<E> last;public DLink() {this.size = 0;this.first = null;this.last = null;}public boolean isEmpty() {return first == null;}public void addNode(Object o) {final DNode<E> l = last;final DNode<E> f = first;DNode<E> newNode = new DNode<E>(l, o, null);last = newNode;if (l == null) {first = newNode;first.next = newNode;last.prev = newNode;first.prev = newNode;} else {l.next = newNode;f.prev = newNode;newNode.prev = l;newNode.next = f;}size++;}public boolean removeNode(Object o) {if (o == null) { for (DNode<E> x = first; x.next != first; x = x.next) {if (x.item == null) {unlink(x);return true;}}if (last.item == null) {unlink(last);return true;}} else {for (DNode<E> x = first; x.next != first; x = x.next) {if (x.item.equals(o)) {unlink(x);return true;}if (last.item.equals(o)) {unlink(last);return true;}}}return false;}private void unlink(DNode<E> e) {final DNode<E> c = e;final DNode<E> next = c.next;final DNode<E> prev = c.prev;final DNode<E> f = first;final DNode<E> l = last;if (c == first) {first = f.next;first.prev = l;l.next = first;return;}if (c == last) {last = l.prev;last.next = first;first.prev = last;return;}prev.next = next;next.prev = prev;size--;}public void display() {for (DNode<E> x = first; x.next != first; x = x.next) {System.out.println(x.prev.item + " <== " + x.item + " ==> " + x.next.item);}System.out.println(last.prev.item + " <== " + last.item + " ==> " + last.next.item);}// DNode<E> x = first;// for (int i = 1; i <= DLink.size; i++) {// System.out.println(x.prev.item + " <== " + x.item + " ==> " +// x.next.item);// x = x.next;// }// } }
4，构建测试类
public class DTest {public static void main(String[] args) {DLink dlink = new DLink();dlink.addNode("列兵");dlink.addNode("上等兵");dlink.addNode("下士");dlink.addNode("中士");dlink.addNode("上士");dlink.addNode("四级军士长");dlink.addNode("三级军士长");dlink.addNode("二级军士长");;dlink.addNode("一级军士长");dlink.addNode("少尉");dlink.addNode("中尉");dlink.addNode("中尉");dlink.addNode("上尉");dlink.addNode("少校");dlink.addNode("中校");dlink.addNode("上校");dlink.addNode("大校");dlink.addNode("少将");dlink.addNode("中将");dlink.addNode("上将");dlink.display();System.out.println("===============================================");dlink.removeNode(null);dlink.display();System.out.println("===============================================");// dlink.removeNode("列兵");// dlink.removeNode("上将");dlink.removeNode("中将");dlink.display();} }
5，打印测试结果
上将 <== 列兵 ==> 上等兵 列兵 <== 上等兵 ==> 下士 上等兵 <== 下士 ==> 中士 下士 <== 中士 ==> 上士 中士 <== 上士 ==> 四级军士长 上士 <== 四级军士长 ==> 三级军士长 四级军士长 <== 三级军士长 ==> 二级军士长 三级军士长 <== 二级军士长 ==> 一级军士长 二级军士长 <== 一级军士长 ==> 少尉 一级军士长 <== 少尉 ==> 中尉 少尉 <== 中尉 ==> 中尉 中尉 <== 中尉 ==> 上尉 中尉 <== 上尉 ==> 少校 上尉 <== 少校 ==> 中校 少校 <== 中校 ==> 上校 中校 <== 上校 ==> 大校 上校 <== 大校 ==> 少将 大校 <== 少将 ==> 中将 少将 <== 中将 ==> 上将 中将 <== 上将 ==> 列兵 =============================================== 上将 <== 列兵 ==> 上等兵 列兵 <== 上等兵 ==> 下士 上等兵 <== 下士 ==> 中士 下士 <== 中士 ==> 上士 中士 <== 上士 ==> 四级军士长 上士 <== 四级军士长 ==> 三级军士长 四级军士长 <== 三级军士长 ==> 二级军士长 三级军士长 <== 二级军士长 ==> 一级军士长 二级军士长 <== 一级军士长 ==> 少尉 一级军士长 <== 少尉 ==> 中尉 少尉 <== 中尉 ==> 中尉 中尉 <== 中尉 ==> 上尉 中尉 <== 上尉 ==> 少校 上尉 <== 少校 ==> 中校 少校 <== 中校 ==> 上校 中校 <== 上校 ==> 大校 上校 <== 大校 ==> 少将 大校 <== 少将 ==> 中将 少将 <== 中将 ==> 上将 中将 <== 上将 ==> 列兵 =============================================== 上将 <== 列兵 ==> 上等兵 列兵 <== 上等兵 ==> 下士 上等兵 <== 下士 ==> 中士 下士 <== 中士 ==> 上士 中士 <== 上士 ==> 四级军士长 上士 <== 四级军士长 ==> 三级军士长 四级军士长 <== 三级军士长 ==> 二级军士长 三级军士长 <== 二级军士长 ==> 一级军士长 二级军士长 <== 一级军士长 ==> 少尉 一级军士长 <== 少尉 ==> 中尉 少尉 <== 中尉 ==> 中尉 中尉 <== 中尉 ==> 上尉 中尉 <== 上尉 ==> 少校 上尉 <== 少校 ==> 中校 少校 <== 中校 ==> 上校 中校 <== 上校 ==> 大校 上校 <== 大校 ==> 少将 大校 <== 少将 ==> 上将 少将 <== 上将 ==> 列兵
