在上篇文章中廉丽，我們以及詳細說過了鏈表，但是現(xiàn)實生活中我們不僅僅需要單項的鏈表衷戈，也就是單向的關系呵曹，我們可能需要雙向的關系，那么我們就引出了我們下一個鏈表围苫，雙向鏈表
雙向鏈表
雙向鏈表與單向鏈表的區(qū)別在于，在單向鏈表中我們只有一個next指向他的下一個節(jié)點撤师，但是在雙向鏈表中多添加了一個元素pre剂府，用來指向他的上一個節(jié)點。因此雙向鏈表的具體構成應該為下圖
同普通鏈表一樣我們將上圖進行拆分剃盾，我們可以很明確的得到一個雙向鏈表應該有的數(shù)據(jù)結構腺占，如下圖：
我們先來實現(xiàn)這兩個類
Node類
import LinkNode from './LinkNode'
export default class DlinkNode extends LinkNode {
public pre: any;
constructor(node: any, next?: any, pre?: any) {
super(node);
this.pre = pre;
}
}
List類
import LinkList from './LinkList'
import DLinkNode from './DLinkNode'
export default class DLinklist extends LinkList {
public tail: any;
constructor(node?: any) {
super();
this.tail = undefined;
}
}
同普通鏈表一樣，實際上痒谴，雙向鏈表所需要的方法同普通的鏈表方法一樣衰伯。皆為下表方法
| 方法名 | 描述 |
|---|---|
| push(item) | 添加一個元素到鏈表中 |
| insert(item,index) | 添加一個元素到鏈表指定位置中 |
| getItemAt(index) | 獲取鏈表指定位置元素 |
| remove() | 移除最后一項 |
| clear() | 清除鏈表 |
| size() | 返回鏈表大小 |
| removeAt(index) | 移除指定位置元素并返回 |
| indexOf(item) | 獲取指定元素所在的位置 |
由于雙向鏈表與普通鏈表相比可以看到多了一個pre以及一個tail，所以我們對于增刪處理就需要相對于雙向鏈表多做一些處理积蔚，因此我們只需要修改insert以及removeAt方法即可
insert（item,index)
在指定位置插入元素嚎研。我們選擇插入元素，依舊是只有三個位置库倘，頭部临扮，尾部以及中間，這點和單項鏈表的方式是一樣教翩，
首先頭部插入杆勇，如果頭部插入元素的話，那么也就是當前head指向的為插入的元素饱亿，插入元素的next指向head以前指向的元素蚜退，這點和原有的一樣，但是對于pre彪笼，則需要將當前插入節(jié)點的pre指向一個undefined钻注，將原有的head指向的節(jié)點的pre指向插入的節(jié)點
第二種情況，從尾部插入配猫，也就是將當前尾部元素的next指向我們插入的元素幅恋，我們插入的元素的next指向原有元素next指向的位置這點不變，增加當前插入元素的pre指向原有最后一個節(jié)點泵肄，同時tail指向插入的節(jié)點
第三種情況插入中間位置捆交，那么也就是說假設我們將數(shù)據(jù)插入第二個位置，我們只需要將第一個位置節(jié)點的next指向插入的元素腐巢，插入的元素的next指向當前元素即可品追，和單向的一直，增加對pre處理冯丙，將第二個位置的pre指向插入的元素肉瓦，插入元素的pre指向第二個節(jié)點前一個節(jié)點即可
因此我們可以實現(xiàn)insert方法如下
public insert(item: any, index: number): boolean {
if (index >= 0 && index <= this.count) {
let node = new DLinkNode(item);
if (index === 0) {
if (this.head) {
node.next = this.head;
this.head = node;
this.head.pre = node;
} else {
this.head = node;
this.tail = node;
}
} else if (index >= this.count) {
let currentTail = this.getItemAt(this.count - 1);
this.tail = node;
node.pre = currentTail;
currentTail.next = node;
} else {
let currentNode = this.getItemAt(index);
let preNode = this.getItemAt(index - 1);
node.pre = preNode;
node.next = currentNode;
preNode.next = node;
currentNode.pre = node;
}
this.count++;
return true;
}
return false;
}
removeAt（index）
從任意位置移除元素，我們來分析分析，我們選擇插入元素泞莉，那么同移除有三個位置洁墙，頭部，尾部以及中間戒财，這點和單項鏈表的方式是一樣热监，
首先頭部插入，如果頭部移除元素的話饮寞，那么也就是當前head指向的為插入的元素孝扛，插入元素的next指向head以前指向的元素，這點和原有的一樣幽崩，但是對于pre苦始，則需要將當前插入節(jié)點的pre指向一個undefined，將原有的head指向的節(jié)點的pre指向插入的節(jié)點慌申，也就是
第二種情況陌选，從尾部移除，只需要將tail指向當前尾部的pre節(jié)點蹄溉，同時將pre節(jié)點的next設置為undefined即可
第三種情況插入中間位置咨油，只需要將插入位置的前面節(jié)點的next指向插入位置后面節(jié)點，同時將插入位置后面節(jié)點的pre指向插入位置前面節(jié)點即可
因此移除的方法實現(xiàn)為
public removeAt(index: number) {
if (index >= 0 && index < this.size()) {
let current = this.head;
if (index == 0) {
this.head = current.next;
if (this.size() === 1) {
this.tail = undefined;
} else {
this.head.next.pre = undefined;
}
} else if (index === this.size() - 1) {
current = this.tail;
this.tail = current.pre;
this.tail.next = undefined;
} else {
current = this.getItemAt(index);
let preNode = current.pre;
preNode.next = current.next;
current.next.pre = preNode;
}
this.count--;
return current.node;
} else {
return undefined;
}
}
至此柒爵，雙向鏈表的說明結束了役电，當然鏈表遠遠不止這兩種，下一章我們將說循環(huán)鏈表以及有序鏈表棉胀。
最后附上雙向鏈表的全部實現(xiàn)
import LinkList from './LinkList'
import DLinkNode from './DLinkNode'
export default class DLinklist extends LinkList {
public tail: any;
constructor(node?: any) {
super();
this.tail = undefined;
}
public insert(item: any, index: number): boolean {
if (index >= 0 && index <= this.count) {
let node = new DLinkNode(item);
if (index === 0) {
if (this.head) {
node.next = this.head;
this.head = node;
this.head.pre = node;
} else {
this.head = node;
this.tail = node;
}
} else if (index >= this.count) {
let currentTail = this.getItemAt(this.count - 1);
this.tail = node;
node.pre = currentTail;
currentTail.next = node;
} else {
let currentNode = this.getItemAt(index);
let preNode = this.getItemAt(index - 1);
node.pre = preNode;
node.next = currentNode;
preNode.next = node;
currentNode.pre = node;
}
this.count++;
return true;
}
return false;
}
public push(item: any) {
let node = new DLinkNode(item);
if (!this.head) {
this.head = node;
this.tail = node;
} else {
let currentTail = this.tail;
currentTail.next = node;
node.pre = currentTail;
this.tail = node;
}
this.count++;
}
public removeAt(index: number) {
if (index >= 0 && index < this.size()) {
let current = this.head;
if (index == 0) {
this.head = current.next;
if (this.size() === 1) {
this.tail = undefined;
} else {
this.head.next.pre = undefined;
}
} else if (index === this.size() - 1) {
current = this.tail;
this.tail = current.pre;
this.tail.next = undefined;
} else {
current = this.getItemAt(index);
let preNode = current.pre;
preNode.next = current.next;
current.next.pre = preNode;
}
this.count--;
return current.node;
} else {
return undefined;
}
}
}
