Javascript之双向链表

上篇文章(链表LinkedList的实现)中实现了普通链表的基本功能,那么本文再来实现一下双向链表。双向链表和普通链表的区别在于,在普通链表中,一个节点只有链向下一个节点的链接,而在双向链表中,链接是双向的:一个链向下一个节点,另一个链向上一个节点。

双向链表
双向链表(图片来源于网络)

同样实现和上篇文章中和链表一样的功能,只不过多了一个上一个节点prev的处理。

DoublyLinkedList类包括如下的这些方法:

  • append(element):向列表尾部添加一个新元素。
  • removeAt(position):删除列表中指定位置的元素。
  • insert(position, element):删除列表中指定位置的元素。
  • indexOf(element):返回指定元素在列表中的位置。
  • remove(element):删除指定元素。
  • getHead():获取列表第一个元素。
  • getTail():获取列表最后一个元素。
  • isEmpty():列表是否为空。
  • size():列表的大小。

insert(position, element)方法为例,向链表中添加一个新元素到指定位置。这里需要考虑到三种情况:1.向一个位置添加元素;2.向最后一个位置添加元素;3.向中间位置添加元素。

当向第一个位置添加元素时,需要判断当前链表是否有元素,如果没有,直接添加的就是第一个节点,同时也是最后一个节点。

当链表不为空时,则需要把原来的第一个元素的prev指向新元素,然后再将新元素的next指向原来的第一个元素,再将第一个元素head更新为当前添加的元素。

当向最后一个位置添加元素时,需要将原最后一个元素的next指向新元素,并将新元素的prev指向原最后一个元素,最后再更新最后一个元素tail

最后一种情况是向中间位置添加元素,从第一个元素head开始向后迭代(当然,也可以根据position相对于链表的长度,选择从第一个或最后一个位置开始迭代,增加迭代效率)。迭代到指定位置后,将该位置元素的prev设置为待添加的元素node,将nodenext设置为原该位置的元素。同理,将原迭代位置的上一个元素的next设置的node,在将nodeprev也指向上一个元素。

详细查看代码

const DoublyLinkedList = (function () {
    let head = null,
        tail = null,
        length = 0

    const Node = class {
        constructor(element) {
            this.element = element
            this.prev = null
            this.next = null
        }
    }

    class DoublyLinkedList {
        append(element) {
            const node = new Node(element)
            if (length === 0) {
                head = tail = node
            } else {
                node.prev = tail
                tail.next = node
                tail = node
            }
            length++
        }

        insert(position, element) {
            const node = new Node(element)
            let current = head
            if (position > -1 && position < length) {
                if (position === 0) {
                    if (head === null) {
                        head = node
                        tail = node
                    } else {
                        head = node
                        head.next = current
                        current.prev = head
                    }
                } else if (position === length - 1) {
                    tail.next = node
                    node.prev = tail
                    tail = node
                } else {
                    let index = 0,
                        prev = null
                    while (index++ < position) {
                        prev = current
                        current = current.next
                    }
                    prev.next = node
                    node.prev = prev

                    current.prev = node
                    node.next = current
                }
                length++
                return true
            }
            return false
        }

        removeAt(position) {
            if (position > -1 && position < length) {
                let current = head
                if (position === 0) {
                    if (length === 1) {
                        head = tail = null
                    } else {
                        head = head.next
                        head.prev = null
                    }
                } else if (position === length) {
                    current = tail
                    tail = tail.prev
                    tail.next = null
                } else {
                    let index = 0,
                        prev = null
                    while (index++ < position) {
                        prev = current
                        current = current.next
                    }
                    prev.next = current.next
                    current.next.prev = prev
                }
                length--
                return current.element
            }
        }

        indexOf(element) {
            let current = head,
                index = 0
            while (current) {
                if (current.element === element) {
                    return index
                }
                index++
                current = current.next
            }
            return -1
        }

        remove(element) {
            const index = this.indexOf(element)
            return this.removeAt(index)
        }

        isEmpty() {
            return length === 0
        }

        size() {
            return length
        }

        getHead() {
            return head
        }

        getTail() {
            return tail
        }

        toString() {
            let current = head,
                str = ''
            while (current) {
                str += `element: ${current.element}, prev: ${current.prev ? current.prev.element : 'null'}, next: ${current.next ? current.next.element + '\r\n' : 'null'}`
                current = current.next
            }
            return str
        }
    }

    return DoublyLinkedList
}())

const doublyLinkedList = new DoublyLinkedList()
doublyLinkedList.append('a')
doublyLinkedList.append('b')
doublyLinkedList.append('c')
doublyLinkedList.append('d')
doublyLinkedList.insert(1, 'hello world')
console.log(doublyLinkedList.toString());
console.log(doublyLinkedList.indexOf('hello world'));

//输出
// element: a, prev: null, next: hello world
// element: hello world, prev: a, next: b
// element: b, prev: hello world, next: c
// element: c, prev: b, next: d
// element: d, prev: c, next: null
// 1
如果您觉得本文对您有用,欢迎捐赠或留言~
微信支付
支付宝

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注