數(shù)據(jù)結構與算法JavaScript描述（4） —— 鏈表（LinkedList ）

單向鏈表

鏈表是由一組節(jié)點組成的集合。每個節(jié)點都使用一個對象的引用指向它的后繼瑞眼。指向另一個節(jié)點的引用叫做鏈。

實現(xiàn)：

class Node {
    constructor(val) {
        this.val = val      // 節(jié)點數(shù)據(jù)
        this.next = null        // 指向下一個節(jié)點的鏈接
    }
}

class LinkedList {

    constructor() {
        this.head = new Node('head')
        this.length = 0         // 鏈表的長度，默認為0妒峦，不算頭節(jié)點
    }

    get isEmpty() {
        return !this.length
    }

    // 遍歷鏈表，查找指定索引節(jié)點
    find(val) {
        let curNode = this.head
        while(curNode.val !== val) {
            curNode = curNode.next
        }
        return curNode
    }

    // 查找指定節(jié)點的索引
    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
    }

    // 在任意位置插入節(jié)點
    insert(position, val) {
        if (position < 0 || position > this.length) return false
        const newNode = new Node(val)
        let curNode = this.head
        let index = 0
        // 找到插入點的節(jié)點
        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++
    }

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

    // 刪除節(jié)點
    remove(val) {
        // 找到待刪除節(jié)點前面的節(jié)點兵睛，然后修改它的next屬性肯骇，使其不再指向待刪除節(jié)點，而是指向待刪除節(jié)點的下一個節(jié)點
        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

雙向鏈表

與普通列表類似祖很，只是多了一個指向前驅節(jié)點的鏈接笛丙。

實現(xiàn)：

class Node {
    constructor(val) {
        this.val = val      // 節(jié)點數(shù)據(jù)
        this.next = null        // 指向下一個節(jié)點的鏈接
        this.prev = null    // 指向前一個節(jié)點
    }
}

class DbLinkedList {

    constructor() {
        this.head = new Node('head')
        this.current = this.head
        this.length = 0         // 鏈表的長度，默認為0假颇，不算頭節(jié)點
    }

    get isEmpty() {
        return !this.length
    }

    // 遍歷鏈表胚鸯，查找指定索引節(jié)點
    find(val) {
        let curNode = this.head
        while(curNode.val !== val) {
            curNode = curNode.next
        }
        return curNode
    }

    // 查找最后的節(jié)點
    findLast() {
        let curNode = this.head
        while(curNode.next !== null) {
            curNode = curNode.next
        }
        return curNode
    }

    // 查找指定節(jié)點的索引
    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
    }

    // 在任意位置插入節(jié)點
    insert(position, val) {
        if (position < 0 || position > this.length) return false
        const newNode = new Node(val)
        let curNode = this.head
        let index = 0
        // 找到插入點的節(jié)點
        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++
    }

    // 刪除指定位置的節(jié)點
    removeAt(position) {
        if (position < 0 || position > this.length) return null
        let curNode = this.head
        let index = 0
        let prevNode = null
        // 找到待刪除節(jié)點
        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
    }

    // 刪除節(jié)點
    remove(val) {
        // 找到待刪除節(jié)點前面的節(jié)點，然后修改它的next屬性笨鸡，使其不再指向待刪除節(jié)點姜钳，而是指向待刪除節(jié)點的下一個節(jié)點
        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 個節(jié)點
    advance(n) {
        while(n > 0 && this.current.next !== null) {
            this.current = this.current.next
            n--
        }
    }

    // 在雙向鏈表中后退 n 個節(jié)點
    back(n) {
        while(n > 0 && this.current.val !== 'head') {
            this.current = this.current.prev
            n--
        }
    }

    // 只顯示當前節(jié)點
    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}

循環(huán)鏈表

循環(huán)鏈表和單向鏈表相似，節(jié)點類型都是一樣的形耗。唯一的區(qū)別是哥桥，在創(chuàng)建循環(huán)鏈表時，讓其頭節(jié)點的 next 屬性指向它本身激涤，即: head.next = head

實現(xiàn)：

class Node {
    constructor(val) {
        this.val = val      // 節(jié)點數(shù)據(jù)
        this.next = null        // 指向下一個節(jié)點的鏈接
    }
}

class CircularLinkedList {
    constructor() {
        this.head = new Node('head')
        this.length = 0         // 鏈表的長度拟糕，默認為0，不算頭節(jié)點
        this.current = this.head
    }

    get isEmpty() {
        return !this.length
    }

    // 遍歷鏈表倦踢，查找指定索引節(jié)點
    find(val) {
        let curNode = this.head
        while(curNode.val !== val && curNode.next.val !== 'head') {
            curNode = curNode.next
        }
        return curNode
    }

    // 查找指定節(jié)點的索引
    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
    }

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

    // 在任意位置插入節(jié)點
    insert(position, val) {
        if (position < 0 || position > this.length) return false
        const newNode = new Node(val)
        let curNode = this.head
        let index = 0
        // 找到插入點的節(jié)點
        while(index < position) {
            curNode = curNode.next
            index++
        }
        newNode.next = curNode.next
        curNode.next = newNode
        // 鏈表的尾節(jié)點指向頭節(jié)點
        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
        // 鏈表的尾節(jié)點指向頭節(jié)點
        newNode.next = this.head
        this.length++
    }

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

    // 刪除節(jié)點
    remove(val) {
        // 找到待刪除節(jié)點前面的節(jié)點送滞，然后修改它的next屬性，使其不再指向待刪除節(jié)點硼一，而是指向待刪除節(jié)點的下一個節(jié)點
        const index = this.findIndex(val)
        return this.removeAt(index)
    }

    // 在鏈表中向前移動 n 個節(jié)點
    advance(n) {
        while(n > 0) {
        this.current = this.current.next
        if (this.current.val === 'head') {
            this.current = this.current.next
        }
        n--
    }
    }

    // 只顯示當前節(jié)點
    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}

示例：約瑟夫環(huán)問題

傳說在公元 1 世紀的猶太戰(zhàn)爭中累澡，猶太歷史學家弗拉維奧·約瑟夫斯和他的 40 個同胞被羅馬士兵包圍。猶太士兵決定寧可自殺也不做俘虜般贼，于是商量出了一個自殺方案愧哟。他們圍成一個圈，從一個人開始哼蛆，數(shù)到第三個人時將第三個人殺死蕊梧，然后再數(shù)，直到殺光所有人腮介。約瑟夫和另外一個人決定不參加這個瘋狂的游戲肥矢，他們快速地計算出了兩個位置，站在那里得以幸存。寫一段程序將 n 個人圍成一圈甘改，并且第 m 個人會被殺掉旅东，計算一圈人中哪兩個人最后會存活。使用循環(huán)鏈表解決該問題十艾。

/**
 * @param { Number } n  // 總人數(shù)
 * @param { Number } m  // 間隔人數(shù)
 * @return { String }
 */
function game(n, m) {
    var links = new CircularLinkedList()
    links.insert(0, 1)
    var sign = 2
    // 生成循環(huán)鏈表
    while(sign <= n) {
        links.insert(sign - 1, sign)
        sign++
    }
    // 循環(huán)遍歷抵代，直到剩余的人數(shù)少于間隔數(shù)
    while(n >= m) {
        links.advance(m)
        links.remove(links.current.val)
        n--
    }
    links.display()
}

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

?著作權歸作者所有,轉載或內(nèi)容合作請聯(lián)系作者

人面猴
序言：七十年代末，一起剝皮案震驚了整個濱河市忘嫉，隨后出現(xiàn)的幾起案子荤牍，更是在濱河造成了極大的恐慌，老刑警劉巖庆冕，帶你破解...
沈念sama閱讀 218,682評論 6贊 507
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件康吵，死亡現(xiàn)場離奇詭異，居然都是意外死亡访递，警方通過查閱死者的電腦和手機晦嵌，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 93,277評論 3贊 395
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來力九，“玉大人耍铜，你說我怎么就攤上這事〉埃” “怎么了棕兼？”我有些...
開封第一講書人閱讀 165,083評論 0贊 355
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵，是天一觀的道長抵乓。經(jīng)常有香客問我伴挚，道長，這世上最難降的妖魔是什么灾炭？我笑而不...
開封第一講書人閱讀 58,763評論 1贊 295
?港島之戀（遺憾婚禮）
正文為了忘掉前任茎芋，我火速辦了婚禮，結果婚禮上蜈出，老公的妹妹穿的比我還像新娘田弥。我一直安慰自己，他們只是感情好铡原，可當我...
茶點故事閱讀 67,785評論 6贊 392
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布偷厦。她就那樣靜靜地躺著，像睡著了一般燕刻。火紅的嫁衣襯著肌膚如雪只泼。梳的紋絲不亂的頭發(fā)上，一...
開封第一講書人閱讀 51,624評論 1贊 305
城市分裂傳說
那天卵洗，我揣著相機與錄音请唱，去河邊找鬼。笑死，一個胖子當著我的面吹牛十绑，可吹牛的內(nèi)容都是我干的聚至。我是一名探鬼主播，決...
沈念sama閱讀 40,358評論 3贊 418
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼本橙，長吁一口氣：“原來是場噩夢啊……” “哼晚岭！你這毒婦竟也來了？” 一聲冷哼從身側響起勋功，我...
開封第一講書人閱讀 39,261評論 0贊 276
萬榮殺人案實錄
序言：老撾萬榮一對情侶失蹤，失蹤者是張志新（化名）和其女友劉穎库说，沒想到半個月后狂鞋，有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體，經(jīng)...
沈念sama閱讀 45,722評論 1贊 315
?護林員之死
正文獨居荒郊野嶺守林人離奇死亡潜的，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點故事閱讀 37,900評論 3贊 336
?白月光啟示錄
正文我和宋清朗相戀三年，在試婚紗的時候發(fā)現(xiàn)自己被綠了信不。大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
茶點故事閱讀 40,030評論 1贊 350
活死人
序言：一個原本活蹦亂跳的男人離奇死亡梭姓，死狀恐怖，靈堂內(nèi)的尸體忽然破棺而出嫩码，到底是詐尸還是另有隱情誉尖，我是刑警寧澤，帶...
沈念sama閱讀 35,737評論 5贊 346
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布铡恕，位于F島的核電站，受9級特大地震影響回挽，放射性物質發(fā)生泄漏没咙。R本人自食惡果不足惜，卻給世界環(huán)境...
茶點故事閱讀 41,360評論 3贊 330
男人毒藥：我在死后第九天來索命
文/蒙蒙一、第九天我趴在偏房一處隱蔽的房頂上張望寄月。院中可真熱鬧克懊，春花似錦谭溉、人聲如沸碧库。這莊子的主人今日做“春日...
開封第一講書人閱讀 31,941評論 0贊 22
一樁弒父案吠架，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽磺平。三九已至拣挪，卻和暖如春，著一層夾襖步出監(jiān)牢的瞬間舔痪，已是汗流浹背。一陣腳步聲響...
開封第一講書人閱讀 33,057評論 1贊 270
情欲美人皮
我被黑心中介騙來泰國打工驯耻，沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留，地道東北人花墩。一個月前我還...
沈念sama閱讀 48,237評論 3贊 371
代替公主和親
正文我出身青樓，卻偏偏與公主長得像观游，于是被迫代替她去往敵國和親搂捧。傳聞我的和親對象是個殘疾皇子，可洞房花燭夜當晚...
茶點故事閱讀 44,976評論 2贊 355

數(shù)據(jù)結構與算法JavaScript描述（4） —— 鏈表（LinkedList ）

單向鏈表

雙向鏈表

循環(huán)鏈表

推薦閱讀更多精彩內(nèi)容