cover

数据结构与算法之链表

最后更新:  阅读时间: 3 min 知识共享许可协议

前言

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

实现

使用 LinkedListNode 类来表示节点，使用 LinkedList 来表示链表

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
class LinkedListNode {
  element: any
  next: LinkedListNode

  constructor(element: any) {
    this.element = element
    this.next = null
  }
}

class LinkedList {
  // 头节点
  head: LinkedListNode

  constructor() {
    this.head = new LinkedListNode('head')
  }

  // 查找
  find(element: any) {
    let currentNode: LinkedListNode = this.head

    while (currentNode.element !== element) {
      currentNode = currentNode.next
    }
    return currentNode
  }

  // 插入
  insert(element: any, item: any) {
    let newNode = new LinkedListNode(element)
    let currentNode = this.find(item)

    newNode.next = currentNode.next
    currentNode.next = newNode
  }

  // 移除
  remove(element: any) {
    let prevNode = this.findPrevNode(element)

    if (!(prevNode.next === null)) {
      prevNode.next = prevNode.next.next
    }
  }

  //
  findPrevNode(element: any) {
    let currentNode = this.head
    while (
      !(currentNode.next === null) &&
      currentNode.next.element !== element
    ) {
      currentNode = currentNode.next
    }
    return currentNode
  }

  // 显示
  display() {
    let currentNode = this.head

    while (!(currentNode.next === null)) {
      console.log(currentNode.next.element)
      currentNode = currentNode.next
    }
  }
}

测试

1
2
3
4
5
6
7
8
9
10
11
const foods = new LinkedList()

foods.insert('eggs', 'head')
foods.insert('apple', 'eggs')
foods.insert('bread', 'apple')
foods.insert('chese', 'bread')
foods.insert('rice', 'chese')
foods.display()
console.log('------------')
foods.remove('bread')
foods.display()

输出

1
2
3
4
5
6
7
8
9
10
eggs
apple
bread
chese
rice
------------
eggs
apple
chese
rice

双向链表

要实现双向链表首先要为 LinkedListNode 类增加一个 prev 属性

1
2
3
4
5
6
7
8
9
10
11
class LinkedListNode {
  element: any
  prev: LinkedListNode
  next: LinkedListNode

  constructor(element: any) {
    this.element = element
    this.prev = null
    this.next = null
  }
}

然后修改 LinkedList 类的 insert, remove 方法

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
class LinkedList {
  // 头节点
  head: LinkedListNode = new LinkedListNode('head')

  // 查找
  find(element: any) {
    let currentNode = this.head

    while (currentNode.element !== element) {
      currentNode = currentNode.next
    }
    return currentNode
  }

  // 找到最后的节点
  findLast() {
    let currentNode = this.head

    while (currentNode.next !== null) {
      currentNode = currentNode.next
    }
    return currentNode
  }

  // 插入
  insert(element: any, item: any) {
    let newNode = new LinkedListNode(element)
    let currentNode = this.find(item)

    newNode.prev = currentNode
    newNode.next = currentNode.next
    currentNode.next = newNode
  }

  // 移除
  remove(element: any) {
    let currentNode = this.find(element)

    if (currentNode.next !== null) {
      currentNode.prev.next = currentNode.next
      currentNode.next.prev = currentNode.prev
      currentNode.next = null
      currentNode.prev = null
    }
  }

  // 显示
  display() {
    let currentNode = this.head

    while (!(currentNode.next === null)) {
      console.log(currentNode.next.element)
      currentNode = currentNode.next
    }
  }

  // 倒叙显示
  displayReverse() {
    let currentNode = this.findLast()

    while (currentNode.prev !== null) {
      console.log(currentNode.element)
      currentNode = currentNode.prev
    }
  }
}

测试一下

1
2
3
4
5
6
7
8
9
10
11
foods.insert('eggs', 'head')
foods.insert('apple', 'eggs')
foods.insert('bread', 'apple')
foods.insert('chese', 'bread')
foods.insert('rice', 'chese')
foods.display()
console.log('------------')
foods.remove('bread')
foods.display()
console.log('------------')
foods.displayReverse()

输出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
eggs
apple
bread
chese
rice
------------
eggs
apple
chese
rice
------------
rice
chese
apple
eggs

循环链表

创建循环链表需要让它的头节点的 next 属性指向本身， 然后修改 display 方法

1
2
3
4
5
6
7
8
9
10
11
this.head.next = this.head

 // 显示
display() {
  let currentNode = this.head

  while (currentNode.next !== null && currentNode.next.element !== 'head') {
    console.log(currentNode.next.element)
    currentNode = currentNode.next
  }
}

总结

链表是一种高效的数据结构，如果发现数组在使用时很慢，就可以考虑用链表替代它，但是如果需要对数据随机访问，数组任然是更优的选择

Buy Me A Coffee
← 数据结构与算法之字典 如何在 Egg.js 中使用 Sequelize 的事务 Transaction →