摘要：猶太士兵決定寧可自殺也不做俘虜，于是商量出了一個(gè)自殺方案。他們圍成一個(gè)圈，從一個(gè)人開始，數(shù)到第三個(gè)人時(shí)將第三個(gè)人殺死，然后再數(shù)，直到殺光所有人。使用循環(huán)鏈表解決該問題。首先我們看到他們圍成一個(gè)圈判斷應(yīng)該使用循環(huán)鏈表來處理改問題完整代碼前移

本章將討論另一種列表: 鏈表 . 解釋為什么有時(shí)鏈表優(yōu)于數(shù)組, 還會(huì)實(shí)現(xiàn)一個(gè)基于對(duì)象的鏈表.

數(shù)組不總是組織數(shù)據(jù)的最佳數(shù)據(jù)結(jié)構(gòu), 原因如下. 在很多編程語言中, 數(shù)組的長度是固定的, 所以當(dāng)數(shù)組已被數(shù)據(jù)填滿時(shí), 再要加入新的元素就會(huì)非常困難. 在數(shù)組中, 添加和刪除元素也很麻煩, 因?yàn)樾枰獙?shù)組中的其他元素向前或向后平移, 以反映數(shù)組剛剛進(jìn)行了添加或刪除操作. 然而, JS的數(shù)組不存在上述問題. 因?yàn)槭褂?b>splice()方法不需要再訪問數(shù)組中的其它元素了.

由一組節(jié)點(diǎn)組成的集合. 每一個(gè)節(jié)點(diǎn)都使用一個(gè)對(duì)象的引用指向它的后繼. 指向另一個(gè)節(jié)點(diǎn)的引用叫做鏈.

數(shù)組元素靠它們的位置進(jìn)行引用, 鏈表元素則是靠相互之間的關(guān)系進(jìn)行引用. 在上圖中, 我們說99跟在12后面, 而不說99是鏈表中的第二個(gè)元素. 遍歷鏈表, 就是跟著連接, 從鏈表的首元素一直走到尾元素(但這不包含鏈表的頭結(jié)點(diǎn), 頭結(jié)點(diǎn)常常永愛作為鏈表的接入點(diǎn)). 值得注意的是, 鏈表的尾元素指向一個(gè)null節(jié)點(diǎn).

然鵝要標(biāo)識(shí)出鏈表的起始節(jié)點(diǎn)卻有點(diǎn)麻煩, 許多鏈表的實(shí)現(xiàn)都是在鏈表最前面有一個(gè)特殊節(jié)點(diǎn), 叫做 頭節(jié)點(diǎn).

鏈表中插入一個(gè)節(jié)點(diǎn)的效率很高. 向鏈表中插入一個(gè)節(jié)點(diǎn), 需要修改它前面的節(jié)點(diǎn)(前驅(qū)), 使其事項(xiàng)新加入的節(jié)點(diǎn), 而新加入的節(jié)點(diǎn)則指向原來前驅(qū)指向的節(jié)點(diǎn).

從鏈表中刪除一個(gè)元素也很簡單. 將待刪除元素的前驅(qū)節(jié)點(diǎn)指向待刪除元素的后繼節(jié)點(diǎn), 同時(shí)將待刪除元素指向null, 元素就刪除成功了.

我們?cè)O(shè)計(jì)的鏈表包含兩個(gè)類. Node類用于表示節(jié)點(diǎn), LinkedList類提供了插入節(jié)點(diǎn)、刪除節(jié)點(diǎn)、顯示列表元素的方法, 以及其他一些輔助方法.

Node類包含兩個(gè)屬性: element用來保存節(jié)點(diǎn)上的數(shù)據(jù), next用來保存指向下一個(gè)節(jié)點(diǎn)的鏈接.

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

LList類提供了對(duì)鏈表進(jìn)行操作的方法. 該類的功能包括插入刪除節(jié)點(diǎn)、在列表中查找給定的值.

class LList {
    constructor() {
        this._head = new Node("head");
    }
    _find(item) {
        let currNode = this._head;
        while (currNode.element != item) {
            currNode = currNode.next;
        };
        return currNode;
    }
    _findPrevious(item) {
        let currNode = this._head;
        while (currNode.next !== null && currNode.next.element !== item) {
            currNode = currNode.next;
        };
        return currNode;  
    }
    insert(newElement, item) {
        const newNode = new Node(newElement);
        const current = this._find(item);
        newNode.next = current.next;
        current.next = newNode
    }
    remove(item) {
        const prevNode = this._findPrevious(item);
        if (prevNode.next !== null) {
            prevNode.next = prevNode.next.next
        }
    }
    display() {
        let currNode = this._head;
        while (!(currNode.next === null)) {
            console.log(currNode.next.element);
            currNode = currNode.next;
        }
    }
};

插入新節(jié)點(diǎn)insert()
該方法向鏈表中插入一個(gè)節(jié)點(diǎn). 向鏈表中插入新節(jié)點(diǎn)時(shí), 需要明確指出要在哪個(gè)節(jié)點(diǎn)前面或后面插入元素.

在一個(gè)已知節(jié)點(diǎn)后面插入元素時(shí), 先要找到 后面 的節(jié)點(diǎn). 為此, 創(chuàng)建一個(gè)輔助方法find(), 該方法遍歷鏈表, 查找給定數(shù)據(jù). 如果找到數(shù)據(jù), 該方法就返回保存該數(shù)據(jù)的節(jié)點(diǎn).
find()方法演示了如何在鏈表上進(jìn)行移動(dòng). 首先, 創(chuàng)建一個(gè)新節(jié)點(diǎn), 并將鏈表的頭節(jié)點(diǎn)賦給這個(gè)新創(chuàng)建的節(jié)點(diǎn). 然后再鏈表上進(jìn)行循環(huán), 如果當(dāng)前節(jié)點(diǎn)的element屬性和我們要找的信息不符, 就從當(dāng)前節(jié)點(diǎn)移動(dòng)到下一個(gè)節(jié)點(diǎn). 如果查找成功, 則返回該數(shù)據(jù)的節(jié)點(diǎn); 否則返回null.

一旦找到 后面 的節(jié)點(diǎn), 就可以將新的節(jié)點(diǎn)插入鏈表了. 首先, 將新節(jié)點(diǎn)的next屬性設(shè)置為 后面 節(jié)點(diǎn)的next屬性對(duì)應(yīng)的值. 然后設(shè)置 后面 節(jié)點(diǎn)的next屬性指向新節(jié)點(diǎn).

在測試之前我們定義一個(gè)display()方法, 該方法用來顯示鏈表中的元素.
display()先將列表的頭節(jié)點(diǎn)賦給一個(gè)變量, 然后循環(huán)遍歷鏈表, 當(dāng)節(jié)點(diǎn)的next屬性為null時(shí)循環(huán)結(jié)束. 為了只顯示包含數(shù)據(jù)的節(jié)點(diǎn)(換句話說, 不顯示頭節(jié)點(diǎn)), 程序只訪問當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)中保存的數(shù)據(jù): currNode.next.element.

測試程序:

const letters = new LList();
letters.insert("a", "head");
letters.insert("b", "a");
letters.insert("c", "b");
letters.insert("d", "c");
letters.display();

輸出:

a
b
c
d

刪除一個(gè)節(jié)點(diǎn)remove()
從鏈表中刪除節(jié)點(diǎn)時(shí), 需要先找到待刪除節(jié)點(diǎn)前面的節(jié)點(diǎn). 找到這個(gè)節(jié)點(diǎn)后, 修改它的next屬性, 使其不再事項(xiàng)待刪除節(jié)點(diǎn), 而是指向待刪除節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn). 我們定義一個(gè)方法findPrevious(). 該方法遍歷鏈表中的元素, 檢查每一個(gè)節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)中是否存儲(chǔ)待刪除數(shù)據(jù). 如果找到, 返回該節(jié)點(diǎn)(即 前一個(gè) 節(jié)點(diǎn)), 這樣就可以修改它的next屬性了.

remove()方法中最重要的一行代碼prevNode.next = prevNode.next.next;
這里跳過了待刪除節(jié)點(diǎn), 讓 前一個(gè) 節(jié)點(diǎn)指向了待刪除節(jié)點(diǎn)的后一個(gè)節(jié)點(diǎn).

測試程序:

const letters = new LList();
letters.insert("a", "head");
letters.insert("b", "a");
letters.insert("c", "b");
letters.insert("d", "c");
letters.display();

letters.remove("d");
console.log("")
letters.display();

輸出:

a
b
c
d

a
b
c

盡管從鏈表的頭節(jié)點(diǎn)到尾節(jié)點(diǎn)很簡單, 但反過來, 從后向前遍歷則沒那么簡單. 通過給Node對(duì)象增加一個(gè)屬性, 該屬性存儲(chǔ)指向前驅(qū)節(jié)點(diǎn)的鏈接, 這樣就容易多了. 此時(shí)向鏈表中插入一個(gè)節(jié)點(diǎn)需要更多的工作, 我們需要指出該節(jié)點(diǎn)正確的前驅(qū)和后繼. 但是刪除節(jié)點(diǎn)時(shí)效率提高了, 不需要再查找待刪除節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)了.

首先我們要為Node類增加一個(gè)previous屬性:

class Node {
    constructor(element) {
        this.element = element;
        this.next = null;
        this.previous = null;
    };
};

insert()方法和單向鏈表的類似, 但是需要設(shè)置新節(jié)點(diǎn)的previous屬性, 使其指向該節(jié)點(diǎn)的前驅(qū).

...
insert(newElement, item) {
    const newNode = new Node(newElement);
    const current = this._find(item);
    newNode.next = current.next;
    newNode.previous = current;
    current.next = newNode;
}
...

remove()方法比單向鏈表的效率更高, 因?yàn)椴恍枰檎仪膀?qū)節(jié)點(diǎn)了. 首先需要在鏈表中找出存儲(chǔ)待刪除數(shù)據(jù)的節(jié)點(diǎn), 然后設(shè)置該節(jié)點(diǎn)前驅(qū)的next屬性, 使其指向待刪除節(jié)點(diǎn)的后繼; 設(shè)置該節(jié)點(diǎn)后繼的previous屬性, 使其指向待刪除節(jié)點(diǎn)的前驅(qū).

...
remove(item) {
    const currNode = this._find(item);
    if(currNode.next != null) {
        currNode.previous.next = currNode.next;
        currNode.next.previous = currNode.previous;
        currNode.next = null;
        currNode.previous = null;
    }
}
...

為了反序顯示鏈表中元素, 需要給雙向鏈表增加一個(gè)工具方法, 用來查找最后的節(jié)點(diǎn). findLast()方法找出了鏈表中的最后一個(gè)節(jié)點(diǎn), 同時(shí)免除了從前往后遍歷鏈表之苦:

...
_findLast() {
    let currNode = this._head;
    while (currNode != null) {
        currNode = currNode.next;
    };

    return currNode;
}
...

有了這個(gè)工具方法, 就可以寫一個(gè)方法, 反序顯示雙向鏈表中的元素. dispReverse()方法:

...
dispReverse() {
    let currNode = this._head;
    currNode = this._findLast();
    while (currNode.previous != null) {
        console.log(currNode.element);
        currNode = currNode.previous;
    }
}
...

全部代碼:

class Node {
    constructor(element) {
        this.element = element;
        this.next = null;
        this.previous = null;
    }
};

class LList {
    constructor() {
        this._head = new Node("head");
    }
    _find(item) {
        let currNode = this._head;
        while (currNode.element != item) {
            currNode = currNode.next;
        };
        return currNode;
    }
    _findPrevious(item) {
        let currNode = this._head;
        while (currNode.next !== null && currNode.next.element !== item) {
            currNode = currNode.next;
        };
        return currNode;  
    }
    _findLast() {
        let currNode = this._head;
        while (currNode.next != null) {
            currNode = currNode.next;
        };

        return currNode;
    }
    insert(newElement, item) {
        const newNode = new Node(newElement);
        const current = this._find(item);
        newNode.next = current.next;
        newNode.previous = current;
        current.next = newNode
    }
    remove(item) {
        const currNode = this._find(item);
        if (currNode.next !== null) {
            currNode.previous.next = currNode.next;
            currNode.next.previous = currNode.previous;
            currNode.next = null;
            currNode.previous = null;
        } else {
            currNode.previous.next = null;
        }
    }
    display() {
        let currNode = this._head;
        while (!(currNode.next === null)) {
            console.log(currNode.next.element);
            currNode = currNode.next;
        }
    }
    dispReverse() {
        let currNode = this._head;
        currNode = this._findLast();
        while (currNode.previous !== null) {
            console.log(currNode.element);
            currNode = currNode.previous;
        }
    }
};

const letters = new LList();
letters.insert("a", "head");
letters.insert("b", "a");
letters.insert("c", "b");
letters.insert("d", "c");
letters.display();
letters.dispReverse();

letters.remove("d");
letters.remove("b");
console.log("")
letters.dispReverse();

程序輸出:

a
b
c
d
d
c
b
a

c
a

循環(huán)鏈表和單向鏈表相似, 節(jié)點(diǎn)類型都是一樣的. 唯一的區(qū)別是, 在創(chuàng)建循環(huán)鏈表時(shí), 讓其頭節(jié)點(diǎn)的next屬性指向它本身.
_head.next = _head
這種行為會(huì)傳導(dǎo)至鏈表中的每一個(gè)節(jié)點(diǎn), 使得每一個(gè)節(jié)點(diǎn)的next屬性都是指向鏈表的頭節(jié)點(diǎn). 換句話說, 鏈表的尾節(jié)點(diǎn)指向頭節(jié)點(diǎn), 形成了一個(gè)循環(huán)鏈表.

如果你希望可以從后面向前遍歷鏈表, 但是又不想付出額外代價(jià)來創(chuàng)建一個(gè)雙向鏈表, 那么就需要使用循環(huán)鏈表. 從循環(huán)鏈表的尾節(jié)點(diǎn)向后移動(dòng), 就等于從后向前遍歷鏈表.

創(chuàng)建循環(huán)鏈表, 只需要修改單向鏈表的LList類的構(gòu)造函數(shù):

class LList {
    constructor() {
        this._head = new Node("head");
        this._head.next = this._head;
    }
    ...
}

只要修改一處, 就將單向鏈表變成了循環(huán)鏈表. 但是其它一些方法需要修改才能工作正常. eg: display()就需要修改, 原來的方式在循環(huán)鏈表里會(huì)陷入死循環(huán). while循環(huán)條件需要修改, 需要檢查頭節(jié)點(diǎn), 當(dāng)循環(huán)到頭節(jié)點(diǎn)時(shí)退出循環(huán).

...
display() {
    let currNode = this._head;
    while (currNode.next !== null && currNode.next.element !== "head") {
        console.log(currNode.next.element);
        currNode = currNode.next;
    }
}
...

單向鏈表就可以完成該功能. 但是為了配合后移功能我們采用雙向鏈表.

...
advance(n) {
    while ( n && this._head.next != null) {
        this._head = this._head.next;
        n--;
    };
}
...

使整個(gè)鏈表向前移動(dòng), 從頭結(jié)點(diǎn)開始, 移動(dòng)幾位就是頭節(jié)點(diǎn)賦值為第幾個(gè)next節(jié)點(diǎn).

與前移不同的后移功能需要在雙向鏈表上實(shí)現(xiàn).

...
back(n) {
    while ( n && this._head.element != "head") {
        this._head = this._head.previous;
        n--;
    };
}
...

是整個(gè)鏈表向后移動(dòng), 如果第一個(gè)節(jié)點(diǎn)(當(dāng)前節(jié)點(diǎn))為頭節(jié)點(diǎn)(head)則不移動(dòng).

...
show() {
    return this._head;
}
...

傳說在公元1 世紀(jì)的猶太戰(zhàn)爭中，猶太歷史學(xué)家弗拉維奧·約瑟夫斯和他的40個(gè)同胞被羅馬士兵包圍。猶太士兵決定寧可自殺也不做俘虜，于是商量出了一個(gè)自殺方案。他們圍成一個(gè)圈，從一個(gè)人開始，數(shù)到第三個(gè)人時(shí)將第三個(gè)人殺死，然后再數(shù)，直到殺光所有人。約瑟夫和另外一個(gè)人決定不參加這個(gè)瘋狂的游戲，他們快速地計(jì)算出了兩個(gè)位置，站在那里得以幸存。寫一段程序?qū) 個(gè)人圍成一圈，并且第m個(gè)人會(huì)被殺掉，計(jì)算一圈人中哪兩個(gè)人最后會(huì)存活。使用循環(huán)鏈表解決該問題。
首先我們看到他們圍成一個(gè)圈判斷應(yīng)該使用循環(huán)鏈表來處理改問題.
完整代碼:

window.log = console.log.bind(console);
class Node {
    constructor(element) {
        this.element = element;
        this.next = null;
    }
};

class LList {
    constructor() {
        this._head = new Node("head");
        this._head.next = this._head;
        this.currentNode = this._head;
    }
    _find(item) {
        let currNode = this._head;
        while (currNode.element != item) {
            currNode = currNode.next;
        };
        return currNode;
    }
    _findPrevious(item) {
        let currNode = this._head;
        while (currNode.next !== null && currNode.next.element !== item) {
            currNode = currNode.next;
        };
        return currNode;  
    }
    insert(newElement, item) {
        const newNode = new Node(newElement);
        const current = this._find(item);
        newNode.next = current.next;
        current.next = newNode;
    }
    remove(item) {
        const prevNode = this._findPrevious(item);
        if (prevNode.next !== null) {
            prevNode.next = prevNode.next.next
        }
    }
    // 前移
    advance(n) {
        while ( n ) {
            if(this.currentNode.next.element == "head") {
                this.currentNode = this.currentNode.next.next;
            } else {
                this.currentNode = this.currentNode.next;
            } 
            n--;
        };
    }
    show() {
        return this.currNode;
    }
    count() {
        let currNode = this._head;
        let i = 0;
        while (currNode.next.element != "head") {
            currNode = currNode.next;
            ++i
        };
        
        return i;
    }
    display() {
        let currNode = this._head;
        
        while (currNode.next !== null && currNode.next.element !== "head") {
            console.log(currNode.next.element);
            currNode = currNode.next;
        }
    }
};

const p = new LList();

const peopleNum = 40;
for(let i = 1; i <= peopleNum; i++) {
    if(i === 1) {
        p.insert(`people${i}`, "head");
    } else {
        p.insert(`people${i}`, `people${i - 1}`);
    }
};

p.display();
while (p.count() > 2) {
    p.advance(3);
    p.remove(p.currentNode.element);
    log("http://///////////////")
    p.display();
};