js数据结构--链表

发表于 | 更新于 | 阅读次数 28
js算法与数据结构--链表Linked-list

前端说的栈、队列，它们都是列表的一种，底层的数据结构都是数组。

但是数组并不总是最佳的数据结构，索引引入链表结构：

链表（LinkedList）

介绍

链表的出现是为了解决数组增删的操作，在js中，虽然存在如下方法：

  • 尾部添加 push
  • 尾部删除 pop
  • 头部添加 unshift
  • 头部删除 shift
  • 任意位置添加删除 splice

但是与其他语言相比，效率会比较低，所以考虑使用链表（Linked-list）来替换它，链表几乎可以在任何可以使用一位数组的情况中。

链表包含：

  • 单向链表
  • 双向链表
  • 单向循环列表
  • 双向循环列表

定义

链表是一组节点组成的集合，每个节点都使用一个对象的引用来指向它的后一个节点。指向另一个节点的引用称作为链。

链表结构图


其中，data保存数据，next保存着下一个链表的引用，链表的尾元素指向null，表示结束位置。

由于链表的起始点确定比较麻烦，因此在链表的最前面添加一个特殊的节点，成为头节点，表示链表的头部，如：

有头节点的链表

用我们常见的数据结构，大致是这样：

链表数据结构

单向链表

设计链表包含两个类，一个是 Node 类用来表示节点，另一个是 LinkList 类提供增删等操作。

  • Node类

    1
    2
    3
    4
    function Node(el) {
      this.el = el                    // 当前节点元素
      this.next = null                // 下一个节点的链接
    }

  • LinkList类

    1
    2
    3
    4
    5
    6
    7
    8
    9
    function LinkList() {
      this.head = new Node('head')     // 头结点
      this.find = find                 // 查找结点
      this.findPrev = findPrev         // 查找前一个结点
      this.insertAfter = insertAfter   // 在某个节点后插入节点（结合find）
      this.insertBefore = insertBefore // 在某个节点后插入节点（结合findPrev）
      this.remove = remove             // 删除结点（结合findPrev）
      this.display = display           // 显示链表
    }

下面挨个实现这些方法：

find 查找节点

1
2
3
4
5
6
7
function find(el) {
  var curNode = this.head // 从链表头部开始扫描
  while(curNode.el !== el) {
    curNode = curNode.next
  }
  return curNode
}

findPrev 查找前一个结点

1
2
3
4
5
6
7
function findPrev(el) {
  var prevNode = this.head // 从链表头部开始扫描
  while(prevNode.next !== null && prevNode.next.el !== el) {
    prevNode = prevNode.next
  }
  return prevNode
}

insertAfter 在某个节点后插入节点

1
2
3
4
5
6
function insertAfter(newEl, el) {
  var newNode = new Node(newEl)
  var curNode = this.find(el)
  newNode.next = curNode.next
  curNode.next = newNode
}

insertBefore 在某个节点前插入节点

1
2
3
4
5
6
function insertBefore(newEl, el) {
  var newNode = new Node(newEl)
  var prevNode = this.findPrev(el)
  newNode.next = prevNode.next
  prevNode.next = newNode
}

remove 删除节点

1
2
3
4
5
6
function remove(el) {
  var prevNode = this.findPrev(el)
  if (prev !== null) {
    prev.next = prev.next.next
  }
}

display 显示链表

1
2
3
4
5
6
7
function display() {
  var curNode = this.head // 从链表头部开始扫描
  while(curNode !== null) {
    console.log(curNode)
    curNode = curNode.next
  }
}

全部代码如下：

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
function Node(el) {
  this.el = el                    // 当前节点元素
  this.next = null                // 下一个节点的链接
}

function LinkList() {
  this.head = new Node('head')     // 头结点
  this.find = find                 // 查找结点
  this.findPrev = findPrev         // 查找前一个结点
  this.insertAfter = insertAfter   // 在某个节点后插入节点（结合find）
  this.insertBefore = insertBefore // 在某个节点后插入节点（结合findPrev）
  this.remove = remove             // 删除结点（结合findPrev）
  this.display = display           // 显示链表
}

// 查找节点
function find(el) {
  var curNode = this.head // 从链表头部开始扫描
  while(curNode.el !== el) {
    curNode = curNode.next
  }
  return curNode
}

// 查找上一个节点
function findPrev(el) {
  var prevNode = this.head // 从链表头部开始扫描
  while(prevNode.next !== null && prevNode.next.el !== el) {
    prevNode = prevNode.next
  }
  return prevNode
}

// 在某个节点后插入新节点
function insertAfter(newEl, el) {
  var newNode = new Node(newEl)
  var curNode = this.find(el)
  newNode.next = curNode.next
  curNode.next = newNode
}

// 在某个节点前插入新节点
function insertBefore(newEl, el) {
  var newNode = new Node(newEl)
  var prevNode = this.findPrev(el)
  newNode.next = prevNode.next
  prevNode.next = newNode
}

// 删除节点
function remove(el) {
  var prevNode = this.findPrev(el)
  if (prevNode !== null) {
    prevNode.next = prevNode.next.next
  }
}

// 显示链表
function display() {
  var curNode = this.head // 从链表头部开始扫描
  while(curNode !== null) {
    console.log(curNode)
    curNode = curNode.next
  }
}

测试：

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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
var nums = new LinkList()
// nums:
/* {
  ...,
  head: {
    el: 'head',
    next: null
  },
  ...
} */

nums.insertAfter('1', 'head') // 在head头节点之后插入节点1
// nums:
/* {
  ...,
  head: {
    el: 'head',
    next: {
      el: "1",
      next: null
    }
  },
  ...
} */

nums.insertBefore('2', '1') // 在节点1之前插入节点2
// nums:
/* {
  ...,
  head: {
    el: 'head',
    next: {
      el: "2",
      next: {
        el: "1",
        next: null
      }
    }
  },
  ...
} */

nums.find('2') // 查找节点2
/* {
  el: "2",
  next: {
    el: "1",
    next: null
  }
} */
nums.find('1') // 查找节点1
/* {
  el: "1",
  next: null
} */

nums.findPrev('1') // 查找节点1上一个节点（等同于find('2')）
/* {
  el: "2",
  next: {
    el: "1",
    next: null
  }
} */

nums.remove('1') // 删除节点1
// nums:
/* {
  ...,
  head: {
    el: 'head',
    next: {
      el: "2",
      next: null
    }
  },
  ...
} */

nums.display()
/* {
  ...,
  head: {
    el: 'head',
    next: {
      el: "2",
      next: null
    }
  },
  ...
} */
/* {
  ...,
  head: {
    el: '2',
    next: null
  },
  ...
} */

双向链表

要实现双向链表，除了 next 外，还需要一个 previous 属性：

1
2
3
4
5
function Node(el) {
  this.el = el
  this.next = null
  this.previous = null
}

完整代码如下：

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
69
70
71
72
73
74
75
function Node(el) {
  this.el = el
  this.next = null
  this.previous = null
}

function LinkList() {
  this.head = new Node('head')          // 头结点
  this.find = find                      // 查找结点
  this.findLast = findLast              // 查找最后一个结点
  this.insert = insert                  // 在某个节点后插入节点
  this.remove = remove                  // 删除结点
  this.display = display                // 显示链表
  this.displayReverse = displayReverse  // 反向显示链表
}

// 查找结点
function find(el) {
  var curNode = this.head // 从链表头部开始扫描
  while(curNode.el !== el) {
    curNode = curNode.next
  }
  return curNode
}

// 查找最后一个结点
function findLast() {
  var curNode = this.head // 从链表头部开始扫描
  while(curNode.next !== null) {
    curNode = curNode.next
  }
  return curNode
}

// 在某个节点后插入节点
function insert(newEl, el) {
  var newNode = new Node(newEl)
  var curNode = this.find(el)
  newNode.next = curNode.next
  newNode.previous = curNode
  curNode.next = newNode
}

// 删除结点
function remove(el) {
  var curNode = this.find(el)
  if (curNode.next !== null) {
    curNode.previous.next = curNode.next
    curNode.next.previous = curNode.previous
    curNode.next = null
    curNode.previous = null
  } else {
    curNode.previous.next = null
  }
}

// 显示链表
function display() {
  var curNode = this.head
  // 注意while中为curNode，而非curNode.next，curNode.next会漏掉尾部
  while(curNode !== null) {
    console.log(curNode)
    curNode = curNode.next
  }
}

// 反向显示链表
function displayReverse() {
  var curNode = this.findLast()
  // 注意while中为curNode，而非curNode.previous，curNode.previous会溜掉头部
  while(curNode !== null) {
    console.log(curNode)
    curNode = curNode.previous
  }
}

单向循环链表

单向循环链表，尾结点的next指向头节点，即：

单向循环链表结构图

循环链表判断最后一个节点的条件不再是“后继是否为空”，而是“后继是否为头节点”。

双向循环链表

单向循环列表链表 + 双向链表 组合情况

其他数据结构

参考：简书 JS中的算法与数据结构——链表(Linked-list)