作为一名程序员, 编程中很痛苦的一件事情就是看一大段没有注释, 而且多层嵌套, 多层循环的代码, 有时候暗自骂一句'哈麻批'.
在之前一篇文章中, 数据结构 ---- 双向链表里面, 就有很多临界条件判断, 而且有多层循环, 我讨厌这样的代码. 所以, 我写完之后也在思考, 是否有更好的实现方式. 今天偶尔有空, 实现了一下, 把 140 行垃圾代码, 精简到 70 行. 我们来看下实现过程.
1. 结点的结构
结点的结构还是没变, key 值存储数据, prev 指向前驱结点, next 指向后继结点.
如图 1:
代码如下:
- class Node {
- constructor (key) {
- this.key = key
- this.prev = null
- this.next = null
- }
- }
2. 链表的结构
链表的结构也大致和之前一样, 只不过初始化的时候, 头部结点 head 和尾部结点提前定义, 而且不会变化. 这样做的好处是, 我们无需判断很多边界问题, 所以代码量会减少很多.
代码如下:
- class Node {
- constructor (key) {
- this.key = key
- this.prev = null
- this.next = null
- }
- }
- class Link {
- constructor () {
- this.head = new Node(Symbol('head'))
- this.tail = new Node(Symbol('tail'))
- this.head.next = this.tail
- this.tail.prev = this.head
- this.length = 0
- }
- }
在这里, head 的 key 和 tai 的 key 使用了 Symbol, 保证了它们的 key 值不会与之后加入的结点的 key 值相同. 初始化的时候, head 的 next 指向 tail,tail 的 prev 指向 head.
3.push 方法
这个方法相对好实现, 只需要在 tail 结点之前, 加上一个结点就可以了.
代码如下:
- class Node {
- constructor (key) {
- this.key = key
- this.prev = null
- this.next = null
- }
- }
- class Link {
- constructor () {
- this.head = new Node(Symbol('head'))
- this.tail = new Node(Symbol('tail'))
- this.head.next = this.tail
- this.tail.prev = this.head
- this.length = 0
- }
- push (key) { // 向尾部添加一个结点
- let node = new Node(key)
- let prevNode = this.tail.prev // 获取尾部结点前面一个结点
- // 将结点插入在 tail 结点之前
- prevNode.next = node
- node.prev = prevNode
- node.next = this.tail
- this.tail.prev = node
- this.length ++
- }
- }
- const link = new Link()
- link.push('jack')
- link.push('love')
- link.push('rose')
- console.log(link)
添加完成之后链表的结构如图:
4.insert(data, pos) 把 key 为 data 的结点插入在第 pos + 1 个结点之前 (不包括首尾结点)
代码如下:
- class Node {
- constructor (key) {
- this.key = key
- this.prev = null
- this.next = null
- }
- }
- class Link {
- constructor () {
- this.head = new Node(Symbol('head'))
- this.tail = new Node(Symbol('tail'))
- this.head.next = this.tail
- this.tail.prev = this.head
- this.length = 0
- }
- push (key) { // 向尾部添加一个结点
- let node = new Node(key)
- let prevNode = this.tail.prev // 获取尾部结点前面一个结点
- // 将结点插入在 tail 结点之前
- prevNode.next = node
- node.prev = prevNode
- node.next = this.tail
- this.tail.prev = node
- this.length ++
- }
- insert (key, pos) {
- let node = new Node(key)
- let current = this.head
- let index = 0
- while (index < pos) {
- current = current.next
- index ++
- }
- let nextNode = current.next
- current.next = node
- node.prev = current
- nextNode.prev = node
- node.next = nextNode
- this.length ++
- }
- }
- const link = new Link()
- link.push('jack')
- link.push('love')
- link.push('rose')
- link.insert('now', 0)
- link.insert('must', 2)
- link.insert('forever', 5)
- console.log(link)
我们在之前创建的链表里面插入了 now 到第一个位置 (除开头部结点), 把 must 插入到 jack 后面, 最后, 我们希望 jack 能永远rose.
大家可以点击代码右上角的运行, 看下打印的链表结构.
这段代码的实现, 比之前的实现要容易看很多, 没有很多临界条件判断, 也简约了很多. 简约的代码就是一种美.
5.remove(data), 移除为 key 的 data 的结点
我们需要从 head 结点开始循环, 直到找到 key 为 data 的结点, 改变此结点前驱结点与后继结点的关系, 并返回 key, 找不到返回 - 1.
代码如下:
- class Node {
- constructor (key) {
- this.key = key
- this.prev = null
- this.next = null
- }
- }
- class Link {
- constructor () {
- this.head = new Node(Symbol('head'))
- this.tail = new Node(Symbol('tail'))
- this.head.next = this.tail
- this.tail.prev = this.head
- this.length = 0
- }
- push (key) { // 向尾部添加一个结点
- let node = new Node(key)
- let prevNode = this.tail.prev // 获取尾部结点前面一个结点
- // 将结点插入在 tail 结点之前
- prevNode.next = node
- node.prev = prevNode
- node.next = this.tail
- this.tail.prev = node
- this.length ++
- }
- insert (key, pos) {
- let node = new Node(key)
- let current = this.head
- let index = 0
- while (index < pos) {
- current = current.next
- index ++
- }
- let nextNode = current.next
- current.next = node
- node.prev = current
- nextNode.prev = node
- node.next = nextNode
- this.length ++
- }
- remove (key) {
- let current = this.head
- while (current.next && current.key !== key) { // 因为 symbol,key 的值不可能是头部或者尾部的值
- current = current.next
- }
- if (current === this.tail) { // 到 tail 结点都没有找到
- return -1
- } else { // 找到了, 改变一下此结点 prev 结点和 next 结点的指向
- let nextNode = current.next
- let prevNode = current.prev
- prevNode.next = nextNode
- nextNode.prev = prevNode
- this.length --
- return current.key
- }
- }
- }
- const link = new Link()
- link.push('jack')
- link.push('love')
- link.push('rose')
- link.insert('now', 0)
- link.insert('must', 2)
- link.insert('forever', 5)
- link.remove('forever')
- console.log(link)
泰坦尼克号沉了, jack 无法永远爱 rose 了...
好了, 说了这么多该洗洗睡了, 晚安.
来源: http://www.qdfuns.com/article/50934/223d3ef0ba5da1b248e254c131d653ce.html