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，打印测试结果
上将 <== 列兵 ==> 上等兵 列兵 <== 上等兵 ==> 下士 上等兵 <== 下士 ==> 中士 下士 <== 中士 ==> 上士 中士 <== 上士 ==> 四级军士长 上士 <== 四级军士长 ==> 三级军士长 四级军士长 <== 三级军士长 ==> 二级军士长 三级军士长 <== 二级军士长 ==> 一级军士长 二级军士长 <== 一级军士长 ==> 少尉 一级军士长 <== 少尉 ==> 中尉 少尉 <== 中尉 ==> 中尉 中尉 <== 中尉 ==> 上尉 中尉 <== 上尉 ==> 少校 上尉 <== 少校 ==> 中校 少校 <== 中校 ==> 上校 中校 <== 上校 ==> 大校 上校 <== 大校 ==> 少将 大校 <== 少将 ==> 中将 少将 <== 中将 ==> 上将 中将 <== 上将 ==> 列兵 =============================================== 上将 <== 列兵 ==> 上等兵 列兵 <== 上等兵 ==> 下士 上等兵 <== 下士 ==> 中士 下士 <== 中士 ==> 上士 中士 <== 上士 ==> 四级军士长 上士 <== 四级军士长 ==> 三级军士长 四级军士长 <== 三级军士长 ==> 二级军士长 三级军士长 <== 二级军士长 ==> 一级军士长 二级军士长 <== 一级军士长 ==> 少尉 一级军士长 <== 少尉 ==> 中尉 少尉 <== 中尉 ==> 中尉 中尉 <== 中尉 ==> 上尉 中尉 <== 上尉 ==> 少校 上尉 <== 少校 ==> 中校 少校 <== 中校 ==> 上校 中校 <== 上校 ==> 大校 上校 <== 大校 ==> 少将 大校 <== 少将 ==> 中将 少将 <== 中将 ==> 上将 中将 <== 上将 ==> 列兵 =============================================== 上将 <== 列兵 ==> 上等兵 列兵 <== 上等兵 ==> 下士 上等兵 <== 下士 ==> 中士 下士 <== 中士 ==> 上士 中士 <== 上士 ==> 四级军士长 上士 <== 四级军士长 ==> 三级军士长 四级军士长 <== 三级军士长 ==> 二级军士长 三级军士长 <== 二级军士长 ==> 一级军士长 二级军士长 <== 一级军士长 ==> 少尉 一级军士长 <== 少尉 ==> 中尉 少尉 <== 中尉 ==> 中尉 中尉 <== 中尉 ==> 上尉 中尉 <== 上尉 ==> 少校 上尉 <== 少校 ==> 中校 少校 <== 中校 ==> 上校 中校 <== 上校 ==> 大校 上校 <== 大校 ==> 少将 大校 <== 少将 ==> 上将 少将 <== 上将 ==> 列兵