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，打印測試結果

?

上將 <== 列兵 ==> 上等兵
列兵 <== 上等兵 ==> 下士
上等兵 <== 下士 ==> 中士
下士 <== 中士 ==> 上士
中士 <== 上士 ==> 四級軍士長
上士 <== 四級軍士長 ==> 三級軍士長
四級軍士長 <== 三級軍士長 ==> 二級軍士長
三級軍士長 <== 二級軍士長 ==> 一級軍士長
二級軍士長 <== 一級軍士長 ==> 少尉
一級軍士長 <== 少尉 ==> 中尉
少尉 <== 中尉 ==> 中尉
中尉 <== 中尉 ==> 上尉
中尉 <== 上尉 ==> 少校
上尉 <== 少校 ==> 中校
少校 <== 中校 ==> 上校
中校 <== 上校 ==> 大校
上校 <== 大校 ==> 少將
大校 <== 少將 ==> 中將
少將 <== 中將 ==> 上將
中將 <== 上將 ==> 列兵
===============================================
上將 <== 列兵 ==> 上等兵
列兵 <== 上等兵 ==> 下士
上等兵 <== 下士 ==> 中士
下士 <== 中士 ==> 上士
中士 <== 上士 ==> 四級軍士長
上士 <== 四級軍士長 ==> 三級軍士長
四級軍士長 <== 三級軍士長 ==> 二級軍士長
三級軍士長 <== 二級軍士長 ==> 一級軍士長
二級軍士長 <== 一級軍士長 ==> 少尉
一級軍士長 <== 少尉 ==> 中尉
少尉 <== 中尉 ==> 中尉
中尉 <== 中尉 ==> 上尉
中尉 <== 上尉 ==> 少校
上尉 <== 少校 ==> 中校
少校 <== 中校 ==> 上校
中校 <== 上校 ==> 大校
上校 <== 大校 ==> 少將
大校 <== 少將 ==> 中將
少將 <== 中將 ==> 上將
中將 <== 上將 ==> 列兵
===============================================
上將 <== 列兵 ==> 上等兵
列兵 <== 上等兵 ==> 下士
上等兵 <== 下士 ==> 中士
下士 <== 中士 ==> 上士
中士 <== 上士 ==> 四級軍士長
上士 <== 四級軍士長 ==> 三級軍士長
四級軍士長 <== 三級軍士長 ==> 二級軍士長
三級軍士長 <== 二級軍士長 ==> 一級軍士長
二級軍士長 <== 一級軍士長 ==> 少尉
一級軍士長 <== 少尉 ==> 中尉
少尉 <== 中尉 ==> 中尉
中尉 <== 中尉 ==> 上尉
中尉 <== 上尉 ==> 少校
上尉 <== 少校 ==> 中校
少校 <== 中校 ==> 上校
中校 <== 上校 ==> 大校
上校 <== 大校 ==> 少將
大校 <== 少將 ==> 上將
少將 <== 上將 ==> 列兵

?

轉載于:https://www.cnblogs.com/pickKnow/p/9593069.html

總結

以上是生活随笔為你收集整理的链表 -- 双向循环链表(线性表）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。