数据结构 - 链表

概念

链表是一种非线性存储的数据结构，用来解决按照顺序进行物理存储的数据排列（想改变数据的顺序，只需要改变指针即可）

单向链表

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
function Link(key) {
  this.key = key;
  this.next = null;
}
class LinkedList {
  constructor() {
    this.head = new Link("head");
  }
  add(key) {
    const newNode = new Link(key);
    if (this.head === null) {
      this.head = new Link("head");
    } else {
      this.addNode(newNode, this.head);
    }
  }
  addNode(newNode, rootNode) {
    while (rootNode.next != null) {
      rootNode = rootNode.next;
    }
    rootNode.next = newNode;
  }
  find(key) {
    let current = this.head;
    while (current.key !== key) {
      if (current.next == null) return false;
      current = current.next;
    }
    return current;
  }
  convert2array() {
    let current = this.head.next;
    const temp = [];
    while (current) {
      temp.push(current.key);
      current = current.next;
    }
    return temp;
  }
  toString() {
    console.log(this.head);
  }
}
module.exports = LinkedList;

双向链表