数据结构与算法之单向链表

devin 2/25/2022 JavaScript

# 什么是单向链表

先来思考一下什么是链表？第一时间我们可能会联想到数组，但是数组是存储在特定索引中，而链表每一个元素都是一个独立的对象，每个元素(节点)包含存储的数据以及指向下一个引用的next链接，看下面的一张图你就大致懂单向链表的构造了。

这个时候你可能比较好奇为什么会定义一个head头部？因为开始结点无前驱，所以设头指针head指向开始结点。

通过使用head作为链表入口，需要注意的是：head是对链表中第一个节点的引用。并且链表的最后一个节点指向NULL。如果是一个空链表那么head指向为NULL。

# 链表和数组区别

数组
- 数组的优点：随机访问性强、查找速度快；
- 数组的缺点：插入删除效率低、可能浪费内存、内存空间要求高需要有足够的连续内存空间。
链表
- 链表的优点：插入删除效率高、内存利用率高不会浪费内存、大小不固定拓展灵活；
- 链表的缺点：查找效率低，不能随机查找，必须从第一个开始遍历。

# js手撸一个单向链表

在第一章节我介绍了链表的构造，那么用js构造出来的单向链表应该长什么样呢？拿第一章节那张图来举例，可以得到如下所示的代码：

// js构造单向链表解构代码
const list = {
  head: {
    data: 1,
    next: {
      data: 6,
      next: {
        data: 8,
        next: null,
      },
    },
  },
};

1
2
3
4
5
6
7
8
9
10
11
12
13

实现步骤：

js实现链表

// 链表---链表初始化时，初始化head节点
class NodeList {
  constructor (head = null) {
    this.head = head;
  }
}

1
2
3
4
5
6

js节点

// 需要存储节点数据的字段（data）和一个字段（next）指向下一个节点
class Node { // 链表节点
  constructor (data) {
    this.data = data; // 节点数据
    this.next = null; // 下一个节点指针
  }
}

1
2
3
4
5
6
7

使用上面创建的类来创建一个链表

const node1 = new Node(1); // 创建node1节点
const node2 = new Node(6); // 创建node2节点
const node3 = new Node(8); // 创建node3节点
const list = new NodeList(node1); // 创建单向链表，并将head头节点指向node1
node1.next = node2; // node1的next指向node2节点
node2.next = node3; // node2的next指向node3节点
console.log(list)

1
2
3
4
5
6
7

打印出来的list单向链表如下图所示：

js实现链表中存在的节点数、清空链表、返回链表最后一个节点或者第一个节点

// 链表---链表初始化时，初始化head节点
class NodeList {
  constructor (head = null) {
    this.head = head;
  }
  // 链表中存在的节点数
  size () {
    let count = 0;
    let currentNode = this.head;
    while (currentNode) {
      count++;
      currentNode = currentNode.next;
    }
    return count;
  }
  // 清空该链表
  clear () {
    this.head = null; // 只需要将head的指向改为null即可
  }
  // 返回链表最后一个节点
  getLast () {
    let lastNode = this.head;
    while (lastNode && lastNode.next) {
      lastNode = lastNode.next;
    }
    return lastNode;
  }
  // 返回链表第一个节点
  getFirst () {
    return this.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

这里只是带着大家写了一个简单的单向链表，至于链表中查找、删除、添加在这里我没有介绍，后续空闲时间我会画图解析说明并配上相关的代码，当然如果你看到这里如果懂了的话也可以自己尝试写一下那几种方法，如果能够实现证明你是真的明白了。

木头的个人博客

Choose mode