[ JavaScript ] 數(shù)據(jù)結(jié)構(gòu)與算法 —— 鏈表

wfc_666 發(fā)布于2019-08-23 15:19 / 1334人閱讀

摘要：每個(gè)元素由一個(gè)存儲(chǔ)元素本身的節(jié)點(diǎn)和一個(gè)指向下一個(gè)元素的引用也稱指針或鏈接組成。相對(duì)于傳統(tǒng)的數(shù)組，鏈表的一個(gè)好處在于，添加或移除元素的時(shí)候不需要移動(dòng)其他元素。然而，鏈表需要使用指針，因此實(shí)現(xiàn)鏈表時(shí)需要額外注意。

本篇主要有三部分

什么是鏈表

鏈表的實(shí)現(xiàn)

鏈表的變種

源碼地址：https://github.com/yhtx1997/S...

另外，今天2019年2月18日上午發(fā)現(xiàn) 2048-vue 版，代碼版本不對(duì)，且最新版本遺失，無奈只得重新修復(fù)了下
2048-vue地址： https://github.com/yhtx1997/S...

什么是鏈表

鏈表存儲(chǔ)有序的元素集合，但不同于數(shù)組，鏈表中的元素在內(nèi)存中并不是連續(xù)放置的。每個(gè)
元素由一個(gè)存儲(chǔ)元素本身的節(jié)點(diǎn)和一個(gè)指向下一個(gè)元素的引用（也稱指針或鏈接）組成。
相對(duì)于傳統(tǒng)的數(shù)組，鏈表的一個(gè)好處在于，添加或移除元素的時(shí)候不需要移動(dòng)其他元素。然
而，鏈表需要使用指針，因此實(shí)現(xiàn)鏈表時(shí)需要額外注意。數(shù)組的另一個(gè)細(xì)節(jié)是可以直接訪問任何
位置的任何元素，而要想訪問鏈表中間的一個(gè)元素，需要從起點(diǎn)（表頭）開始迭代列表直到找到
所需的元素。
如下圖：

注：其中 00 06 10 12 18 為假定在內(nèi)存中的地址

我將已經(jīng)做好的鏈表存入數(shù)據(jù)，然后在控制臺(tái)打印出來是這樣的：

它看起來就像是這樣的，一層套一層

其實(shí)應(yīng)該是下面這樣，類似于栓狗的鐵鏈

鏈表的實(shí)現(xiàn) 鏈表功能

添加元素

獲取指定位置元素

在指定位置插入元素

移除指定位置的元素

返回指定元素的位置

移除指定元素

是否為空

長(zhǎng)度

獲取表頭

清空鏈表

轉(zhuǎn)換為字符串輸出

// 鏈表元素
class Node {
    constructor(element) {
        this.element = element; // 元素
        this.next = undefined; // 指向下一個(gè)元素
    }
}
class LinkedList {
    // 構(gòu)造函數(shù)聲明一些全局變量
    constructor(){
        this.count = 0; // 長(zhǎng)度
        this.head = undefined; // 第一個(gè)元素
    }
    // 添加元素
    push(element) {
        
    }
    // 獲取指定位置元素
    getElementAt(index) {
        
    }
    // 在指定位置插入元素
    insert(element, index) {
        
    }
    // 移除指定位置的元素
    removeAt(index) {
    
    }
    // 返回指定元素的位置
    indexOf(element) {
        
    }
    // 移除指定元素
    remove(element) {
        
    }
    // 是否為空
    isEmpty() {
        
    }
    // 長(zhǎng)度
    size() {
        
    }
    // 獲取表頭
    getHead() {
       
    }
    // 清空鏈表
    clear() {
        
    }
    // 轉(zhuǎn)換為字符串輸出
    toString() {
        
    }
}

代碼實(shí)現(xiàn)

class LinkedList {
    // 構(gòu)造函數(shù)聲明一些全局變量
    constructor(){
        this.count = 0; // 長(zhǎng)度
        this.head = undefined; // 第一個(gè)元素
    }
    // 添加元素
    push(element) {
        const node = new Node(element);
        if (this.head === undefined) {
            this.head = node;
        } else {
            let current = this.head;
            while (current.next !== undefined) {
                current = current.next;
            }
            current.next = node;
        }
        this.count++;
    }
    // 獲取指定位置元素
    getElementAt(index) {
        // 判斷不是空鏈表
        if (this.isEmpty() || index > this.count || index < 0) { 
            // 非空才能繼續(xù)處理
            // 判斷不大于最大長(zhǎng)度，不小于最小長(zhǎng)度（0）
            return undefined;
        }
        // 循環(huán)找到元素
        let current = this.head;
        for (let i = 0; i < index; i++){
            current = current.next;
        }
        return current;// 返回找到的元素
    }
    // 在指定位置插入元素
    insert(element, index) {
        // 創(chuàng)建一個(gè)元素
        let current = new Node(element);
        // 首先確定是不是在首位置插入
        if (index === 0){
            current.next = this.head;
            this.head = current;
        } else {
            // 找到指定位置前一個(gè)元素
            let previous = this.getElementAt(index - 1);
            // 將前一個(gè)元素的 next 賦值給插入元素的 next
            current.next = previous.next;
            // 將插入元素的 node 賦值給前一個(gè)元素的 next
            previous.next = current;
        }
        this.count++;
    }
    // 移除指定位置的元素
    removeAt(index) {
        let current = this.head;
        if (index === 0){
            this.head = current.next;
        } else {
            // 找到這個(gè)元素和這個(gè)元素之前的元素
            let previous = this.getElementAt(index - 1);
            current = previous.next;
            // 將這個(gè)元素的 next 賦值給這個(gè)元素之前元素的 next
            previous.next = current.next;
        }
        this.count--;
        // 返回要移除的元素
        return current.element;
    }
    // 返回指定元素的位置
    indexOf(element) {
        // 從頭開始找
        let current = this.head;
        // 不超過最大長(zhǎng)度
        for (let i = 0; i < this.size() && current != null; i++){
            if (current.element === element){ // 找到相等的就返回下標(biāo)
                return i;
            }
            current = current.next;
        }
        return -1;
    }
    // 移除指定元素
    remove(element) {
        // 獲取指定元素位置
        let index = this.indexOf(element);
        // 移除指定位置元素
        return this.removeAt(index);
    }
    // 是否為空
    isEmpty() {
        return this.size() === 0;
    }
    // 長(zhǎng)度
    size() {
        return this.count;
    }
    // 獲取表頭
    getHead() {
        return this.head;
    }
    // 清空鏈表
    clear() {
        this.head = undefined;
        this.count = 0;
    }
    // 轉(zhuǎn)換為字符串輸出
    toString() {
        if (this.head == null) {
            return "";
        }
        let objString = `${this.head.element}`;
        let current = this.head.next;
        for (let i = 1; i < this.size() && current != null; i++) {
            objString = `${objString},${current.element}`;
            current = current.next;
        }
        return objString;
    }
}
let a = new LinkedList();
a.push("a");
a.push("b");
a.push("c");
a.push("d");
a.push("e");
a.push("f");
a.push("h");
a.push("i");
a.push("j");
a.push("k");
a.push("l");
a.push("m");
a.push("n");
a.push("o");
a.push("p");
a.push("q");
a.remove("a");
a.insert("a",1);
console.log(a);

插入元素圖解：

現(xiàn)在有狗鏈兩節(jié)，我要在中間加一節(jié)

先把兩節(jié)分開，

然后把前邊的尾部與要加的頭部相連，然后把要加的尾部與后邊的頭部相連

0 連 xx , xx 連 1

鏈表的變種 雙向鏈表

我們已經(jīng)知道鏈表的每個(gè)元素由一個(gè)存儲(chǔ)元素本身的節(jié)點(diǎn)和一個(gè)指向下一個(gè)元素的引用（也稱指針或鏈接）組成，雙向鏈表除了這個(gè)基本特性，每個(gè)元素還包含一個(gè)指向前一個(gè)元素的引用，如圖所示：

循環(huán)鏈表

循環(huán)鏈表就是鏈表的最后一個(gè)指向下一個(gè)元素的引用指向了第一個(gè)元素，使其成為循環(huán)鏈表

雙向循環(huán)鏈表

雙向循環(huán)鏈表就是雙向鏈表的第一個(gè)元素指向前一個(gè)的引用指向了最后一個(gè)元素，而最后一個(gè)元素指向下一個(gè)元素的引用指向了第一個(gè)元素，如圖所示：

GPU云服務(wù)器云服務(wù)器鏈表算法鏈表排序算法算法 c語言鏈表算法與數(shù)據(jù)結(jié)構(gòu)

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

轉(zhuǎn)載請(qǐng)注明本文地址：http://specialneedsforspecialkids.com/yun/101860.html

發(fā)表評(píng)論

登陸后可評(píng)論

0條評(píng)論

wfc_666

男|高級(jí)講師

我要關(guān)注我要私信

TA的文章

域名如何綁定虛擬主機(jī)-如何進(jìn)行域名與虛擬主機(jī)綁定？

閱讀 3676·2021-09-22 15:34
幫你理清React的生命周期

閱讀 1186·2019-08-29 17:25
最簡(jiǎn)單的css reset

閱讀 3399·2019-08-29 11:18
js設(shè)計(jì)模式 --- 模版設(shè)計(jì)模式

閱讀 1370·2019-08-26 17:15
邏輯運(yùn)算符的使用

閱讀 1739·2019-08-23 17:19
React-代碼復(fù)用(mixin.hoc.render props)

閱讀 1227·2019-08-23 16:15
http協(xié)商緩存VS強(qiáng)緩存

閱讀 718·2019-08-23 16:02
[ JavaScript ] 數(shù)據(jù)結(jié)構(gòu)與算法 —— 鏈表

閱讀 1335·2019-08-23 15:19

国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來選購(gòu)！

[ JavaScript ] 數(shù)據(jù)結(jié)構(gòu)與算法 —— 鏈表

相關(guān)文章

**學(xué)習(xí)*JavaScript**數(shù)據(jù)結(jié)構(gòu)*與算法（二）：鏈表**

JavaScript的數(shù)據(jù)結(jié)構(gòu)與算法（四） —— 雙向鏈表