數(shù)據(jù)結構-鏈表

stormzhang 發(fā)布于2019-08-26 12:20 / 3547人閱讀

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

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

數(shù)組的缺點

數(shù)組不總是組織數(shù)據(jù)的最佳數(shù)據(jù)結構, 原因如下. 在很多編程語言中, 數(shù)組的長度是固定的, 所以當數(shù)組已被數(shù)據(jù)填滿時, 再要加入新的元素就會非常困難. 在數(shù)組中, 添加和刪除元素也很麻煩, 因為需要將數(shù)組中的其他元素向前或向后平移, 以反映數(shù)組剛剛進行了添加或刪除操作. 然而, JS的數(shù)組不存在上述問題. 因為使用splice()方法不需要再訪問數(shù)組中的其它元素了.

定義鏈表

由一組節(jié)點組成的集合. 每一個節(jié)點都使用一個對象的引用指向它的后繼. 指向另一個節(jié)點的引用叫做鏈.
圖片名稱

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

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

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

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

設計一個基于對象的鏈表

我們設計的鏈表包含兩個類. Node類用于表示節(jié)點, LinkedList類提供了插入節(jié)點、刪除節(jié)點、顯示列表元素的方法, 以及其他一些輔助方法.

Node類

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

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

LinkedList類

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

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é)點insert()
該方法向鏈表中插入一個節(jié)點. 向鏈表中插入新節(jié)點時, 需要明確指出要在哪個節(jié)點前面或后面插入元素.

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

一旦找到后面的節(jié)點, 就可以將新的節(jié)點插入鏈表了. 首先, 將新節(jié)點的next屬性設置為后面節(jié)點的next屬性對應的值. 然后設置后面節(jié)點的next屬性指向新節(jié)點.

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

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

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

測試程序:

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é)點到尾節(jié)點很簡單, 但反過來, 從后向前遍歷則沒那么簡單. 通過給Node對象增加一個屬性, 該屬性存儲指向前驅(qū)節(jié)點的鏈接, 這樣就容易多了. 此時向鏈表中插入一個節(jié)點需要更多的工作, 我們需要指出該節(jié)點正確的前驅(qū)和后繼. 但是刪除節(jié)點時效率提高了, 不需要再查找待刪除節(jié)點的前驅(qū)節(jié)點了.

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

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

insert()方法和單向鏈表的類似, 但是需要設置新節(jié)點的previous屬性, 使其指向該節(jié)點的前驅(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()方法比單向鏈表的效率更高, 因為不需要查找前驅(qū)節(jié)點了. 首先需要在鏈表中找出存儲待刪除數(shù)據(jù)的節(jié)點, 然后設置該節(jié)點前驅(qū)的next屬性, 使其指向待刪除節(jié)點的后繼; 設置該節(jié)點后繼的previous屬性, 使其指向待刪除節(jié)點的前驅(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;
    }
}
...

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

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

    return currNode;
}
...

有了這個工具方法, 就可以寫一個方法, 反序顯示雙向鏈表中的元素. 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)鏈表

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

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

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

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

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

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

鏈表的其它方法 advance()前移

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

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

使整個鏈表向前移動, 從頭結點開始, 移動幾位就是頭節(jié)點賦值為第幾個next節(jié)點.

back()后移

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

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

是整個鏈表向后移動, 如果第一個節(jié)點(當前節(jié)點)為頭節(jié)點(head)則不移動.

show()只顯示當前節(jié)點數(shù)據(jù)

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

循環(huán)鏈表解決猶太歷史學家弗拉維奧·約瑟夫基和他的同伴生存問題.

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

GPU云服務器云服務器鏈表數(shù)據(jù)結構隊列 linux 數(shù)據(jù)結構鏈表 java鏈表數(shù)據(jù)結構 C++數(shù)據(jù)結構鏈表

文章版權歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/108528.html

學習JavaScript數(shù)據(jù)結構與算法（二）：鏈表

摘要：實現(xiàn)移除給定的元素要移除的元素返回值表示移除成功方法說明移除單向鏈表中某個位置的元素。的前端樂園原文鏈接寒假前端學習學習數(shù)據(jù)結構與算法二鏈表本系列的第一篇文章: 學習JavaScript數(shù)據(jù)結構與算法（一），棧與隊列第二篇文章：學習JavaScript數(shù)據(jù)結構與算法（二）：鏈表第三篇文章：學習JavaScript數(shù)據(jù)結構與算法（三）：集合第四篇文章：學習JavaScript數(shù)據(jù)結構與...

lolomaco 2019-08-22 11:00 評論0 收藏0
JavaScript數(shù)據(jù)結構04 - 鏈表

摘要：類表示要加入鏈表的項。循環(huán)鏈表和普通鏈表之間唯一的區(qū)別在于，最后一個元素指向下一個元素的指針不是引用，而是指向第一個元素。這里就不進行代碼實現(xiàn)了，大家可以結合上面的單向鏈表和雙向鏈表自己實現(xiàn)一個循環(huán)鏈表。一、定義 1.1 概念前面我們學習了數(shù)組這種數(shù)據(jù)結構。數(shù)組（或者也可以稱為列表）是一種非常簡單的存儲數(shù)據(jù)序列的數(shù)據(jù)結構。在這一節(jié)，我們要學習如何實現(xiàn)和使用鏈表這種動態(tài)的數(shù)據(jù)結構，這...

cheukyin 2019-08-23 10:39 評論0 收藏0
JavaScript的數(shù)據(jù)結構與算法（三） —— 單向鏈表

摘要：鏈表鏈表存儲有序的元素集合，但不同于數(shù)組，鏈表中的元素在內(nèi)存中并不是連續(xù)放置的。相對于傳統(tǒng)的數(shù)組，鏈表的一個好處在于，添加或者刪除元素的時候不需要移動其他元素。鏈表鏈表存儲有序的元素集合，但不同于數(shù)組，鏈表中的元素在內(nèi)存中并不是連續(xù)放置的。每個元素由一個存儲元素本事的節(jié)點和一個指向下一個元素的引用組成。相對于傳統(tǒng)的數(shù)組，鏈表的一個好處在于，添加或者刪除元素的時候不需要移動其他元素。...

李濤 2019-08-21 17:14 評論0 收藏0
JavaScript的數(shù)據(jù)結構與算法（四） —— 雙向鏈表

摘要：鏈表鏈表存儲有序的元素集合，但不同于數(shù)組，鏈表中的元素在內(nèi)存中并不是連續(xù)放置的。鏈表又包括單向鏈表和雙向鏈表雙向鏈表雙向鏈表與單向鏈表很是相像。但在雙向鏈表中，還有指向上一個節(jié)點的鏈接，是雙向的。鏈表鏈表存儲有序的元素集合，但不同于數(shù)組，鏈表中的元素在內(nèi)存中并不是連續(xù)放置的。每個元素由一個存儲元素本事的節(jié)點和一個指向下一個元素的引用組成。相對于傳統(tǒng)的數(shù)組，鏈表的一個好處在于，添加或...

Youngdze 2019-08-21 17:13 評論0 收藏0

發(fā)表評論

登陸后可評論

0條評論

stormzhang

男|高級講師

我要關注我要私信

TA的文章

activate

閱讀 3280·2023-04-25 17:19
Linux快速學習-vi編輯器常用命令

閱讀 653·2021-11-23 09:51
Pia云雙11活動：新用戶全場5折，可選美國三網(wǎng)CN2 GIA月付10元起，香港純CN2永不混線月付

閱讀 1376·2021-11-08 13:19
ASEMI肖特基二極管MBR20200FCT參數(shù)詳解

閱讀 810·2021-09-29 09:34
【?重走長征路のC語言中static關鍵字?】

閱讀 1717·2021-09-28 09:36
godaddy主機ftp端口多少-godaddy主機怎么樣？

閱讀 1522·2021-09-22 14:59
css3 彈性布局和多列布局

閱讀 2739·2019-08-29 16:38
es6之迭代器

閱讀 2083·2019-08-26 13:40

成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！

數(shù)據(jù)結構-鏈表

相關文章

學習JavaScript數(shù)據(jù)結構與算法（二）：鏈表

JavaScript數(shù)據(jù)結構04 - 鏈表

**JavaScript的數(shù)據(jù)結構與算法（三） —— 單向鏈表**

**JavaScript的數(shù)據(jù)結構與算法（四） —— 雙向鏈表**

發(fā)表評論

0條評論

stormzhang

男|高級講師

TA的文章

activate

Linux快速學習-vi編輯器常用命令

Pia云雙11活動：新用戶全場5折，可選美國三網(wǎng)CN2 GIA月付10元起，香港純CN2永不混線月付

ASEMI肖特基二極管MBR20200FCT參數(shù)詳解

【?重走長征路のC語言中static關鍵字?】

godaddy主機ftp端口多少-godaddy主機怎么樣？

css3 彈性布局和多列布局

es6之迭代器

最新活動

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！

數(shù)據(jù)結構-鏈表

相關文章

發(fā)表評論

0條評論

男|高級講師

TA的文章

最新活動

上云采購季！| 2核2G4M爆款云服務器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！