双向链表

基本定义

在计算机科学中，双向链表又被称为双链表，也属于链表，但是他每个节点都有两个指针，指向他前一个节点和后一个节点。我们学习单向链表的时候会发现，我们只能从前端遍历到尾端或者是尾端遍历到前端，因为单向链表正如其名：单向，所以说我们可以轻松的得到下一个节点，但是想回到上一个节点是很难的。但是双向链表就不一样的，他每个节点不单单保存着他下一个节点，还保存着他上一个节点，对于操作的方便程度是单向链表无法比拟的。当然，它占用的内存也会大一些

双向链表常见的方法

  1. append：向链表后端新增一个节点
  2. insert：在指定位置插入一个节点
  3. get：返回指定位置的节点
  4. indexOf：返回指定节点在链表的索引，找不到则返回-1
  5. update：修改某个位置的节点
  6. removeAt：移除指定位置的节点
  7. remove：移除链表后端的节点
  8. isEmpty：判断链表有没有节点，有则返回true，反之返回false
  9. size：返回链表的节点个数
  10. toString：输出链表的节点，因为实际上我们只需要节点的value，所以需要封装个方法打印出所有的value
  11. forwarrdString：从前端遍历到后端，打印出所有节点的value
  12. backwordString：从后端遍历到前端，打印出所有节点的value
  13. getHead：返回链表前端的节点
  14. getTail：返回链表后端的节点

在js中实现双向链表

前置工作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Node {
  constructor(data) {
    //当前节点的value
    this.data = data;
    //保存上一个节点信息
    this.prev = null;
    //保存下一个节点信息
    this.next = null;
  }
}

class DoubleList {
  constructor() {
    //头部节点
    this.head = null;
    //尾部节点
    this.tail = null;
    //链表长度
    this.length = 0;
  }
}

先封装个节点类和双向链表类，每一个节点我们都是实例化一个Node类保存到链表的。

以下所有方法都在DoubleList类中实现

实现append方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// append方法：在链表后端插入一个节点
append(data) {
  const node = new Node(data);
  //分情况处理：判断是否是第一个节点
  if (this.length === 0) {
    this.head = node;
    this.tail = node;
  } else {
    let current = this.head;
    while (current.next) {
      current = current.next;
    }
    node.prev = current;
    current.next = node;
    this.tail = node;
  }
  this.length++;
}

append方法比较简单，只是在处理节点的时候需要考虑到上一个节点的保存，别忘记在新增后需要将length加1

实现 insert方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
// insert方法：在指定位置插入元素
insert(position, data) {
  if (position < 0 || position > this.length) return false;

  const node = new Node(data);
  let current = this.head;
  // 先判断插入第一个元素的情况
  if (position == 0) {
    this.head = node;
    node.next = current;
    current.prev = node;
  } else if (position === this.length) {
    //判断插入的是最后一个节点的情况
    while (current.next) {
      current = current.next;
    }
    current.next = node;
    node.prev = current;
    this.tail = node;
  } else {
    //在中间的情况
    let index = 0;
    let prive = null;
    while (index < position) {
      prive = current;
      current = current.next;
      index++;
    }
    prive.next = node;
    node.prev = prive;
    current.prev = node;
    node.next = current;
  }
  this.length++;
  return true;
}

insert方法就比较麻烦，分的情况也比较多，首先需要考虑插入的是第一个节点的情况，先看图：

默认情况

我们可以看到默认情况双向链表的结构，head会指向第一个节点，tail会指向最后一个节点，然后每个节点有个next属性指向下一个节点，也有一个prev属性指向上一个节点

插入后的指针指向

我们会发现head指向value为4的节点，然后value为4的节点的next指向value为1的节点，然后节点value为1的节点的prev指向value为4的节点，也就是他上一个节点

当插入最后也是同理，value为3的节点的next属性指向value为4的节点，value为4的节点的prev属性指向value为3的节点，然后继续将tail指向最后一个节点，也就是value为4的节点。

实现get方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// get方法：获取指定位置的元素
get(position) {
  if (this.length / 2 > position) {
    let index = 0;
    let current = this.head;
    while (index < position) {
      current = current.next;
      index++;
    }
    return current.data;
  } else {
    let index = 0;
    let current = this.tail;
    while (index < this.length - position - 1) {
      current = current.prev;
      index++;
    }
    return current.data;
  }
}

get方法就比较简单，和单向链表相似，值得注意的是，如果我们链表中有大量数据，那么无论什么时候都从头找到尾明显不合适，所以可以判断一下需要找的元素的位置偏向前面还是偏向后面，决定我们从前开始找还是从后开始找，有点类似于二分查找，不过我们只分一次，这也是单向链表做不到的

实现indexOf方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// indexOf方法： 返回元素的索引，没有锗元素就返回-1
 indexOf(data) {
   let index = 0;
   let current = this.head;
   while (current) {
     if (current.data === data) {
       return index;
     } else {
       current = current.next;
       index++;
     }
   }
   return -1;
 }

实现update方法

1
2
3
4
5
6
7
8
9
10
11
12
13
// update方法： 更新方法
update(position, data) {
  if (position < 0 || position >= this.length) return false;

  let index = 0;
  let current = this.head;
  while (index < position) {
    current = current.next;
    index++;
  }
  current.data = data;
  return true;
}

实现removeAt方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// removeAt方法：移除特定位置的元素
 removeAt(position) {
   if (position < 0 || position >= this.length) return false;
   let index = 0;
   let current = this.head;
   let prive = null;
   if (this.length === 1) {
     this.head = null;
     this.tail = null;
     return true;
   }
//一样先判断在移除第一个节点的情况
   if (position === 0) {
     this.head = current.next;
     current.next.prev = this.head;
   } else if (position === this.length - 1) {
     //判断移除最后一个节点的情况
     this.tail.prev.next = null;
     this.tail = this.tail.prev;
   } else {
     //移除中间节点的情况
     while (index < position) {
       prive = current;
       current = current.next;
       index++;
     }
     prive.next = current.next;
     current.next.prev = prive;
     return true;
   }
   this.legnth--;
 }

removeAt方法稍微复杂一点点，大部分情况都是在考虑节点引用的问题，在移除最后一个节点的时候，也要注意移除顺序，如果我们选择现在将tail指向最后一个节点的上一个，那么我们找到倒数第二个节点的时候就找不到了，因为我们拿不到最后一个节点了，所以需要先将最后一个节点的上一个节点的next先置为空，然后在处理tail的指向。

实现remove方法

1
2
3
4
5
// remove方法：移除某个元素
 remove(data) {
   const index = this.indexOf(data);
   return this.removeAt(index);
 }

先调用indexOf方法找到移除元素的索引，然后调用removeAt方法将索引传递进去接口

实现isEmpty方法

1
2
3
4
// isEmpty方法： 判断链表是否为空，是则返回true，否则返回false
isEmpty() {
  return this.legnth > 0 ? true : false;
}

实现size方法

1
2
3
4
// size方法： 返回链表的长度
size() {
  return this.length;
}

实现getHead方法

1
2
3
4
// getHead方法： 返回列表前端元素
getHead() {
  return this.head.data;
}

实现getTail方法

1
2
3
4
// getTail方法： 返回列表后端元素
getTail() {
  return this.tail.data;
}