JavaScript链表---单向链表

简介

链表是由一组节点组成的集合，每个节点都有一个对象的引用指向下一个节点。指向下一个节点的引用叫做链。

data中保存数据，next保存下一个节点的引用。我们可以看到链表的尾元素指向null，表示结束。

由于链表的头结点确定起来很麻烦，由此我们又引入了头结点，来表示链表的头部。

实现

首先我们定义一个Node类来表示节点。从图中可以看出，Node类中需要包含两个属性：

1. element： 用来保存节点上的数据
2. next： 用来保存指向下一个节点的链接

class Node {
  constructor(element) {
    this.element = element; // 当前节点数据
    this.next = null; // 下一个节点的链接
  }
}
1
2
3
4
5
6

我们再定义一个LinkedList类来提供操作链表的一些方法，LinkedList 中只有一个头节点属性。

class LList {
  constructor() {
    this.head = new Node("head"); // 头节点
  }

  /**
   * 显示链表
   */
  display() {}

  /**
   * 查找节点
   * @param {*} item  给定节点
   */
  find(item) {}

  /**
   * 
   * @param {*} item 给定节点
   * @param {*} newElement 插入的新节点
   */
  insert(item, newElement) {}

  /**
   * 查找前一个节点
   * @param {*} item  给定节点
   */
  findPrev(item) {}

  /**
   * 删除节点
   * @param {*} item 
   */
  remove(item) {}
}

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

查看链表

定义一个方法，打印出链表的值，遍历链表，直到next为null。

  display() {
    let currentNode = this.head;
    while (currentNode !== null) {
      console.log(currentNode.element);
      currentNode = currentNode.next;
    }
  }

1
2
3
4
5
6
7
8
9

头节点 next 的初始值是 null，插入新元素后next指向新元素。

想要完成在一个给定节点后插入一个新节点，第一步需要找到这个给定节点。

查找节点

从链表头节点开始查找，遍历链表。

  find(item) {
    let currentNode = this.head;
    while (currentNode !== null && currentNode.element !== item) {
      currentNode = currentNode.next;
    }
    return currentNode;
  }

1
2
3
4
5
6
7
8
9

查找到节点之后，就可以在之后插入新节点了。

插入节点

将新节点的next指向给定节点原本的next，给定节点next指向新节点。

  insert(item, newElement) {
    let newNode = new Node(newElement);
    let oldNode = this.find(item);
    newNode.next = oldNode.next;
    oldNode.next = newNode;
  }

1
2
3
4
5
6
7
8

下面我们来看看方法是否正确：

let fruits = new LList();

fruits.insert("head", "Apple");
fruits.insert("Apple", "Banana");
fruits.insert("Banana", "Pear");

fruits.display();

1
2
3
4
5
6
7
8
9

输出：

查找前一个节点

想要删除一个节点需要找到他的前一个节点

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

删除节点

将需要删除的前一个节点的next指向删除节点的next

  remove(item) {
    let prevNode = this.findPrev(item);
    if (prevNode.next !== null) {
      prevNode.next = prevNode.next.next;
    }
  }

1
2
3
4
5
6
7
8

下面我们再验证一下删除功能：

fruits.remove("Apple");
fruits.display();
1
2

输出：

点击查看源码，在线试一试