单向链表的 js 实现

— By BingqiChen

单向链表

链表是一种数据结构,有单向链表、双向链表和循环链表,单向链表事其中最简单的一种。它有一个 head 指针,整个链表有很多节点构成,而 head 会始终指向链表的头节点;每个节点由两个信息组成:节点数据和指向下一个节点的指针,最后一个节点的指针为 null

节点

单向链表是由一个个节点组成的数据结构类型,每个节点都包含该节点的数据和指向下一个节点的指针,构造一个节点很简单,只需要包含这两项内容就可以了,用 ES6 的写法可以这样描述一个节点:

/**
 * 单个链表节点
 */
class Node {
  constructor(val) {
    this.val = val;
    this.next = null;
  }
}

链表结构

一个链表除了由一个个节点之外,还包含一些属性,如:长度、head指针(用以指向链表的第一个节点),这里新建一个类作如下描述:

/**
 * 链表
 */
class LinkedList {
  constructor(val = null) {
    this.head = null; // 链表的head指针
    this.length = 0; // 链表的长度
    if (val) {
      this.head = new Node(val);
      this.length = 1;
    }
  }
}

这样这个链表结构就有了额外的长度、head指针信息,我们可以构造一个实例看看:

添加一些方法

一般链表都会包含一些操作方法,比如 append、remove...下面就来来添加这些操作函数。

append(在链表尾部添加一个节点)

这里的重点是如何找到链表尾部,这里使用循环整个链表,找到一个节点,它的 next 指向为空即可:

  class LinkedList {
    ...
    append(val) {
      const node = new Node(val); // 创建节点
      if (this.head === null) { // 如果是个空列表
        this.head = node;
      } else {
        let current = this.head;
        while (current.next) { // 找到 next 指向为空的节点
          current = current.next;
        }
        current.next = node;
      }
      this.length += 1; // 整个链表的长度增加
    }
    ...
  }

removeAt(删除指定位置的节点)

从一个链表删除某节点,只需要将该节点前一个的 next 指向替换为该节点的 next 指向即可,这样从整个链表来看就跳过了该节点,需要注意的是需要对用户的输入进行判断:

  class LinkedList {
    ...
    removeAt(position) {
      if (position >= this.length || position < 0) { // 判断输入
        return null;
      }
      let current = this.head;
      if (position === 0) { // 删除头节点,只需改变 head 指针即可
        this.head = current.next;
      } else {
        let index = 0;
        let prev = null;
        while (index < position) {
          prev = current;
          current = current.next;
          index += 1;
        }
        prev.next = current.next; // 改变上一个节点的 next 指向
      }
      this.length -= 1; // 长度减少
      return current.val; // 返回删除节点的值
    }
    ...
  }

insert(在指定位置插入节点)

跟前面的尾部插入不同,这里需要找到插入的位置,再执行插入操作:

  class LinkedList {
    ...
    insert(position, val) {
      if (position >= this.length || position < 0) {
        return false;
      }
      const node = new Node(val);
      if (position === 0) { // 插入位置在头节点
        node.next = this.head;
        this.head = node;
      } else {
        let index = 0;
        let current = this.head;
        let prev = null;
        while (index < position) { // 遍历链表找到指定位置的节点,并记录下前一个节点和该位置原节点
          prev = current;
          current = current.next;
          index += 1;
        }
        node.next = current;
        prev.next = node;
      }
      this.length += 1;
      return true;
    }
    ...
  }

这里可以看到关键的两步是:把插入位置的前一个节点的 next 指向待插入的节点;把待插入的节点的 next 指向原来在该位置上的节点。

indexOf(返回第一个指定值的节点的位置)

这个功能也比较简单,只需要从第一个节点开始遍历,直到找到值符合要求的节点位置即可,在这里加入了一个可以设置起始位置的功能,无非是多了一个判断:

  class LinkedList {
    ...
    indexOf(val, start = 0) {
      if (start >= this.length) { // 判断起始位置是否合法
        return -1;
      }
      let index = 0;
      let current = this.head;
      while (index < this.length) {
        if (current.val === val && index >= start) {
          return index;
        }
        current = current.next;
        index += 1;
      }
      return -1;
    }
    ...
  }

remove(移除第一个指定值的节点)

这个功能可以结合上面的 indexOfremoveAt 来完成:

  class LinkedList {
    ...
    remove(val, start = 0) {
      const index = this.indexOf(val, start);
      return this.removeAt(index);
    }
    ...
  }

size(返回链表长度)

  class LinkedList {
    ...
    size() {
      return this.length;
    }
    ...
  }

isEmpty(返回是否为空链表)

  class LinkedList {
    ...
    isEmpty() {
      return !!this.length;
    }
    ...
  }

添加了这些方法之后,就是一个完整的单向链表 js 实现了。