JavaScript实现双向链表过程解析
时间：2022-07-07 09:50:15 | 栏目：JavaScript代码 | 点击：次
一、什么是双向链表
我们知道单链表只能从头遍历到尾或从尾遍历到头（一般从头遍历到尾），即链表相连的过程是单向的，实现的原理是上一个链表中有一个指向下一个的引用。它有一个比较明显的缺点：
我们可以轻松的到达下一个节点，但是回到前一个节点是很困难的，但是，在实际开发中，经常会遇到需要回到上一个节点的情况，所以这里就需要双向链表。
所谓双向链表就是：既可以从头遍历到尾，又可以从尾遍历到头的链表，但是，双向链表也是有缺点的，比如：每次在插入或删除某个节点的时候，需要处理四个节点的引用，而不是两个，并且相对于单链表而言，占用内存会更大一些，但是这些缺点和我们使用起来的方便程度相比，是微不足道的。
我们就来看看双向链表的结构图。如下所示：
双向链表的特点：
- 可以使用一个head和一个tail分别指向头部和尾部的节点
- 每个节点由三部分组成，前一个节点的指针（prev）、保存的元素（data）、后一个节点的指针（next）
- 双向链表的第一个节点的prev是null
- 双向链表的最后的节点的next是null
我们可以将其抽象为：
知道了双向链表的结构，我们在一起来看看双向链表的封装。
二、双向链表的封装
首先，我们封装一个DoublyLinkedList类，用于表示链表结构，在这个类里面在封装一个内部类Node，用于封装每一个节点上的信息（指向前一个节点的引用、数据和指向下一个节点的引用），然后在Node类中保存三个属性，一个是链表的长度，一个是链表中的头结点，一个是链表的尾节点。如下所示：
function DoublyLinkedList(){
this.head = null;
this.tail = null;
this.length = 0;
function Node(data){
this.data = data;
this.prev = null;
this.next = null;
}
三、双向链表的常用操作
然后可以在里面添加双向链表常用的操作：
append（element:向列表尾部添加一个项
insert(position,element):向列表的特定位置插入一个项
get(position):获取对应位置的元素
indexOf(element):返回元素在列表中的索引，如果列表中没有该元素则返回-1
update(position，ele):修改某个位置的元素
removeAt(position):从列表的指定位置移除一项
remove(element):从列表中移除一项
isEmpty():如果链表中不包含任何元素，返回true,如果链表长度大于0返回false
size():返回链表包含的元素个数，与数组的length属性相关
toString():由于列表项用到了Node类，需要重写继承自JavaScript对象默认的toString方法，让其输出元素的值
forwardString():返回正向遍历的节点字符串形式
backwardString():返回反向遍历的节点字符串形式
接下来们就来一个一个实现。
1、append（element)方法-----向列表尾部添加一个项
这个方法和单链表的方法相似，先创建一个新列表，在判断链表是否为空，如果为空，则直接让链表的头部指向新建立的链表。如果不为空，则让新节点的前驱指针指向链表尾部，链表尾部的节点指向新链表。
Doubly.prototype.append = function(data){
var newNode = new Node(data);
if(this.length == 0){
this.head = newNode;
}else{
newNode.prev = this.tail;
this.tail.next = newNode;
}
this.tail = newNode;
this.length += 1;
}
2、将链表转化为字符串形式
1、toString():正向输出元素的值
这个方法主要是获取每一个元素，该方法默认获取链表的任何元素都必须从第一个节点开始，所以我们可以从头结点开始，循环遍历每一个节点，并且取出其中的element，拼接成字符串，并将字符串返回。具体方法为创建一个临时节点current，让这个临时节点指向双向链表的头部，然后通过next指针依次向后遍历，将每次遍历得到的数据进行拼接。
DoublyLinkedList.prototype.tostring = function(){
var current = this.head;
var str = '';
while(current){
str += current.data + ' ';
current = current.next;
}
return str;
}
2、forwardString():返回正向遍历的节点字符串形式
该方法也是实现双向链表的正向打印并输出，所以我们这里可以直接调用上一个方法：
DoublyLinkedList.prototype.forwardString = function(){
return this.toString()
}
3、backwardString():返回反向遍历的节点字符串形式
这个方法主要是从后往前遍历获取每一个元素并打印，所以我们可以从尾结点开始，循环遍历每一个节点，并且取出其中的element，拼接成字符串，并将字符串返回。具体方法为创建一个临时节点current，让这个临时节点指向双向链表的尾部，然后通过prev指针依次向前遍历，将每次遍历得到的数据进行拼接。
DoublyLinkedList.prototype.backwardString = function(){
var current = this.tail;
var str = '';
//依次向前遍历，获取每一个节点
while(current){
str += current.data +' ';
current = current.prev;
}
return str;
}
验证：
例如我们通过append()方法创建一个含有三个数据的双向链表，然后分别将他们正向拼接和反向拼接：
var list = new DoublyLinkedList();
list.append("a");
list.append("b");
list.append("c");
list.append("d");
console.log('toString()方法：'+list.toString());
console.log('forwardString()方法：'+list.forwardString());
console.log('backwardString()方法：'+list.backwardString());
打印结果为：
验证成功。
3、insert(position,element):向列表的特定位置插入一个项
这个方法相对来说是比较复杂的，首先，先判断要插入的位置是否越界，在不越界的情况下，在根据链表的情况判断，如果链表为空，则插入节点为第一个元素，直接让头结点和尾节点的指针指向新创建的节点；如果链表不为空，则插入的位置有三种情况：插入到首位，插入到末尾和插入到中间部位。具体操作如下：
DoublyLinkedList.prototype.insert = function(position,data){
var newNode = new Node(data);
//越界判断，如果不满足，返回false
if(position<0 || position>this.length){
return false;
}else{
//再次判断
//如果链表为空，直接插入
if(position==0){
this.head = newNode;
this.tail = newNode;
}else {
//如果链表不为空
//如果插入位置为末尾
if(position == this.length){
this.tail.next = newNode;
newNode.prev = this.tail;
this.tail = newNode;
}else if(position == 0){
//如果插入位置为首位
this.head.prev = newNode;
newNode.next = this.head;
this.head = newNode;
}else{
//如果插入位置为中间
var index = 0;
var current = this.head;
while(index++ <position){
current = current.next;
}
newNode.next = current;
newNode.prev = current.prev;
current.prev.next = newNode;
current.prev = newNode;
}
this.length += 1;
}
}
}
验证：如果在1位置插入xl,如下所示:
list.insert(1,'xl') console.log(list.toString());
运行结果为：
验证成功。
4、get(position):获取对应位置的元素
这个方法首先要判断位置是否越界，在不越界的情况下，定义一个临时节点和索引，让这个临时节点的指针指向头结点，遍历临时节点，同时索引自加，如果遍历道德节点的位置等于要获取元素的位置，则临时节点对应位置的元素就是要获得的元素。
DoublyLinkedList.prototype.get = function(position){
if(position<0 || position>=this.length){
return false;
}else{
var index = 0;
var current = this.head;
while(index++ <position){
current = current.next;
}
return current.data;
}
}
验证：查询position = 2的元素
console.log('list.get(2):'+list.get(2));
结果为：
验证成功。
但是，这种查找方式有一个弊端，即只能从前向后查找，在某些情况下效率就会很低，所以我们就可以两头查找，具体查找方式为：当我们要查找的节点的位置小于或等于链表长度的一半，我们就可以从前向后查找，如果要查找的节点的位置大于长度的一半，我们就从后往前查找。实现代码为：
DoublyLinkedList.prototype.get = function(position){
if(position<0 || position>=this.length){
return false;
}else{
var len = Math.floor(this.length/2);
if(position<=len){
var index = 0;
var current = this.head;
while(index++ <position){
current = current.next;
}
}else{
var index = this.length-1;
var current = this.tail;
while(index-->position){
current = current.prev;
}
}
return current.data;
}
}
5、indexOf(element):返回元素在列表中的索引
创建一个临时节点和索引，让临时节点指向头结点，依次向后遍历，同时让索引跟着递增，如果遍历的临时节点所得到的元素等于我们指定的元素，则此时的临时节点的位置就是我们目标位置，该位置的索引就是目标值的索引。
DoublyLinkedList.prototype.indexOf = function(data){
var current = this.head;
var index = 0;
while(current){
if(current.data === data){
return index;
}
current = current.next;
index ++;
}
return -1;
}
验证成功。
6、 update(position，ele):修改某个位置的元素
首先判断要修改的位置是否越界，在不越界的情况下，定义一个临时节点和索引，让临时节点指向头结点，索引位置为0，遍历临时节点并判断临时节点此时的索引和要修改元素的位置是否相等，如果相等的话，此时临时节点的位置就是要修改元素的位置，可以直接给临时节点的数据域更改元素。
DoublyLinkedList.prototype.update = function(position,newData){
if(position<0 || position>=this.length){
return false;
}else{
var index = 0;
var current = this.head;
while(index++ <position){
current = curent.next;
}
current.data = newData;
return true;
}
}
验证：将0位置的数据换成rc
list.update(0,'rc')
console.log("list.update(0,'rc')为:");
console.log(list.toString());
验证成功。
7、removeAt(position):从列表的指定位置移除一项
这个方法和insert()方法的思想相似，首先判断是否越界，在不越界的情况下，如果链表只有一个节点，则直接移除该项，让链表的头结点和尾节点均指向空。如果链表有多个节点的情况下，也分为三种情况，操作如下：
DoublyLinkedList.prototype.removeAt = function(position){
if(position<0 || position>=this.length){
return null;
}else{
var current = this.head;
if(this.length ===1){
//链表长度为1
this.head = null;
this.tail = null
}else{//链表长度不为1
if(position === 0){
//删除首位
this.head.next.prev = null;
this.head = this.head.next;
}else if(position === this.length-1){
this.tail.prev.next = null;
this.tail = this.tail.prev;
}else{
var index = 0;
while(index++ <position){
current = current.next;
}
current.prev.next = current.next;
current.next.pre = current.prev;
}
}
this.length -=1;
return current.data;
}
}
验证：删除位置3的数据：
list.removeAt(3)
console.log("list.removeAt(3)为:");
console.log(list.toString());
结果为：
验证成功
8、remove(element):从列表中移除一项
可以直接根据indexOf(element)方法获取元素在链表中的位置，在根据removeAt(position)方法将其删除。
DoublyLinkedList.prototype.remove = function(data){
var index = this.indexOf(data);
return this.removeAt(index);
}
验证：删除数据为rc的节点：
list.remove('rc');
console.log("list.remove('rc')为:");
console.log(list.toString());
9、isEmpty():判断链表是否为空
直接判断链表中元素的个数是否为零，如果为零则为空，返回true，否则不为空，返回false.
DoublyLinkedList.prototype.isEmpty = function(){
return this.length ==0;
}
验证：
console.log("链表是否为空："+list.isEmpty());
10、size():返回链表包含的元素个数
链表长度就是元素个数。
DoublyLinkedList.prototype.size = function(){
return this.length;
}
验证：
console.log("链表的元素个数为："+list.size());
