代码视界

Hanpeng Chen的个人博客

JavaScript中的数据结构—链表

算法 数据结构 链表 2021/01/17

本文于 1166 天之前发表，文中内容可能已经过时。

前言

数据结构与算法在前端开发工程师的日常工作中也许不常用，但在这对前端工程师要求日益提高的时代，如果对数据结构、算法思维、代码效率等知识拥有足够的储备，那么我们将拥有更强的竞争力。

话不多说，我们接下来学习一种数据结构：链表(Linked list)。

链表

数组对于每个开发来说是非常熟悉的一种数据结构。链表是一种比数组稍微复杂一点的数据结构，掌握起来也比数组稍难一些。

链表是一种与数组类似的线性数据结构，但与数组的元素存储在特定的内存位置或索引中不同，链表的每个元素都是独立的对象，它包含一个指向该列表中下一个对象的指针或链接。

链表的每个元素（我们通常称为节点）包含两项：

  • 存储的数据：数据可以是任何有效的数据类型。
  • 指针：到下一节点的链接

链表的结构可以由很多种，它可以是单链表或双链表，也可以是已排序的或未排序的，环形的或非环形的。如果一个链表是单向的，那么链表中的每个元素没有指向前一个元素的指针。已排序的和未排序的链表较好理解。常见的有：单向链表、双向链表、单向循环链表和双向循环链表。

从上图我们可以看出，循环链表和单链表的区别在于：单链表的尾元素指向的Null，而循环链表的尾元素指向的是链表的头部元素。

欢迎关注我的微信公众号：前端极客技术(FrontGeek)

单向链表

链表和数组一样，也支持数据的查找、插入和删除。

由于链表是非连续的，想要访问第i个元素就不像数组那么方便，而是需要根据指针一个节点一个节点一次遍历，直到找到相应的节点。

因为链表的数据本身是非连续的空间，所以它的插入或删除操作，不需要像数组那边挪动原来的数据，因此在链表中插入数据、删除数据是非常快的。

设计链表

我们设计链表包含两个类：一个是Node类用来表示节点；另一个是LinkedList类提供插入节点、删除节点等操作。

头结点head的next初始化为null，每当调用插入方法时，next就会指向新的元素

  • Node

    1
    2
    3
    4
    5
    6
    class Node {
      constructor(el) {
        this.el = el;
        this.next = null;
      }
    }

  • LinkedList

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    class LinkedList {
      constructor(){
        this.head = new Node('head')
      }

      // 用于查找
      find(){}

      // 插入节点
      insert(){}

      // 删除节点
      remove(){}
    }

查找

从头结点开始查找，如果没找到就把当前指针往后移，找到就返回该元素，如果遍历完没找到就直接返回null。

代码实现如下：

1
2
3
4
5
6
7
find(item){
  let currentNode = this.head
  while (currentNode !== null && currentNode.el !== item) {
    currentNode = currentNode.next;
  }
  return currentNode
}

插入新节点

要往链表中插入新节点，需要知道在哪个节点后面插入。那么我们就需要知道在哪里插入和插入的元素是什么。

知道在哪个节点后面插入后，首先我们要先找到这个节点的位置，这里我们就可以用上面实现的查找方法。

找到节点后，我们先创建一个新节点，把新节点的next指针指向找到的这个节点next指向的对应节点，再把找到的这个节点的next指针指向新节点，数据的插入就完成了。具体过程如下图所示：

代码实现如下：

1
2
3
4
5
6
7
8
9
// 插入节点
  // el:要插入的数据
  // item：数据插入到这个节点后面
  insert(el, item){
    const newNode = new Node(el)
    const cur = this.find(item)
    newNode.next = cur.next
    cur.next = newNode
  }

删除节点

删除节点和插入节点类似，首先要找到相应节点的前一个节点，找到后，让它的next指向待删除节点的下一个节点。如下图所示：

代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
findPre(item) {
  let cur = this.head
  while (cur.next !== null && cur.next.el !== item) {
    cur = cur.next
  }
  return cur
}

// 删除节点
remove(item){
  const preNode = this.findPre(item)
  if (preNode.next !== null) {
    preNode.next = preNode.next.next
  }
}

单向链表完整代码：

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
// 单项链表

// 节点
class Node {
  constructor(el) {
    this.el = el;
    this.next = null;
  }
}

class LinkedList {
  constructor(){
    this.head = new Node('head')
  }

  // 用于查找
  find(item){
    let currentNode = this.head
    while (currentNode !== null && currentNode.el !== item) {
      currentNode = currentNode.next;
    }
    return currentNode
  }

  findPre(item) {
    let cur = this.head
    while (cur.next !== null && cur.next.el !== item) {
      cur = cur.next
    }
    return cur
  }

  // 插入节点
  // el:要插入的数据
  // item：数据插入到这个节点后面
  insert(el, item){
    const newNode = new Node(el)
    const cur = this.find(item)
    newNode.next = cur.next
    cur.next = newNode
  }

  // 删除节点
  remove(item){
    const preNode = this.findPre(item)
    if (preNode.next !== null) {
      preNode.next = preNode.next.next
    }
  }
}

双向链表

双向链表，顾名思义就是它有两个方向，除了next指针指向下一个节点外，比单向链表多了一个prev指针，用来指向上一个节点。

双向链表如下图所示：

和单向链表相比，在存储相同的数据情况下，双向链表要比单向链表占用更多的空间，但双向链表往往会比单向链表更加灵活。例如：

双向链表删除节点时，因为有prev指向上一个节点，就不需要像单向链表一样去寻找待删除节点的前驱节点，使得删除节点的效率提高了。

接下来我们来看下如何实现双向链表：

双向链表的设计

对于节点类，我们只要在单向链表的基础上，加上一个prev指针。

1
2
3
4
5
6
7
class Node {
  constructor(el) {
    this.el = el
    this.next = null
    this.prev = null
  }
}

另外双向链表的查找和单向链表一样，这里就不再细说，我们直接来看下插入节点。

插入

双向链表的插入和单向链表相似，多了一个prev指针，只要将新节点的prev指向前驱节点，将后驱节点的prev指向新节点。如下图所示：

实现代码如下：

1
2
3
4
5
6
7
8
insert(el, item){
    const newNode = new Node(el)
    const cur = this.find(item)
    newNode.next = cur.next
    newNode.prev = cur
    cur.next = newNode
    cur.next.prev = newNode
  }

删除

双向链表的删除 remove 方法比单链表效率高，不需要查找前驱节点，只要找出待删除节点，然后将该节点的前驱 next 属性指向待删除节点的后继，设置该节点后继 previous 属性，指向待删除节点的前驱即可。

实现代码如下：

1
2
3
4
5
6
7
remove(item){
    const node = this.find(item)
    node.prev.next = node.next
    node.next.prev = node.prev
    node.next = null
    node.prev = null
  }

双向链表完整代码如下：

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
37
38
39
40
41
42
43
44
// 双向链表
class Node {
  constructor(el) {
    this.el = el
    this.next = null
    this.prev = null
  }
}

class LinkedList {
  constructor(){
    this.head = new Node('head')
  }

  // 用于查找
  find(item){
    let currentNode = this.head
    while (currentNode !== null && currentNode.el !== item) {
      currentNode = currentNode.next;
    }
    return currentNode
  }

  // 插入节点
  // el:要插入的数据
  // item：数据插入到这个节点后面
  insert(el, item){
    const newNode = new Node(el)
    const cur = this.find(item)
    newNode.next = cur.next
    newNode.prev = cur
    cur.next = newNode
    cur.next.prev = newNode
  }

  // 删除节点
  remove(item){
    const node = this.find(item)
    node.prev.next = node.next
    node.next.prev = node.prev
    node.next = null
    node.prev = null
  }
}

单向循环链表

单向循环链表和单向链表相似，节点类型都一样，唯一的区别就是在创建循环链表的时候，让其头结点的next属性指向它本身。

1
head.next = head

单向循环链表如上图所示，具体的实现细节不再一一细说，我们直接来看实现代码：

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
37
38
39
40
41
42
43
44
45
46
47
48
class Node {
  constructor(el) {
    this.el = el;
    this.next = null;
  }
}

class LinkedList {
  constructor(){
    this.head = new Node('head')
    this.head.next = this.head
  }

  // 用于查找
  find(item){
    let currentNode = this.head
    while (currentNode !== null && currentNode.el !== item) {
      currentNode = currentNode.next;
    }
    return currentNode
  }

  findPre(item) {
    let cur = this.head
    while (cur.next !== null && cur.next.el !== item) {
      cur = cur.next
    }
    return cur
  }

  // 插入节点
  // el:要插入的数据
  // item：数据插入到这个节点后面
  insert(el, item){
    const newNode = new Node(el)
    const cur = this.find(item)
    newNode.next = cur.next
    cur.next = newNode
  }

  // 删除节点
  remove(item){
    const preNode = this.findPre(item)
    if (preNode.next !== null) {
      preNode.next = preNode.next.next
    }
  }
}

双向循环链表

既然单链表可以有循环链表，双向链表也可以是循环链表。双向循环链表头结点的prev指针指向尾结点，尾结点的next指针指向头结点。如下图所示：

实现代码如下：

1
2


本文所有示例代码见：linked-list

参考文章：

欢迎关注微信公众号： 『前端极客技术』『代码视界』
赏
支付宝打赏 微信打赏

赞赏是不耍流氓的鼓励

转载声明： 商业转载请联系作者获得授权,非商业转载请注明出处 © 代码视界
Copyright © 2019 | Powered by Hexo | Theme by Snippet