一、雙向鏈表的結構。(1)、首先節點的結構，其中包含本節點內容，同時需要知道前面是誰后面是誰。 Java代碼 private static class Entry<E> { //元素 E e; //后一個節點 Entry<E> nextEntry; //前一個節點 Entry<E> previousEntry; public Entry(E e, Entry<E> previousEntry, Entry<E> nextEntry) { this.e = e; this.nextEntry = nextEntry; this.previousEntry = previousEntry; } } private static class Entry<E> {//元素E e;//后一個節點Entry<E> nextEntry;//前一個節點Entry<E> previousEntry;public Entry(E e, Entry<E> previousEntry, Entry<E> nextEntry) {this.e = e;this.nextEntry = nextEntry;this.previousEntry = previousEntry;}} 其中e則指向本節點的元素，而nextEntry則指向下一個節點，previousEntry則指向前一個節點。 (2)、需要定義一個節點，其同時知道表頭，同時知道表尾，這里就暫時定義為head。Java代碼 private transient Entry<E> head = new Entry<E>(null, null, null); public DoubleChain() { head.nextEntry = head.previousEntry = head; } private transient Entry<E> head = new Entry<E>(null, null, null);public DoubleChain() {head.nextEntry = head.previousEntry = head;} 可以看出，在初始化方法中，直接將表頭和表尾直接都指向head。這樣在head的基礎上不管怎么增加元素都逃脫不了與head關系。牢記head.nextEntry表頭，head.previousEntry表尾。(3)、同樣記錄節點的個數只是為了提高效率，不是必要。Java代碼 private int size; public int size() { return this.size; } private int size;public int size() {return this.size;} Java代碼 好了有這三樣，就足夠了。就看我們如何用他們了。二、內部實現。(1)、方法addBefore。由于一開始就初始化了head，有了head作為基準，玩轉整個鏈表也就靠這個方法了。Java代碼 private void addBefore(E e, Entry<E> entry) { //新節點的初始化，指定新節點的前一個節點和后一個節點 Entry<E> newEntry = new Entry<E>(e, entry.previousEntry, entry); //告知新節點的前一個節點其后面是新節點 newEntry.previousEntry.nextEntry = newEntry; //告知新節點的后一個節點其前節點是新節點 newEntry.nextEntry.previousEntry = newEntry; size++; } private void addBefore(E e, Entry<E> entry) {//新節點的初始化，指定新節點的前一個節點和后一個節點Entry<E> newEntry = new Entry<E>(e, entry.previousEntry, entry);//告知新節點的前一個節點其后面是新節點newEntry.previousEntry.nextEntry = newEntry;//告知新節點的后一個節點其前節點是新節點newEntry.nextEntry.previousEntry = newEntry;size++;} 可以看出，通過指定的元素創建一個新的節點。然后將其前前后后的關系都打通就好了。(2)、表頭插入。再簡單不過了，直接在head.nextEntry前增加就好了，直接調用addBefore。效率高 Java代碼 public void addHead(E e) { this.addBefore(e, head.nextEntry); } public void addHead(E e) {this.addBefore(e, head.nextEntry);} (3)、尾插入。同樣簡單，直接在head.previous前增加就好了，同樣調用addBefore。效率高 Java代碼 public void add(E e) { this.addBefore(e, head); } public void add(E e) {this.addBefore(e, head);} (4)、指定節點插入（插隊）。同樣需要插隊，但是由于其節點的雙向性，則不需要進行特殊處理，直接循環找出指定的節點元素就好了。效率低 Java代碼 public void addSpecifyIndex(E e, int index) { int count = 0; for (Entry<E> p = head.nextEntry; p != head; p = p.nextEntry) { if (count == index) { this.addBefore(e, p); return; } count++; } } public void addSpecifyIndex(E e, int index) {int count = 0;for (Entry<E> p = head.nextEntry; p != head; p = p.nextEntry) {if (count == index) {this.addBefore(e, p);return;}count++;}} (5)、指定節點獲取元素。同樣循環找出。效率低 Java代碼 public E get(int index) { int count = 0; E result = null; for (Entry<E> p = head.nextEntry; p != head; p = p.nextEntry) { if (count == index) { result = p.e; } count++; } return result; } public E get(int index) {int count = 0;E result = null;for (Entry<E> p = head.nextEntry; p != head; p = p.nextEntry) {if (count == index) {result = p.e;}count++;}return result;} (6)、指定節點刪除。同理，找到要刪除的節點，讓指定節點的前后直接相通就OK了。效率低Java代碼 public void remove(int index) { int count = 0; for (Entry<E> p = head.nextEntry; p != head; p = p.nextEntry) { if (count == index) { p.previousEntry.nextEntry= p.nextEntry; p.nextEntry.previousEntry=p.previousEntry; size--; return; } count++; } } public void remove(int index) {int count = 0;for (Entry<E> p = head.nextEntry; p != head; p = p.nextEntry) {if (count == index) {p.previousEntry.nextEntry= p.nextEntry;p.nextEntry.previousEntry=p.previousEntry;size--;return;}count++;}} (7)、循環。為了好進行遍歷演示，下面的就是循環遍歷所用的了，大家隨意看一下就好了。Java代碼 private Entry<E> current; public boolean hasNext() { return current != head; } public E next() { E result = current.e; current = current.nextEntry; return result; } public void setCursor(int index) { int count = 0; for (Entry<E> p = head.nextEntry; p != head; p = p.nextEntry) { if (count == index) { current = p; } count++; } private Entry<E> current;public boolean hasNext() {return current != head;}public E next() {E result = current.e;current = current.nextEntry;return result;}public void setCursor(int index) {int count = 0;for (Entry<E> p = head.nextEntry; p != head; p = p.nextEntry) {if (count == index) {current = p;}count++;} 三、測試。。一個main方法，測試一下。Java代碼 public static void main(String[] args) { DoubleChain<String> doubleChain = new DoubleChain<String>(); for (int i = 0; i < 4; i++) { doubleChain.add(i + ""); } // 頭插入 // doubleChain.addHead("head"); // // 尾插入 // doubleChain.add("tail"); // // 指定節點插入 // doubleChain.addSpecifyIndex("Specify", 1); // // 指定節點刪除 // doubleChain.remove(3); // // 設置循環的初始節點 // doubleChain.setCursor(0); int count = 0; System.out.println("######SIZE" + doubleChain.size() + "#######"); while (doubleChain.hasNext()) { System.out.println("index:" + count + ",entry:" + doubleChain.next()); count++; } System.out.println(doubleChain.get(doubleChain.size() - 2)); } public static void main(String[] args) {DoubleChain<String> doubleChain = new DoubleChain<String>();for (int i = 0; i < 4; i++) {doubleChain.add(i + "");}// 頭插入 // doubleChain.addHead("head"); // // 尾插入 // doubleChain.add("tail"); // // 指定節點插入 // doubleChain.addSpecifyIndex("Specify", 1); // // 指定節點刪除 // doubleChain.remove(3); // // 設置循環的初始節點 // doubleChain.setCursor(0);int count = 0;System.out.println("######SIZE" + doubleChain.size() + "#######");while (doubleChain.hasNext()) {System.out.println("index:" + count + ",entry:"+ doubleChain.next());count++;}System.out.println(doubleChain.get(doubleChain.size() - 2));} 四、總結。。可以看出，從結構上講，雙向鏈表和單項鏈表最大的區別在于每個節點都是雙向的。從效率上講，提高了尾插入的效率，但是對于插隊同樣效率不高。如果需要反復進行插隊操作的同學注意了，LinkedList的效率會很低的哦。五、全部代碼。。Java代碼 package paladin.chain; public class DoubleChain<E> implements Chain<E> { private transient Entry<E> head = new Entry<E>(null, null, null); private Entry<E> current; private int size; public DoubleChain() { head.nextEntry = head.previousEntry = head; } private void addBefore(E e, Entry<E> entry) { //新節點的初始化，指定新節點的前一個節點和后一個節點 Entry<E> newEntry = new Entry<E>(e, entry.previousEntry, entry); //告知新節點的前一個節點其后面是新節點 newEntry.previousEntry.nextEntry = newEntry; //告知新節點的后一個節點其前節點是新節點 newEntry.nextEntry.previousEntry = newEntry; size++; } public void add(E e) { this.addBefore(e, head); } public void addHead(E e) { this.addBefore(e, head.nextEntry); } public void addSpecifyIndex(E e, int index) { int count = 0; for (Entry<E> p = head.nextEntry; p != head; p = p.nextEntry) { if (count == index) { this.addBefore(e, p); return; } count++; } } public void remove(int index) { int count = 0; for (Entry<E> p = head.nextEntry; p != head; p = p.nextEntry) { if (count == index) { p.previousEntry.nextEntry= p.nextEntry; p.nextEntry.previousEntry=p.previousEntry; size--; return; } count++; } } public E get(int index) { int count = 0; E result = null; for (Entry<E> p = head.nextEntry; p != head; p = p.nextEntry) { if (count == index) { result = p.e; } count++; } return result; } public boolean hasNext() { return current != head; } public E next() { E result = current.e; current = current.nextEntry; return result; } public void setCursor(int index) { int count = 0; for (Entry<E> p = head.nextEntry; p != head; p = p.nextEntry) { if (count == index) { current = p; } count++; } } public int size() { return this.size; } private static class Entry<E> { //元素 E e; //后一個節點 Entry<E> nextEntry; //前一個節點 Entry<E> previousEntry; public Entry(E e, Entry<E> previousEntry, Entry<E> nextEntry) { this.e = e; this.nextEntry = nextEntry; this.previousEntry = previousEntry; } } public static void main(String[] args) { DoubleChain<String> doubleChain = new DoubleChain<String>(); for (int i = 0; i < 4; i++) { doubleChain.add(i + ""); } // 頭插入 // doubleChain.addHead("head"); // // 尾插入 // doubleChain.add("tail"); // // 指定節點插入 // doubleChain.addSpecifyIndex("Specify", 1); // // 指定節點刪除 // doubleChain.remove(3); // // 設置循環的初始節點 // doubleChain.setCursor(0); int count = 0; System.out.println("######SIZE" + doubleChain.size() + "#######"); while (doubleChain.hasNext()) { System.out.println("index:" + count + ",entry:" + doubleChain.next()); count++; } System.out.println(doubleChain.get(doubleChain.size() - 2)); } } package paladin.chain;public class DoubleChain<E> implements Chain<E> {private transient Entry<E> head = new Entry<E>(null, null, null);private Entry<E> current;private int size;public DoubleChain() {head.nextEntry = head.previousEntry = head;}private void addBefore(E e, Entry<E> entry) {//新節點的初始化，指定新節點的前一個節點和后一個節點Entry<E> newEntry = new Entry<E>(e, entry.previousEntry, entry);//告知新節點的前一個節點其后面是新節點newEntry.previousEntry.nextEntry = newEntry;//告知新節點的后一個節點其前節點是新節點newEntry.nextEntry.previousEntry = newEntry;size++;}public void add(E e) {this.addBefore(e, head);}public void addHead(E e) {this.addBefore(e, head.nextEntry);}public void addSpecifyIndex(E e, int index) {int count = 0;for (Entry<E> p = head.nextEntry; p != head; p = p.nextEntry) {if (count == index) {this.addBefore(e, p);return;}count++;}}public void remove(int index) {int count = 0;for (Entry<E> p = head.nextEntry; p != head; p = p.nextEntry) {if (count == index) {p.previousEntry.nextEntry= p.nextEntry;p.nextEntry.previousEntry=p.previousEntry;size--;return;}count++;}}public E get(int index) {int count = 0;E result = null;for (Entry<E> p = head.nextEntry; p != head; p = p.nextEntry) {if (count == index) {result = p.e;}count++;}return result;}public boolean hasNext() {return current != head;}public E next() {E result = current.e;current = current.nextEntry;return result;}public void setCursor(int index) {int count = 0;for (Entry<E> p = head.nextEntry; p != head; p = p.nextEntry) {if (count == index) {current = p;}count++;}}public int size() {return this.size;}private static class Entry<E> {//元素E e;//后一個節點Entry<E> nextEntry;//前一個節點Entry<E> previousEntry;public Entry(E e, Entry<E> previousEntry, Entry<E> nextEntry) {this.e = e;this.nextEntry = nextEntry;this.previousEntry = previousEntry;}}public static void main(String[] args) {DoubleChain<String> doubleChain = new DoubleChain<String>();for (int i = 0; i < 4; i++) {doubleChain.add(i + "");}// 頭插入 // doubleChain.addHead("head"); // // 尾插入 // doubleChain.add("tail"); // // 指定節點插入 // doubleChain.addSpecifyIndex("Specify", 1); // // 指定節點刪除 // doubleChain.remove(3); // // 設置循環的初始節點 // doubleChain.setCursor(0);int count = 0;System.out.println("######SIZE" + doubleChain.size() + "#######");while (doubleChain.hasNext()) {System.out.println("index:" + count + ",entry:"+ doubleChain.next());count++;}System.out.println(doubleChain.get(doubleChain.size() - 2));}}

總結

以上是生活随笔為你收集整理的Java实现双向链表的全部內容，希望文章能夠幫你解決所遇到的問題。

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