数据结构与算法JavaScript描述（4） —— 链表（LinkedList ）

单向链表

链表是由一组节点组成的集合。每个节点都使用一个对象的引用指向它的后继。指向另一个节点的引用叫做链。

实现：

class Node {
    constructor(val) {
        this.val = val      // 节点数据
        this.next = null        // 指向下一个节点的链接
    }
}

class LinkedList {

    constructor() {
        this.head = new Node('head')
        this.length = 0         // 链表的长度，默认为0，不算头节点
    }

    get isEmpty() {
        return !this.length
    }

    // 遍历链表，查找指定索引节点
    find(val) {
        let curNode = this.head
        while(curNode.val !== val) {
            curNode = curNode.next
        }
        return curNode
    }

    // 查找指定节点的索引
    findIndex(val) {
        let curNode = this.head
        let index = -1
        while(curNode.val !== val) {
            curNode = curNode.next
            index++
        }
        if (index == this.length) return -1
        return index
    }

    // 在任意位置插入节点
    insert(position, val) {
        if (position < 0 || position > this.length) return false
        const newNode = new Node(val)
        let curNode = this.head
        let index = 0
        // 找到插入点的节点
        while(index < position) {
            curNode = curNode.next
            index++
        }
        newNode.next = curNode.next
        curNode.next = newNode
        this.length++
        return true
    }

    // 在链表最后插入一个新元素
    append(val) {
        const newNode = new Node(val)
        let curNode = this.head
        while(curNode.next !== null) {
            curNode = curNode.next
        }
        curNode.next = newNode
        this.length++
    }

    // 删除指定位置的节点
    removeAt(position) {
        if (position < 0 || position > this.length) return null
        let curNode = this.head
        let index = 0
        let prevNode = null
        // 找到待删除节点
        while(index <= position) {
            prevNode = curNode
            curNode = curNode.next
            index++
        }
        prevNode.next = curNode.next
        this.length--
        return curNode.val
    }

    // 删除节点
    remove(val) {
        // 找到待删除节点前面的节点，然后修改它的next属性，使其不再指向待删除节点，而是指向待删除节点的下一个节点
        const index = this.findIndex(val)
        return this.removeAt(index)
    }

    toString() {
        let curNode = this.head
        let str = ''
        while(curNode.next !== null) {
            str += curNode.next.val + ', '
            curNode = curNode.next
        }
        return str.slice(0, -2)
    }
}

测试：

// test
const cities = new LinkedList()
cities.insert(0, 'BeiJing')
cities.insert(1, 'ShangHai')
cities.insert(0, 'ChongQing')
console.log(cities.toString())      // ChongQing, BeiJing, ShangHai
cities.remove('BeiJing')
console.log(cities.toString())      // ChongQing, ShangHai
console.log(cities.length)              // 2
cities.removeAt(1)
console.log(cities.toString())      // ChongQing
cities.append('GuangZhou')
console.log(cities.toString())      // ChongQing, GuangZhou

双向链表

与普通列表类似，只是多了一个指向前驱节点的链接。

实现：

class Node {
    constructor(val) {
        this.val = val      // 节点数据
        this.next = null        // 指向下一个节点的链接
        this.prev = null    // 指向前一个节点
    }
}

class DbLinkedList {

    constructor() {
        this.head = new Node('head')
        this.current = this.head
        this.length = 0         // 链表的长度，默认为0，不算头节点
    }

    get isEmpty() {
        return !this.length
    }

    // 遍历链表，查找指定索引节点
    find(val) {
        let curNode = this.head
        while(curNode.val !== val) {
            curNode = curNode.next
        }
        return curNode
    }

    // 查找最后的节点
    findLast() {
        let curNode = this.head
        while(curNode.next !== null) {
            curNode = curNode.next
        }
        return curNode
    }

    // 查找指定节点的索引
    findIndex(val) {
        let curNode = this.head
        let index = -1
        while(curNode.val !== val) {
            curNode = curNode.next
            index++
        }
        if (index == this.length) return -1
        return index
    }

    // 在任意位置插入节点
    insert(position, val) {
        if (position < 0 || position > this.length) return false
        const newNode = new Node(val)
        let curNode = this.head
        let index = 0
        // 找到插入点的节点
        while(index < position) {
            curNode = curNode.next
            index++
        }
        newNode.next = curNode.next
        newNode.prev = curNode
        if (curNode.next && curNode.next.prev) {
            curNode.next.prev = newNode
        }
        curNode.next = newNode
        this.length++
        return true
    }

    // 在链表最后插入一个新元素
    append(val) {
        const newNode = new Node(val)
        let curNode = this.head
        while(curNode.next !== null) {
            curNode = curNode.next
        }
        curNode.next = newNode
        newNode.prev = curNode
        this.length++
    }

    // 删除指定位置的节点
    removeAt(position) {
        if (position < 0 || position > this.length) return null
        let curNode = this.head
        let index = 0
        let prevNode = null
        // 找到待删除节点
        while(index <= position) {
            prevNode = curNode
            curNode = curNode.next
            index++
        }
        prevNode.next = curNode.next
        curNode.next.prev = prevNode
        curNode.prev = null
        curNode.next = null
        this.length--
        return curNode.val
    }

    // 删除节点
    remove(val) {
        // 找到待删除节点前面的节点，然后修改它的next属性，使其不再指向待删除节点，而是指向待删除节点的下一个节点
        const index = this.findIndex(val)
        return this.removeAt(index)
    }

    toString() {
        let curNode = this.head
        let str = ''
        while(curNode.next !== null) {
            str += curNode.next.val + ', '
            curNode = curNode.next
        }
        return str.slice(0, -2)
    }

    display() {
        console.log(this.toString())
    }

    displayReverse() {
        const data = this.toString().split(', ').reverse().join(', ')
        console.log(data)
    }

    // 在链表中向前移动 n 个节点
    advance(n) {
        while(n > 0 && this.current.next !== null) {
            this.current = this.current.next
            n--
        }
    }

    // 在双向链表中后退 n 个节点
    back(n) {
        while(n > 0 && this.current.val !== 'head') {
            this.current = this.current.prev
            n--
        }
    }

    // 只显示当前节点
    show() {
        console.log(this.current)
    }
}

测试：

const cities = new DbLinkedList()
cities.insert(0, 'BeiJing')
cities.insert(1, 'ShangHai')
cities.insert(0, 'ChongQing')
cities.append('GuangZhou')
cities.append('TianJin')
cities.append('Taiwan')
cities.display()                            // ChongQing, BeiJing, ShangHai, GuangZhou, TianJin, Taiwan
cities.remove('BeiJing')
cities.display()                            // ChongQing, ShangHai, GuangZhou, TianJin, Taiwan
cities.removeAt(1)
cities.display()                            // ChongQing, GuangZhou, TianJin, Taiwan
cities.displayReverse()             // Taiwan, TianJin, GuangZhou, ChongQing
cities.show()
cities.advance(2)
cities.show()                                   // Node {val: "GuangZhou", next: Node, prev: Node}
cities.back(1)
cities.show()                                   // Node {val: "ChongQing", next: Node, prev: Node}

循环链表

循环链表和单向链表相似，节点类型都是一样的。唯一的区别是，在创建循环链表时，让其头节点的 next 属性指向它本身，即: head.next = head

实现：

class Node {
    constructor(val) {
        this.val = val      // 节点数据
        this.next = null        // 指向下一个节点的链接
    }
}

class CircularLinkedList {
    constructor() {
        this.head = new Node('head')
        this.length = 0         // 链表的长度，默认为0，不算头节点
        this.current = this.head
    }

    get isEmpty() {
        return !this.length
    }

    // 遍历链表，查找指定索引节点
    find(val) {
        let curNode = this.head
        while(curNode.val !== val && curNode.next.val !== 'head') {
            curNode = curNode.next
        }
        return curNode
    }

    // 查找指定节点的索引
    findIndex(val) {
        let curNode = this.head
        let index = -1
        while(curNode.val !== val && curNode.next.val !== 'head') {
            curNode = curNode.next
            index++
        }
        if (index == this.length) return -1
        return index
    }

    // 查找最后的节点
    findLast() {
        let curNode = this.head
        while(curNode.next !== null && curNode.next.val !== 'head') {
            curNode = curNode.next
        }
        return curNode
    }

    // 在任意位置插入节点
    insert(position, val) {
        if (position < 0 || position > this.length) return false
        const newNode = new Node(val)
        let curNode = this.head
        let index = 0
        // 找到插入点的节点
        while(index < position) {
            curNode = curNode.next
            index++
        }
        newNode.next = curNode.next
        curNode.next = newNode
        // 链表的尾节点指向头节点
        const lastNode = this.findLast()
        lastNode.next = this.head
        this.length++
        return true
    }

    // 在链表最后插入一个新元素
    append(val) {
        const newNode = new Node(val)
        let curNode = this.head
        while(curNode.next !== null && curNode.next.val !== 'head') {
            curNode = curNode.next
        }
        curNode.next = newNode
        // 链表的尾节点指向头节点
        newNode.next = this.head
        this.length++
    }

    // 删除指定位置的节点
    removeAt(position) {
        if (position < 0 || position > this.length) return null
        let curNode = this.head
        let index = 0
        let prevNode = null
        // 找到待删除节点
        while(index <= position) {
            prevNode = curNode
            curNode = curNode.next
            index++
        }
        prevNode.next = curNode.next
        this.length--
        return curNode.val
    }

    // 删除节点
    remove(val) {
        // 找到待删除节点前面的节点，然后修改它的next属性，使其不再指向待删除节点，而是指向待删除节点的下一个节点
        const index = this.findIndex(val)
        return this.removeAt(index)
    }

    // 在链表中向前移动 n 个节点
    advance(n) {
        while(n > 0) {
        this.current = this.current.next
        if (this.current.val === 'head') {
            this.current = this.current.next
        }
        n--
    }
    }

    // 只显示当前节点
    show() {
        console.log(this.current)
    }

    display() {
        console.log(this.toString())
    }

    displayReverse() {
        const data = this.toString().split(', ').reverse().join(', ')
        console.log(data)
    }

    toString() {
        let curNode = this.head
        let str = ''
        while(curNode.next !== null && curNode.next.val !== 'head') {
            str += curNode.next.val + ', '
            curNode = curNode.next
        }
        return str.slice(0, -2)
    }
}

测试：

const cities = new CircularLinkedList()
cities.insert(0, 'BeiJing')
cities.insert(1, 'ShangHai')
cities.insert(0, 'ChongQing')
cities.append('GuangZhou')
cities.append('TianJin')
cities.append('Taiwan')
cities.display()                            // ChongQing, BeiJing, ShangHai, GuangZhou, TianJin, Taiwan
cities.remove('BeiJing')
cities.display()                            // ChongQing, ShangHai, GuangZhou, TianJin, Taiwan
cities.removeAt(1)
cities.display()                            // ChongQing, GuangZhou, TianJin, Taiwan
cities.displayReverse()             // Taiwan, TianJin, GuangZhou, ChongQing
cities.advance(2)
cities.show()                                   // Node {val: "GuangZhou", next: Node}

示例：约瑟夫环问题

传说在公元 1 世纪的犹太战争中，犹太历史学家弗拉维奥·约瑟夫斯和他的 40 个同胞被罗马士兵包围。犹太士兵决定宁可自杀也不做俘虏，于是商量出了一个自杀方案。他们围成一个圈，从一个人开始，数到第三个人时将第三个人杀死，然后再数，直到杀光所有人。约瑟夫和另外一个人决定不参加这个疯狂的游戏，他们快速地计算出了两个位置，站在那里得以幸存。写一段程序将 n 个人围成一圈，并且第 m 个人会被杀掉，计算一圈人中哪两个人最后会存活。使用循环链表解决该问题。

/**
 * @param { Number } n  // 总人数
 * @param { Number } m  // 间隔人数
 * @return { String }
 */
function game(n, m) {
    var links = new CircularLinkedList()
    links.insert(0, 1)
    var sign = 2
    // 生成循环链表
    while(sign <= n) {
        links.insert(sign - 1, sign)
        sign++
    }
    // 循环遍历，直到剩余的人数少于间隔数
    while(n >= m) {
        links.advance(m)
        links.remove(links.current.val)
        n--
    }
    links.display()
}

// test
game(40, 3)        // 13, 28

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 206,013评论 6赞 481
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 88,205评论 2赞 382
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 152,370评论 0赞 342
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 55,168评论 1赞 278
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 64,153评论 5赞 371
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,954评论 1赞 283
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 38,271评论 3赞 399
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,916评论 0赞 259
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 43,382评论 1赞 300
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,877评论 2赞 323
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,989评论 1赞 333
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,624评论 4赞 322
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 39,209评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 30,199评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,418评论 1赞 260
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 45,401评论 2赞 352
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,700评论 2赞 345

数据结构与算法JavaScript描述（4） —— 链表（LinkedList ）

单向链表

双向链表

循环链表

推荐阅读更多精彩内容