前往小程序，Get更优阅读体验！
立即前往
文档建议反馈控制台
首页
学习
活动
专区
工具
TVP
最新优惠活动
文章/答案/技术大牛
发布
首页
学习
活动
专区
工具
TVP最新优惠活动
返回腾讯云官网
社区首页 >专栏 >前端学习 数据结构与算法 快速入门 系列 —— 链表(转载非原创)

前端学习 数据结构与算法 快速入门 系列 —— 链表(转载非原创)

作者头像
xlj
修改于 2021-09-23 15:26:01
7781
修改于 2021-09-23 15:26:01
举报
文章被收录于专栏：XLJ的技术专栏XLJ的技术专栏

转载来源:https://www.cnblogs.com/pengjiali/p/15320535.html

链表

链表数据结构

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

就像这样：

代码语言：javascript
复制
// 从头部插入元素
Array.prototype.insertFirst = function (v) {
    for (let i = this.length; i >= 1; i--) {
        this[i] = this[i - 1]
    }
    this[0] = v
}

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

代码语言：javascript
复制
              Node             Node                      Node
head -> [value | next] -> [value | next] -> ... -> [value | next(undefined)]

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

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

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

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

创建链表

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

代码语言：javascript
复制
// 链表中的节点
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：理解了什么是链表，比较容易想到的方法有

  • 插入和删除：push、insert、remove、removeAt
  • 其他：size、isEmpty、toString
向链表尾部添加一个新元素

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

代码语言：javascript
复制
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++
}

第二种实现，不依赖其他方法：

代码语言：javascript
复制
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++
}
从任意位置移除元素
代码语言：javascript
复制
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 方法，可以这样：

代码语言：javascript
复制
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 中的相同：

代码语言：javascript
复制
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
}
在任意位置插入新元素
代码语言：javascript
复制
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++
}

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

代码语言：javascript
复制
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
    }
    ...
}
元素在链表中的索引
代码语言：javascript
复制
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 循环更显简洁：

代码语言：javascript
复制
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：剩下的几个方法都比较简单，就放在一起介绍

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

    let elements = []
    let current = this.head
    while(current){
        elements.push(current.element)
        current = current.next
    }
    return elements.join(',')
}
使用 LinkedList 类
代码语言：javascript
复制
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(',')
    }
}
代码语言：javascript
复制
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 引用，用于从尾部迭代到头部。就像这样：

代码语言：javascript
复制
                      Node                   Node                      node           
head -> [prev(undefined) | value | next] <->  ... <-> [prev | value | next(undefined)] <- tail

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

创建双向链表

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

代码语言：javascript
复制
// 双向链表中的节点
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种情况
代码语言：javascript
复制
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种
代码语言：javascript
复制
// 从链表中删除特定位置的元素
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() 实现比较简单：
代码语言：javascript
复制
// 在 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() 方法，这里稍微优化一下：
代码语言：javascript
复制
// 如果 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
}

剩余的方法直接调用父类：indexOf、toString、remove、size、isEmpty、getElementAt

使用 DoubleLinkedList 类
代码语言：javascript
复制
/**
 * 双向链表中的节点
 *
 * @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()

代码语言：javascript
复制
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，不需要增加额外的属性，就像这样：

代码语言：javascript
复制
class CircularLinkedList extends LinkedList{
    constructor(equalsFn = defaultEquals) {
        super(equalsFn)
    }
}

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

有序链表

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

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

代码语言：javascript
复制
// 默认比较的方法
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：其中 defaultEquals 在 LinkedList 类中已经实现过：

代码语言：javascript
复制
function defaultEquals(a, b) {
    return Object.is(a, b)
}

测试代码如下：

代码语言：javascript
复制
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：

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

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

链表完整代码

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

LinkedList.js
代码语言：javascript
复制
/**
 * 链表的节点
 *
 * @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
代码语言：javascript
复制
const { LinkedList, DoubleLinkedList, SortedLinkedList, StackLinkedList } = require('./LinkedList')

let stack = new StackLinkedList()
stack.push(1, 3, 5)
console.log(stack.toString()) // 1,3,5

本文系转载，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

编程算法
网站
数据结构
java

本文系转载，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

编程算法
网站
数据结构
java
评论
登录后参与评论
0 条评论
热度
最新
登录 后参与评论
推荐阅读
LV.
文章
0
获赞
0
目录
  • 链表
    • 链表数据结构
      • 创建链表
      • 向链表尾部添加一个新元素
      • 从任意位置移除元素
      • 取得特定位置的节点
      • 在任意位置插入新元素
      • 元素在链表中的索引
      • 其他方法
      • 使用 LinkedList 类
    • 双向链表
      • 创建双向链表
      • 在任意位置插入新元素
      • 从任意位置移除元素
      • 其他方法
      • 使用 DoubleLinkedList 类
    • 循环链表
      • 基于单项链表的循环链表
    • 有序链表
      • 基于链表的栈
        • 链表完整代码
          • LinkedList.js
          • test.js
      领券

      腾讯云开发者

      扫码关注腾讯云开发者

      扫码关注腾讯云开发者

      领取腾讯云代金券

      热门产品

      热门推荐

      更多推荐

      Copyright © 2013 - 2024 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有 

      深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 深公网安备号 44030502008569

      腾讯云计算（北京）有限责任公司 京ICP证150476号 |  京ICP备11018762号 | 京公网安备号11010802020287

      问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档

      Copyright © 2013 - 2024 Tencent Cloud.

      All Rights Reserved. 腾讯云 版权所有

      登录 后参与评论
      1