在上篇文章中，我们以及详细说过了链表，但是现实生活中我们不仅仅需要单项的链表，也就是单向的关系，我们可能需要双向的关系，那么我们就引出了我们下一个链表，双向链表
双向链表
双向链表与单向链表的区别在于，在单向链表中我们只有一个next指向他的下一个节点，但是在双向链表中多添加了一个元素pre，用来指向他的上一个节点。因此双向链表的具体构成应该为下图
双向链表的构成
同普通链表一样我们将上图进行拆分，我们可以很明确的得到一个双向链表应该有的数据结构，如下图：
双向链表数据结构拆分
我们先来实现这两个类
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，则需要将当前插入节点的pre指向一个undefined，将原有的head指向的节点的pre指向插入的节点
头部插入
第二种情况，从尾部插入，也就是将当前尾部元素的next指向我们插入的元素，我们插入的元素的next指向原有元素next指向的位置这点不变，增加当前插入元素的pre指向原有最后一个节点，同时tail指向插入的节点
尾部插入
第三种情况插入中间位置，那么也就是说假设我们将数据插入第二个位置，我们只需要将第一个位置节点的next指向插入的元素，插入的元素的next指向当前元素即可，和单向的一直，增加对pre处理，将第二个位置的pre指向插入的元素，插入元素的pre指向第二个节点前一个节点即可
中间插入
因此我们可以实现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，则需要将当前插入节点的pre指向一个undefined，将原有的head指向的节点的pre指向插入的节点，也就是
头部移除
第二种情况，从尾部移除，只需要将tail指向当前尾部的pre节点，同时将pre节点的next设置为undefined即可
尾部移除
第三种情况插入中间位置，只需要将插入位置的前面节点的next指向插入位置后面节点，同时将插入位置后面节点的pre指向插入位置前面节点即可
中间位置移除
因此移除的方法实现为
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;
}
}
至此，双向链表的说明结束了，当然链表远远不止这两种，下一章我们将说循环链表以及有序链表。
最后附上双向链表的全部实现
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;
}
}
}
网友评论