前端学习 数据结构与算法 快速入门 系列 —— 链表

2021年9月23日 4点热度 0条评论 来源: 彭加李

链表

链表数据结构

前面我们已经学习了数组数据结构,但是从数组头部或中间插入元素,或者移除元素的成本比较高,因为需要移动元素。

就像这样:

// 从头部插入元素
Array.prototype.insertFirst = function (v) {
    for (let i = this.length; i >= 1; i--) {
        this[i] = this[i - 1]
    }
    this[0] = v
}

链表不同于数组,链表中的元素在内存中不是连续放置的,每个元素由一个存储元素本身的节点和一个指向下一个元素的引用(也称为指针)组成。就像这样:

              Node             Node                      Node
head -> [value | next] -> [value | next] -> ... -> [value | next(undefined)]

要想访问链表中的元素,需要从起点(表头)开始迭代,直到找到所需要的元素。

就像寻宝游戏,给你一个起始线索,得到第二个线索,在得到下一个线索...。要得到中间线索的唯一方法就是从起点(第一条线索)顺着寻找。

相对于数组,链表的一个好处是,添加或移除元素的时候不需要移动其他元素,无论是从头部、尾部还是中间来添加或移除。

比较典型的例子就是火车,非常容易增加一节车厢或移除一个车厢,只需要改变一下车厢的挂钩即可。

创建链表

理解了链表,我们就要开始实现我们的数据结构,以下是 LinkedList 的骨架:

// 链表中的节点
class Node{
    constructor(element){
        this.element = element
        this.next = undefined
    }
}

// 默认的相等的函数
function defaultEquals(a, b){
    return Object.is(a, b)
}

// 链表类
class LinkedList{
    constructor(equalsFn = defaultEquals){
        this.count = 0
        this.head = undefined
        this.equalsFn = equalsFn
    }
}

链表中的方法:

  • push(element),向链表尾部添加一个新元素

  • insert(element, index),在任意位置插入新元素。插入成功返回 true,否则返回 false

  • remove(element) 移除特定元素。返回删除的元素

  • removeAt(index) 从任意位置移除元素,并返回删除的元素。索引从 0 开始

  • size() 返回链表中元素的个数

  • isEmpty() 如果链表不包含任何元素,返回 true,否则返回 false

  • toString() 返回表示链表的字符串

  • indexOf(element) 返回元素在链表中的索引。如果没有该元素,则返回 -1

  • getElementAt(index) 取得特定位置的元素。如果不存在这样的元素,则返回 undefined。

    • getNodeAt(index) 取得特定位置的节点。和 getElementAt(index) 唯一不同是返回值,前者返回 node,后者返回 element。

Tip:理解了什么是链表,比较容易想到的方法有

  • 插入和删除:pushinsertremoveremoveAt
  • 其他:sizeisEmptytoString

向链表尾部添加一个新元素

第一种实现,需要依赖于另外两个方法:

push(element) {
    // 封装成节点
    const node = new Node(element)
    if(this.isEmpty()){
        this.head = node
        this.count++
        return
    }
    const lastNode = this.getNodeAt(this.count - 1)
    lastNode.next = node
    this.count++
}

第二种实现,不依赖其他方法:

push(element) {
    // 封装成节点
    const node = new Node(element)
    if(this.head === undefined){
        this.head = node
        this.count++
        return
    }
    // 取得最后一个节点,并将其引用指向新的节点
    let lastNode = this.head
    while(lastNode.next){
        lastNode = lastNode.next
    }
    lastNode.next = node
    this.count++
}

从任意位置移除元素

removeAt(index) {
        // index 必须是自然数,即 0、1、2...
        const isNaturalNumber = Number.isInteger(index) && index >= 0
        const outOfBounds = index >= this.count
        // 处理不能删除的情况:非自然数、index 出界,都不做处理
        if (!isNaturalNumber || outOfBounds) {
            return
        }

        let current
        // 删除第一项
        if (Object.is(index, 0)) {
            current = this.head
            this.head = current.next
        } else {  // 删除中间项或最后一项
            let prev = this.getNodeAt(index - 1)
            current = prev.next
            prev.next = current.next
        }
        this.count--
        return current.element
    }

如果不需要依赖 getNodeAt 方法,可以这样:

removeAt(index) {
    ...

    let current = this.head
    // 删除第一项
    if (Object.is(index, 0)) {
        this.head = current.next
    } else {  // 删除中间项或最后一项
        let prev
        while(index--){
            prev = current
            current = prev.next
        }
        prev.next = current.next
    }

    ...
}

取得特定位置的节点

首先排除无效的索引(index),逻辑和 removeAt 中的相同:

getNodeAt(index) {
    // index 必须是自然数,即 0、1、2...
    const isNaturalNumber = Number.isInteger(index) && index >= 0
    const outOfBounds = index >= this.count
    // 处理不能取得节点的情况:非自然数、index 出界,都不做处理
    if (!isNaturalNumber || outOfBounds) {
        return
    }

    let current = this.head
    while (index--) {
        current = current.next
    }
    return current
}

在任意位置插入新元素

insert(element, index) {
    // 参数不合法
    const isNaturalNumber = Number.isInteger(index) && index >= 0
    const outOfBounds = index > this.count
    if (!isNaturalNumber || outOfBounds) {
        return
    }
    
    const newNode = new Node(element)
    // 链表为空
    if (Object.is(this.head, undefined)) {
        this.head = newNode
    } else if (Object.is(index, 0)) { // 插入第一项
        newNode.next = this.head
        this.head = newNode
    } else if (Object.is(index, this.count)) { // 插入最后一项
        const lastNode = this.getNodeAt(index - 1)
        lastNode.next = newNode
    } else { // 插入中间
        const prev = this.getNodeAt(index - 1)
        newNode.next = prev.next
        prev.next = newNode
    }
    this.count++
}

其中前两种逻辑可以合并,后面插入最后一项以及插入中间也可以合并成一个逻辑:

insert(element, index) {
    ...
    const newNode = new Node(element)
    if (Object.is(index, 0)) { // 链表为空 & 插入第一项
        newNode.next = this.head
        this.head = newNode
    } else { // 插入中间以及插入最后一项
        const prev = this.getNodeAt(index - 1)
        newNode.next = prev.next
        prev.next = newNode
    }
    ...
}

元素在链表中的索引

indexOf(element) {
    let result = -1
    let current = this.head
    let { count } = this
    let i = 0
    while (i < count) {
        if (this.equalsFn(current.element, element)) {
            result = i
            break
        }
        current = current.next
        i++
    }
    return result
}

改成 for 循环更显简洁:

indexOf(element) {
    let current = this.head
    for(let i = 0, count = this.count; i < count; i++){
        if (this.equalsFn(current.element, element)) {
            return i
        }
        current = current.next
    }
    return -1
}

其他方法

Tip:剩下的几个方法都比较简单,就放在一起介绍

  • 从链表中移除一个元素
remove(element){
    const index = this.indexOf(element)
    return this.removeAt(index)
}
  • size()isEmpty()
size(){
    return this.count
}
isEmpty(){
    return this.count === 0
}
  • 返回表示链表的字符串
toString(){
    if(this.isEmpty()){
        return ''
    }

    let elements = []
    let current = this.head
    while(current){
        elements.push(current.element)
        current = current.next
    }
    return elements.join(',')
}

使用 LinkedList 类

class Node {
    constructor(element) {
        this.element = element
        this.next = undefined
    }
}

function defaultEquals(a, b) {
    return Object.is(a, b)
}

/**
 * 链表
 * @class LinkedList
 */
class LinkedList {
    constructor(equalsFn = defaultEquals) {
        this.count = 0
        this.head = undefined
        this.equalsFn = equalsFn
    }
    // 向链表尾部添加一个新元素
    push(element) {
        // 封装成节点
        const node = new Node(element)
        if (this.head === undefined) {
            this.head = node
            this.count++
            return
        }
        // 取得最后一个节点,并将其引用指向新的节点
        let lastNode = this.head
        while (lastNode.next) {
            lastNode = lastNode.next
        }
        lastNode.next = node
        this.count++
    }
    // 从链表中删除特定位置的元素
    removeAt(index) {
        // index 必须是自然数,即 0、1、2...
        const isNaturalNumber = Number.isInteger(index) && index >= 0
        const outOfBounds = index >= this.count
        // 处理不能删除的情况:非自然数、index 出界,都不做处理
        if (!isNaturalNumber || outOfBounds) {
            return
        }

        let current = this.head
        // 删除第一项
        if (Object.is(index, 0)) {
            this.head = current.next
        } else {  // 删除中间项或最后一项
            let prev
            while (index--) {
                prev = current
                current = prev.next
            }
            prev.next = current.next
        }
        this.count--
        return current.element
    }
    getNodeAt(index) {
        // index 必须是自然数,即 0、1、2...
        const isNaturalNumber = Number.isInteger(index) && index >= 0
        const outOfBounds = index >= this.count
        // 处理不能删除的情况:非自然数、index 出界,都不做处理
        if (!isNaturalNumber || outOfBounds) {
            return
        }

        let current = this.head
        while (index--) {
            current = current.next
        }
        return current
    }
    getElementAt(index) {
        const result = this.getNodeAt(index)
        return result ? result.element : result
    }

    // 向链表特定位置插入一个新元素
    insert(element, index) {
        // 参数不合法
        const isNaturalNumber = Number.isInteger(index) && index >= 0
        const outOfBounds = index > this.count
        if (!isNaturalNumber || outOfBounds) {
            return false
        }

        const newNode = new Node(element)
        if (Object.is(index, 0)) { // 链表为空 & 插入第一项
            newNode.next = this.head
            this.head = newNode
        } else { // 插入中间以及插入最后一项
            const prev = this.getNodeAt(index - 1)
            newNode.next = prev.next
            prev.next = newNode
        }
        this.count++
        return true
    }

    indexOf(element) {
        let current = this.head
        for (let i = 0, count = this.count; i < count; i++) {
            if (this.equalsFn(current.element, element)) {
                return i
            }
            current = current.next
        }
        return -1
    }

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

    size() {
        return this.count
    }

    isEmpty() {
        return this.count === 0
    }

    toString() {
        if (this.isEmpty()) {
            return ''
        }

        let elements = []
        let current = this.head
        while (current) {
            elements.push(current.element)
            current = current.next
        }
        return elements.join(',')
    }
}
class Dog {
    constructor(name) {
        this.name = name
    }
    toString() {
        return this.name
    }
}

let linkedlist = new LinkedList()
console.log(linkedlist.isEmpty()) // true
linkedlist.push(1)
console.log(linkedlist.isEmpty()) // false
linkedlist.push(2)
console.log(linkedlist.toString()) // 1,2

linkedlist.insert(3, 0) // 在索引 0 处插入元素 3
linkedlist.insert(4, 3)
linkedlist.insert(5, 5) // 插入失败
console.log(linkedlist.toString()) // 3,1,2,4

let i = linkedlist.indexOf(3)
let j = linkedlist.indexOf(4)
console.log('i: ', i) // i:  0
console.log('j: ', j) // j:  3

let dog1 = new Dog('a')
linkedlist.push(dog1)
console.log(linkedlist.toString()) // 3,1,2,4,a
let k = linkedlist.indexOf(dog1)
console.log('k: ', k) // k:  4
let m = linkedlist.getElementAt(0)
console.log('m: ', m) // m:  3
linkedlist.remove(dog1)
linkedlist.removeAt(0)
console.log(linkedlist.toString()) // 1,2,4
let l = linkedlist.size()
console.log('l: ', l) // l:  3

双向链表

链表有多种类型,双向链表提供两种迭代方法:从头到尾,或者从尾到头。

在双向链表中,相对于链表,每一项都新增了一个 prev 引用。还有 tail 引用,用于从尾部迭代到头部。就像这样:

                      Node                   Node                      node           
head -> [prev(undefined) | value | next] <->  ... <-> [prev | value | next(undefined)] <- tail

Tip:在单向链表中,如果错过了要找的元素,就需要重新回到起点,重新迭代。而双向链表则没有这个问题

创建双向链表

我们先从最基础的开始,创建 DoubleNode 类和 DoubleLinkedList 类:

// 双向链表中的节点
class DoubleNode extends Node {
    constructor(element) {
        super(element)
        this.prev = undefined
    }
}

// 双向链表
class DoubleLinkedList extends LinkedList {
    constructor(equalsFn = defaultEquals) {
        super(equalsFn)
        this.tail = undefined
    }
}

:因为双向链表对于链表来说,只是增加了从尾部遍历到头部的特性,所以双向链表的方法和链表的方法其实是相同的(也是 10 个方法)

在任意位置插入新元素

我们直接在 LinkedList 类中 insert 方法的基础上修改一下即可:

  • 对于不能插入的情况,即“参数不合法”部分,无需修改
  • 节点的创建,改为 DoubleNode
  • 插入分4种情况
insert(element, index) {
    // 参数不合法
    const isNaturalNumber = Number.isInteger(index) && index >= 0
    const outOfBounds = index > this.count
    if (!isNaturalNumber || outOfBounds) {
        return false
    }

    const newNode = new DoubleNode(element)
    // 链表为空
    if (Object.is(this.head, undefined)) {
        this.head = newNode
        this.tail = newNode
    } else if (Object.is(index, 0)) { // 插入第一项
        newNode.next = this.head
        this.head.prev = newNode
        this.head = newNode
    } else if (Object.is(index, this.count)) { // 插入最后一项
        newNode.prev = this.tail
        this.tail.next = newNode
        this.tail = newNode
    } else { // 插入中间
        const prev = this.getNodeAt(index - 1)
        newNode.next = prev.next
        prev.next.prev = newNode
        prev.next = newNode
        newNode.prev = prev
    }
    this.count++
    return true
}

从任意位置移除元素

我们直接在 LinkedList 类中 removeAt 方法的基础上修改一下即可:

  • 对于不能删除的情况,即“参数不合法”部分,无需修改
  • 删除的场景从2种改为4种
// 从链表中删除特定位置的元素
removeAt(index) {
    // index 必须是自然数,即 0、1、2...
    const isNaturalNumber = Number.isInteger(index) && index >= 0
    const outOfBounds = index >= this.count
    // 处理不能删除的情况:非自然数、index 出界,都不做处理
    if (!isNaturalNumber || outOfBounds) {
        return
    }

    let current = this.head

    // 第一项&唯一
    if (Object.is(this.size(), 1)) {
        this.head = undefined
        this.tail = undefined
    } else if (Object.is(index, 0)) { // 第一项
        this.head = current.next
        current.next.prev = undefined
    } else if (Object.is(index, this.size() - 1)) { // 最后一项
        this.tail = this.tail.prev
        this.tail.next = undefined
    } else { // 中间项
        current = this.getNodeAt(index)
        const prev = current.prev
        const next = current.next
        prev.next = next
        next.prev = prev
    }
    this.count--
    return current.element
}

其他方法

  • push() 实现比较简单:
// 在 LinkedList 的 push 方法基础上修改即可
// 也是分链表为空和不为空的情况
// 这个方法还可以调用 insert 实现
push(element) {
    // 封装成节点
    const newNode = new DoubleNode(element)
    if (this.isEmpty()) {
        this.head = newNode
        this.tail = newNode
        this.count++
        return
    }
    this.tail.next = newNode
    newNode.prev = this.tail
    this.tail = newNode
    this.count++
}
  • getNodeAt() 其实可以使用 LinkedList 中的 getNodeAt() 方法,这里稍微优化一下:
// 如果 index 大于 count/2,就可以从尾部开始迭代,而不是从头开始(这样就能迭代更少的元素)
getNodeAt(index) {
    // index 必须是自然数,即 0、1、2...
    const isNaturalNumber = Number.isInteger(index) && index >= 0
    const outOfBounds = index >= this.count
    // 处理不能取得节点的情况:非自然数、index 出界,都不做处理
    if (!isNaturalNumber || outOfBounds) {
        return
    }

    let current = this.head
    let isPositiveOrder = index < (this.count / 2)
    let indexMethod = 'next'
    let count = index
    if (!isPositiveOrder) {
        count = this.count - 1 - index
        indexMethod = 'prev'
    }
    while (count--) {
        current = current[indexMethod]
    }
    return current
}

剩余的方法直接调用父类:indexOftoStringremovesizeisEmptygetElementAt

使用 DoubleLinkedList 类

/**
 * 双向链表中的节点
 *
 * @class DoubleNode
 * @extends {Node}
 */
class DoubleNode extends Node {
    constructor(element) {
        super(element)
        this.prev = undefined
    }
}

/**
 * 双向链表
 * 此类有10个方法,6个来自父类,4个重写了父类的方法
 * @class DoubleLinkedList
 * @extends {LinkedList}
 */
class DoubleLinkedList extends LinkedList {
    constructor(equalsFn = defaultEquals) {
        super(equalsFn)
        this.tail = undefined
    }
    // 向链表特定位置插入一个新元素
    insert(element, index) {
        // 参数不合法
        const isNaturalNumber = Number.isInteger(index) && index >= 0
        const outOfBounds = index > this.count
        if (!isNaturalNumber || outOfBounds) {
            return false
        }

        const newNode = new DoubleNode(element)
        // 链表为空
        if (Object.is(this.head, undefined)) {
            this.head = newNode
            this.tail = newNode
        } else if (Object.is(index, 0)) { // 插入第一项
            newNode.next = this.head
            this.head.prev = newNode
            this.head = newNode
        } else if (Object.is(index, this.count)) { // 插入最后一项
            newNode.prev = this.tail
            this.tail.next = newNode
            this.tail = newNode
        } else { // 插入中间
            const prev = this.getNodeAt(index - 1)
            newNode.next = prev.next
            prev.next.prev = newNode
            prev.next = newNode
            newNode.prev = prev
        }
        this.count++
        return true
    }
    // 从链表中删除特定位置的元素
    removeAt(index) {
        // index 必须是自然数,即 0、1、2...
        const isNaturalNumber = Number.isInteger(index) && index >= 0
        const outOfBounds = index >= this.count
        // 处理不能删除的情况:非自然数、index 出界,都不做处理
        if (!isNaturalNumber || outOfBounds) {
            return
        }

        let current = this.head

        // 第一项&唯一
        if (Object.is(this.size(), 1)) {
            this.head = undefined
            this.tail = undefined
        } else if (Object.is(index, 0)) { // 第一项
            this.head = current.next
            current.next.prev = undefined
        } else if (Object.is(index, this.size() - 1)) { // 最后一项
            this.tail = this.tail.prev
            this.tail.next = undefined
        } else { // 中间项
            current = this.getNodeAt(index)
            const prev = current.prev
            const next = current.next
            prev.next = next
            next.prev = prev
        }
        this.count--
        return current.element
    }
    // 在 LinkedList 的 push 方法基础上修改即可
    // 也是分链表为空和不为空的情况
    // 这个方法还可以调用 insert 实现
    push(element) {
        // 封装成节点
        const newNode = new DoubleNode(element)
        if (this.isEmpty()) {
            this.head = newNode
            this.tail = newNode
            this.count++
            return
        }
        this.tail.next = newNode
        newNode.prev = this.tail
        this.tail = newNode
        this.count++
    }
    // 其实可以使用 LinkedList 中的 getNodeAt() 方法,这里稍微优化一下
    // 如果 index 大于 count/2,就可以从尾部开始迭代,而不是从头开始(这样就能迭代更少的元素)
    getNodeAt(index) {
        // index 必须是自然数,即 0、1、2...
        const isNaturalNumber = Number.isInteger(index) && index >= 0
        const outOfBounds = index >= this.count
        // 处理不能取得节点的情况:非自然数、index 出界,都不做处理
        if (!isNaturalNumber || outOfBounds) {
            return
        }

        let current = this.head
        let isPositiveOrder = index < (this.count / 2)
        let indexMethod = 'next'
        let count = index
        if (!isPositiveOrder) {
            count = this.count - 1 - index
            indexMethod = 'prev'
        }
        while (count--) {
            current = current[indexMethod]
        }
        return current
    }
}

:下面的测试代码和 LinkedList 中的几乎相同,唯一不同的是将 new LinkedList() 改为 new DoubleLinkedList()

class Dog {
    constructor(name) {
        this.name = name
    }
    toString() {
        return this.name
    }
}

let linkedlist = new DoubleLinkedList()
console.log(linkedlist.isEmpty()) // true
linkedlist.push(1)
console.log(linkedlist.isEmpty()) // false
linkedlist.push(2)
console.log(linkedlist.toString()) // 1,2

linkedlist.insert(3, 0) // 在索引 0 处插入元素 3
linkedlist.insert(4, 3)
linkedlist.insert(5, 5) // 插入失败
console.log(linkedlist.toString()) // 3,1,2,4

let i = linkedlist.indexOf(3)
let j = linkedlist.indexOf(4)
console.log('i: ', i) // i:  0
console.log('j: ', j) // j:  3

let dog1 = new Dog('a')
linkedlist.push(dog1)
console.log(linkedlist.toString()) // 3,1,2,4,a
let k = linkedlist.indexOf(dog1)
console.log('k: ', k) // k:  4
let m = linkedlist.getElementAt(0)
console.log('m: ', m) // m:  3
linkedlist.remove(dog1)
linkedlist.removeAt(0)
console.log(linkedlist.toString()) // 1,2,4
let l = linkedlist.size()
console.log('l: ', l) // l:  3

循环链表

循环链表可以基于单项链表,也可以基于双向链表。

以单项链表为基础,只需要将链表中最后一个节点的 next 指向第一个节点,就是循环链表

如果以双向链表为基础,则需要将最后一个节点的 next 指向第一个节点,第一个节点的 prev 指向最后一个节点

基于单项链表的循环链表

直接继承 LinkedList,不需要增加额外的属性,就像这样:

class CircularLinkedList extends LinkedList{
    constructor(equalsFn = defaultEquals) {
        super(equalsFn)
    }
}

Tip:剩余部分,可自行重写相应的方法即可,笔者就不在展开。

有序链表

有序链表是指保持元素有序的链表结构。

所以我们只需要继承 LinkedList 类,并重写和插入相关的两个方法即可:

// 默认比较的方法
function defaultCompare(a, b) {
    return a - b
}

/**
 * 有序链表
 * 重写2个方法,保证元素插入到正确的位置,保证链表的有序性
 * @class SortedLinkedList
 * @extends {LinkedList}
 */
class SortedLinkedList extends LinkedList {
    constructor(equalsFn = defaultEquals, compareFn = defaultCompare) {
        super(equalsFn)
        this.compareFn = compareFn
    }
    push(element) {
        this.insert(element)
    }
    // 不允许在任意位置插入
    insert(element) {
        if (this.isEmpty()) {
            return super.insert(element, 0)
        }

        let current = this.head
        let position = 0
        for (let count = this.size(); position < count; position++) {
            if (this.compareFn(element, current.element) < 0) {
                return super.insert(element, position)
            }
            current = current.next
        }
        return super.insert(element, position)
    }
}

Tip:其中 defaultEqualsLinkedList 类中已经实现过:

function defaultEquals(a, b) {
    return Object.is(a, b)
}

测试代码如下:

let linkedlist = new SortedLinkedList()
linkedlist.insert(3)
console.log(linkedlist.toString()) // 3
linkedlist.insert(2)
linkedlist.insert(1)
linkedlist.push(0)
console.log(linkedlist.toString()) // 0,1,2,3

基于链表的栈

我们可以使用链表作为内部数据结构来创建其他数据结构,例如栈、队列等

比如我们用 LinkedList 作为 Stack 的内部数据结构,用于创建 StackLinkedList

/**
 * 基于链表的栈
 *
 * @class StackLinkedList
 */
class StackLinkedList {
    constructor() {
        this.items = new LinkedList()
    }
    push(...values) {
        values.forEach(item => {
            this.items.push(item)
        })
    }
    toString() {
        return this.items.toString()
    }
    // todo 其他方法 
}
let stack = new StackLinkedList()
stack.push(1, 3, 5)
console.log(stack.toString()) // 1,3,5

Tip:我们还可以对 LinkedList 类优化,保存一个指向尾部元素的引用

链表完整代码

Tip:笔者是在 node 环境下进行

LinkedList.js


/**
 * 链表的节点
 *
 * @class Node
 */
class Node {
    constructor(element) {
        this.element = element
        this.next = undefined
    }
}

function defaultEquals(a, b) {
    return Object.is(a, b)
}

/**
 * 链表
 * @class LinkedList
 */
class LinkedList {
    constructor(equalsFn = defaultEquals) {
        this.count = 0
        this.head = undefined
        this.equalsFn = equalsFn
    }
    // 向链表尾部添加一个新元素
    push(element) {
        // 封装成节点
        const node = new Node(element)
        if (this.head === undefined) {
            this.head = node
            this.count++
            return
        }
        // 取得最后一个节点,并将其引用指向新的节点
        let lastNode = this.head
        while (lastNode.next) {
            lastNode = lastNode.next
        }
        lastNode.next = node
        this.count++
    }
    // 从链表中删除特定位置的元素
    removeAt(index) {
        // index 必须是自然数,即 0、1、2...
        const isNaturalNumber = Number.isInteger(index) && index >= 0
        const outOfBounds = index >= this.count
        // 处理不能删除的情况:非自然数、index 出界,都不做处理
        if (!isNaturalNumber || outOfBounds) {
            return
        }

        let current = this.head
        // 删除第一项
        if (Object.is(index, 0)) {
            this.head = current.next
        } else {  // 删除中间项或最后一项
            let prev
            while (index--) {
                prev = current
                current = prev.next
            }
            prev.next = current.next
        }
        this.count--
        return current.element
    }
    getNodeAt(index) {
        // index 必须是自然数,即 0、1、2...
        const isNaturalNumber = Number.isInteger(index) && index >= 0
        const outOfBounds = index >= this.count
        // 处理不能取得节点的情况:非自然数、index 出界,都不做处理
        if (!isNaturalNumber || outOfBounds) {
            return
        }

        let current = this.head
        while (index--) {
            current = current.next
        }
        return current
    }
    getElementAt(index) {
        const result = this.getNodeAt(index)
        return result ? result.element : result
    }

    // 向链表特定位置插入一个新元素
    insert(element, index) {
        // 参数不合法
        const isNaturalNumber = Number.isInteger(index) && index >= 0
        const outOfBounds = index > this.count
        if (!isNaturalNumber || outOfBounds) {
            return false
        }

        const newNode = new Node(element)
        if (Object.is(index, 0)) { // 链表为空 & 插入第一项
            newNode.next = this.head
            this.head = newNode
        } else { // 插入中间以及插入最后一项
            const prev = this.getNodeAt(index - 1)
            newNode.next = prev.next
            prev.next = newNode
        }
        this.count++
        return true
    }

    indexOf(element) {
        let current = this.head
        for (let i = 0, count = this.count; i < count; i++) {
            if (this.equalsFn(current.element, element)) {
                return i
            }
            current = current.next
        }
        return -1
    }

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

    size() {
        return this.count
    }

    isEmpty() {
        return this.count === 0
    }

    toString() {
        if (this.isEmpty()) {
            return ''
        }

        let elements = []
        let current = this.head
        while (current) {
            elements.push(current.element)
            current = current.next
        }
        return elements.join(',')
    }
}


/**
 * 双向链表中的节点
 *
 * @class DoubleNode
 * @extends {Node}
 */
class DoubleNode extends Node {
    constructor(element) {
        super(element)
        this.prev = undefined
    }
}

/**
 * 双向链表
 * 此类有10个方法,6个来自父类,4个重写了父类的方法
 * @class DoubleLinkedList
 * @extends {LinkedList}
 */
class DoubleLinkedList extends LinkedList {
    constructor(equalsFn = defaultEquals) {
        super(equalsFn)
        this.tail = undefined
    }
    // 向链表特定位置插入一个新元素
    insert(element, index) {
        // 参数不合法
        const isNaturalNumber = Number.isInteger(index) && index >= 0
        const outOfBounds = index > this.count
        if (!isNaturalNumber || outOfBounds) {
            return false
        }

        const newNode = new DoubleNode(element)
        // 链表为空
        if (Object.is(this.head, undefined)) {
            this.head = newNode
            this.tail = newNode
        } else if (Object.is(index, 0)) { // 插入第一项
            newNode.next = this.head
            this.head.prev = newNode
            this.head = newNode
        } else if (Object.is(index, this.count)) { // 插入最后一项
            newNode.prev = this.tail
            this.tail.next = newNode
            this.tail = newNode
        } else { // 插入中间
            const prev = this.getNodeAt(index - 1)
            newNode.next = prev.next
            prev.next.prev = newNode
            prev.next = newNode
            newNode.prev = prev
        }
        this.count++
        return true
    }
    // 从链表中删除特定位置的元素
    removeAt(index) {
        // index 必须是自然数,即 0、1、2...
        const isNaturalNumber = Number.isInteger(index) && index >= 0
        const outOfBounds = index >= this.count
        // 处理不能删除的情况:非自然数、index 出界,都不做处理
        if (!isNaturalNumber || outOfBounds) {
            return
        }

        let current = this.head

        // 第一项&唯一
        if (Object.is(this.size(), 1)) {
            this.head = undefined
            this.tail = undefined
        } else if (Object.is(index, 0)) { // 第一项
            this.head = current.next
            current.next.prev = undefined
        } else if (Object.is(index, this.size() - 1)) { // 最后一项
            this.tail = this.tail.prev
            this.tail.next = undefined
        } else { // 中间项
            current = this.getNodeAt(index)
            const prev = current.prev
            const next = current.next
            prev.next = next
            next.prev = prev
        }
        this.count--
        return current.element
    }
    // 在 LinkedList 的 push 方法基础上修改即可
    // 也是分链表为空和不为空的情况
    // 这个方法还可以调用 insert 实现
    push(element) {
        // 封装成节点
        const newNode = new DoubleNode(element)
        if (this.isEmpty()) {
            this.head = newNode
            this.tail = newNode
            this.count++
            return
        }
        this.tail.next = newNode
        newNode.prev = this.tail
        this.tail = newNode
        this.count++
    }
    // 其实可以使用 LinkedList 中的 getNodeAt() 方法,这里稍微优化一下
    // 如果 index 大于 count/2,就可以从尾部开始迭代,而不是从头开始(这样就能迭代更少的元素)
    getNodeAt(index) {
        // index 必须是自然数,即 0、1、2...
        const isNaturalNumber = Number.isInteger(index) && index >= 0
        const outOfBounds = index >= this.count
        // 处理不能取得节点的情况:非自然数、index 出界,都不做处理
        if (!isNaturalNumber || outOfBounds) {
            return
        }

        let current = this.head
        let isPositiveOrder = index < (this.count / 2)
        let indexMethod = 'next'
        let count = index
        if (!isPositiveOrder) {
            count = this.count - 1 - index
            indexMethod = 'prev'
        }
        while (count--) {
            current = current[indexMethod]
        }
        return current
    }
}


/**
 * 循环链表
 * todo
 * @class CircularLinkedList
 * @extends {LinkedList}
 */
class CircularLinkedList extends LinkedList {
    constructor(equalsFn = defaultEquals) {
        super(equalsFn)
    }
}

// 默认比较的方法
function defaultCompare(a, b) {
    return a - b
}

/**
 * 有序链表
 * 重写2个方法,保证元素插入到正确的位置,保证链表的有序性
 * @class SortedLinkedList
 * @extends {LinkedList}
 */
class SortedLinkedList extends LinkedList {
    constructor(equalsFn = defaultEquals, compareFn = defaultCompare) {
        super(equalsFn)
        this.compareFn = compareFn
    }
    push(element) {
        this.insert(element)
    }
    // 不允许在任意位置插入
    insert(element) {
        if (this.isEmpty()) {
            return super.insert(element, 0)
        }

        let current = this.head
        let position = 0
        for (let count = this.size(); position < count; position++) {
            if (this.compareFn(element, current.element) < 0) {
                return super.insert(element, position)
            }
            current = current.next
        }
        return super.insert(element, position)
    }
}

/**
 * 基于链表的栈
 *
 * @class StackLinkedList
 */
class StackLinkedList {
    constructor() {
        this.items = new LinkedList()
    }
    push(...values) {
        values.forEach(item => {
            this.items.push(item)
        })
    }
    toString() {
        return this.items.toString()
    }
    // todo 其他方法 
}
module.exports = { LinkedList, DoubleLinkedList, SortedLinkedList, StackLinkedList }

test.js

const { LinkedList, DoubleLinkedList, SortedLinkedList, StackLinkedList } = require('./LinkedList')

let stack = new StackLinkedList()
stack.push(1, 3, 5)
console.log(stack.toString()) // 1,3,5
    原文作者:彭加李
    原文地址: https://www.cnblogs.com/pengjiali/p/15320535.html
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。