數(shù)據(jù)結(jié)構(gòu)與算法--雙向鏈表
單向鏈表的指向是單向的，當(dāng)前結(jié)點(diǎn)只指向它的后一個(gè)結(jié)點(diǎn)。同樣，遍歷的時(shí)候也只有一個(gè)順序。如果需要訪問(wèn)前一個(gè)結(jié)點(diǎn)，即使是單向循環(huán)鏈表也需要循環(huán)size - 1次。有沒(méi)有辦法更方便的訪問(wèn)前面的結(jié)點(diǎn)呢？改變下Node的數(shù)據(jù)結(jié)構(gòu)就行了。
private class Node {
Item data;
Node prev;
Node next;
}
其中Item是泛型參數(shù)。現(xiàn)在每個(gè)結(jié)點(diǎn)都有兩個(gè)指向了，同時(shí)擁有了前后兩個(gè)結(jié)點(diǎn)的信息。由于我們實(shí)現(xiàn)的是非循環(huán)結(jié)構(gòu)的雙向鏈表，所以first的prev指向null，last的next指向null，這應(yīng)該是不言自明的。雖然每個(gè)結(jié)點(diǎn)有個(gè)兩個(gè)指針，但是很多操作中只用一個(gè)指針也夠了，所以單鏈表的很多方法可以直接拿過(guò)來(lái)使用。
上代碼。
package Chap3;
import java.util.Iterator;
public class DLinkedList<Item> implements Iterable<Item> {
private class Node {
Item data;
Node prev;
Node next;
}
// 指向第一個(gè)節(jié)點(diǎn)
private Node first;
// 指向最后一個(gè)節(jié)點(diǎn)
private Node last;
private int N;
public int size() {
return N;
}
public boolean isEmpty() {
return N == 0;
}
private Node index(int index) {
// [0, N-1]的定位范圍
if (index < 0 || index >= N) {
throw new IndexOutOfBoundsException(index + "");
}
// 索引在前半部分就正向查找, 在后半部分就反向查找
if (index < N / 2) {
Node current = first;
for (int j = 0; j < index; j++) {
current = current.next;
}
return current;
} else {
Node current = last;
for (int i = N - 1; i > index; i--) {
current = current.prev;
}
return current;
}
}
public Item get(int index) {
Node current = index(index);
return current.data;
}
public void set(int index, Item item) {
Node current = index(index);
current.data = item;
}
// 可以在表頭（index==0）和表尾插入
public void insert(int index, Item item) {
if (index == N) {
add(item);
} else {
// 因?yàn)橛衟rev，所以定位到當(dāng)前結(jié)點(diǎn)就好,如果使用index(index -1)當(dāng)index為0時(shí)報(bào)錯(cuò)
Node current = index(index);
Node pre = current.prev;
Node a = new Node();
a.data = item;
/* 由于多處使用到current即pre.next，所以最后才改變其值
1. 先確定新結(jié)點(diǎn)的兩頭
2. 更新 后結(jié)點(diǎn)的前驅(qū)
3. 更新 前結(jié)點(diǎn)的后繼
*/
a.prev = pre;
a.next = current;
current.prev = a;
// 如果是insert(0，item)則pre為null,沒(méi)有前結(jié)點(diǎn)，跳過(guò)步驟3
if (pre == null) {
first = a;
} else {
pre.next = a;
}
N++;
}
}
public Item remove(int index) {
/*
定位到當(dāng)前位置
1. 前一結(jié)點(diǎn)的后繼為下一結(jié)點(diǎn)
2. 下一結(jié)點(diǎn)的前驅(qū)為前一結(jié)點(diǎn)
*/
Node current = index(index);
Item item = current.data;
Node pre = current.prev;
Node next = current.next;
// 下面三行幫助垃圾回收
current.prev = null;
current.next = null;
current.data = null;
// 如果刪除的是第一個(gè)結(jié)點(diǎn)，則pre為null。沒(méi)有后繼，跳過(guò)
if (pre == null) {
first = next;
} else {
pre.next = next;
}
// 如果刪除的是最后一個(gè)結(jié)點(diǎn)，則next為null。沒(méi)有前驅(qū)，跳過(guò)
if (next == null) {
last = pre;
} else {
next.prev = pre;
}
N--;
return item;
}
// 表尾加入元素
public void add(Item item) {
Node oldlast = last;
last = new Node();
last.data = item;
// last應(yīng)該指向null，但是新的結(jié)點(diǎn)next默認(rèn)就是null
// 如果是第一個(gè)元素，則last和first指向同一個(gè)，即第一個(gè)
if (isEmpty()) {
first = last;
} else {
last.prev = oldlast;
oldlast.next = last;
}
N++;
}
// 表頭插入元素
public void push(Item item) {
Node oldfirst = first;
first = new Node();
first.data = item;
// 和add一樣，第一個(gè)元素加入時(shí)，last和first指向同一個(gè)結(jié)點(diǎn)
if (isEmpty()) {
last = first;
} else {
first.next = oldfirst;
oldfirst.prev = first;
}
N++;
}
// 刪除表頭元素
public Item pop() {
Item item = first.data;
Node next = first.next;
// 這兩行有助于垃圾回收
first.data = null;
first.next = null;
first = next;
N--;
// 最后一個(gè)元素被刪除，first自然為空了，但是last需要置空。
if (isEmpty()) {
last = null;
} else {
// next的引用給first，此時(shí)first的prev不為空。需要把表頭的前驅(qū)設(shè)為null（因?yàn)閒irst沒(méi)有前驅(qū)）
first.prev = null;
}
return item;
}
public void clear() {
while (first != null) {
Node next = first.next;
// 下面兩行幫助垃圾回收
first.next = null;
first.data = null;
first = next;
}
// 所有元素都空時(shí)，last也沒(méi)有有所指了。記得last置空
last = null;
N = 0;
}
public int indexOf(Item item) {
int index = 0;
if (item != null) {
for (Node cur = first; cur != null; cur = cur.next) {
if (item.equals(cur.data)) {
return index;
}
index++;
}
} else {
for (Node cur = first; cur != null; cur = cur.next) {
if (cur.data == null) {
return index;
}
index++;
}
}
return -1;
}
public boolean contains(Item item) {
return indexOf(item) >= 0;
}
@Override
public Iterator<Item> iterator() {
return new Iterator<Item>() {
private Node current = first;
@Override
public boolean hasNext() {
return current != null;
}
@Override
public Item next() {
Item item = current.data;
current = current.next;
return item;
}
};
}
public Iterable<Item> reversed() {
return new Iterable<Item>() {
@Override
public Iterator<Item> iterator() {
return new Iterator<Item>() {
Node cur = last;
@Override
public boolean hasNext() {
return cur != null;
}
@Override
public Item next() {
Item item = cur.data;
cur = cur.prev;
return item;
}
};
}
@Override
public String toString() {
Iterator<Item> it = iterator();
if (!it.hasNext()) {
return "[]";
}
StringBuilder sb = new StringBuilder();
sb.append("[");
while (true) {
Item item = it.next();
sb.append(item);
if (!it.hasNext()) {
return sb.append("]").toString();
}
sb.append(", ");
}
}
};
}
@Override
public String toString() {
Iterator<Item> it = iterator();
if (!it.hasNext()) {
return "[]";
}
StringBuilder sb = new StringBuilder();
sb.append("[");
while (true) {
Item item = it.next();
sb.append(item);
if (!it.hasNext()) {
return sb.append("]").toString();
}
sb.append(", ");
}
}
public static void main(String[] args) {
DLinkedList<Integer> a = new DLinkedList<>();
a.push(2);
a.push(1);
a.push(3);
a.set(2, 11);
System.out.println(a.get(2)); // 11
System.out.println(a);
a.insert(0, 444);
a.clear();
a.add(11);
a.add(12);
a.add(13);
a.push(14);
a.remove(2); // 12
a.pop(); // 14
System.out.println(a.indexOf(13)); // 1
System.out.println(a.reversed());
for (Integer aa : a.reversed()) {
System.out.println(aa);
}
}
}
考慮到效率問(wèn)題，在定位函數(shù)Node index(int index)中使用了prev指針。可以看到，當(dāng)索引位置在鏈表的前半部分時(shí)，使用next指針正向查找。當(dāng)索引位置在鏈表的后半部分時(shí)，使用prev指針?lè)聪虿檎?。這能減少循環(huán)次數(shù)，提高效率。
再看push方法，與單鏈表的方法相比多了一句oldfirst.prev = first，讓原first結(jié)點(diǎn)的前驅(qū)指向新的first結(jié)點(diǎn)。
pop方法多了一個(gè)判斷分支，當(dāng)被彈出的時(shí)最后一個(gè)結(jié)點(diǎn)時(shí)，即first被彈出時(shí)，由于first.prev和first.next都已經(jīng)是null了，所以只需將last置為null；但是如果被彈出的不是最后一個(gè)結(jié)點(diǎn)呢？next結(jié)點(diǎn)攜帶著prev的信息，所以在 first = next之后，first的prev并不為null。所以需要手動(dòng)令first.prev = null。
add方法，也只是多了一句last.prev = oldlast;，目的是讓新的last的前驅(qū)指向舊的last結(jié)點(diǎn)。
以上三個(gè)方法，看圖:
再看關(guān)鍵的insert方法，在單鏈表的實(shí)現(xiàn)中，需要定位到插入結(jié)點(diǎn)的前一個(gè)位置，即index - 1處。由于沒(méi)有使用頭結(jié)點(diǎn)，所以在insert(0, item)處，由于不能定位到index為-1的位置，操作方法有所不同（直接使用push方法）。在雙向鏈表中，如果使用單鏈表的方法，在表尾a[N]處插入時(shí)，會(huì)定位到last，那么current.next為null，調(diào)用current.next.prev將引發(fā)空指針異常。除非再單獨(dú)開(kāi)一個(gè)條件當(dāng)在a[N]處插入時(shí)調(diào)用add方法插到末尾。這樣代碼顯得很臃腫。
雙向鏈表有個(gè)prev指針，好好利用起來(lái)，在定位的時(shí)候不必定位到index - 1處了，直接定位到index處可以省去一些麻煩?？?code>insert中這兩句
if (index == N) {
add(item);
}
這兩句代碼很機(jī)智，在插入第一個(gè)結(jié)點(diǎn)時(shí)若使用insert(0, item)，會(huì)直接調(diào)用add方法，以后在末尾插入時(shí)候，依然調(diào)用add方法。如果按照單鏈表insert的思路來(lái)實(shí)現(xiàn)雙鏈表的insert方法，需要分index == 0，index == N等情況。由于可以直接定位到index位置，定位的范圍是[0, N]，index==N的情況采用上面兩行的方法處理。當(dāng)index == 0時(shí)else分支也能正確處理。整個(gè)insert其實(shí)只使用了插入點(diǎn)處的結(jié)點(diǎn)current和它前一個(gè)結(jié)點(diǎn)current.prev。
再看，賦值語(yǔ)句順序不能搞錯(cuò)。
Node pre = current.prev;
Node a = new Node();
a.data = item;
a.prev = pre;
a.next = current;
current.prev = a;
if (pre == null) {
first = a;
} else {
pre.next = a;
}
由于多處使用到current即pre.next，所以最后才改變其值，不然先改變了，后面使用時(shí)指向的對(duì)象已經(jīng)變了。這會(huì)導(dǎo)致操作失敗。記住下面的操作順序，一般就不會(huì)出錯(cuò)了。
1. 先確定新結(jié)點(diǎn)的兩頭
2. 更新 后結(jié)點(diǎn)的前驅(qū)
3. 更新 前結(jié)點(diǎn)的后繼
如果是insert(0, item)，相當(dāng)于push操作，此時(shí)pre為null，無(wú)法調(diào)用pre.next，跳過(guò)步驟3。想想push的原理，其實(shí)就是讓插入的結(jié)點(diǎn)成為新的first。
remove方法，也是定位到刪除位置，范圍是[0, N - 1]。使用到了移除處的結(jié)點(diǎn)current，它前一個(gè)結(jié)點(diǎn)current.prev以及它后一個(gè)結(jié)點(diǎn)current.next。先用一個(gè)臨時(shí)變量保存后兩者。然后清空移除處結(jié)點(diǎn)的信息，幫助垃圾回收。
移除需要分三種情況：
- 移除除first和last之外的其他結(jié)點(diǎn)
記住下面的操作
- 前一結(jié)點(diǎn)的next指向下一結(jié)點(diǎn)
- 下一結(jié)點(diǎn)的prev指向前一結(jié)點(diǎn)
用代碼表示就是
pre.next = next;
next.prev = pre;
- 移除first結(jié)點(diǎn)
- 讓下一結(jié)點(diǎn)成為新的first
- 下一結(jié)點(diǎn)（已經(jīng)成為first）的prev置為null（pre此時(shí)為null）
代碼表示為
// pre == null
first = next;
next.prev = pre;
- 移除last結(jié)點(diǎn)
- 前一個(gè)結(jié)點(diǎn)（即將稱(chēng)為新的last）的next先指向null（next此時(shí)為null）
- 讓這個(gè)結(jié)點(diǎn)成為新的last
代碼表示就是
pre.next = next;
last = pre;
其余方法如indexOf、contains、clear、iterator都直接使用單鏈表的實(shí)現(xiàn)就行。由于雙向鏈表可以訪問(wèn)前面的結(jié)點(diǎn)，所以新增了一個(gè)reversed方法，返回一個(gè)逆序的可迭代對(duì)象，即返回一個(gè)Iterable<Item>，為此需要實(shí)現(xiàn)iterator方法。
new Iterator<Item>() {
Node cur = last;
@Override
public boolean hasNext() {
return cur != null;
}
@Override
public Item next() {
Item item = cur.data;
cur = cur.prev;
return item;
}
};
將當(dāng)前指針移動(dòng)到last結(jié)點(diǎn)位置，然后通過(guò)cur = cur.prev遍歷。其實(shí)就是將單鏈表iterator實(shí)現(xiàn)中的first改成了last，cur.next改成了prev。
by @sunhaiyu
2017.8.2
