JavaScript數(shù)據(jù)結(jié)構(gòu)之鏈表各種操作詳解

更新時間：2022年10月19日 15:47:55 作者：橘貓吃不胖～

數(shù)據(jù)結(jié)構(gòu)是一種有效處理大量數(shù)據(jù)的手段，了解它的結(jié)構(gòu)和組成為我們提供了更有效的工具來設(shè)計與某些問題相關(guān)的產(chǎn)品。這次我們將進(jìn)行鏈表介紹，回顧它的特點(diǎn)和用途

1 數(shù)組與鏈表的優(yōu)缺點(diǎn)
2 什么是鏈表
3 封裝鏈表結(jié)構(gòu)
4 向鏈表尾部添加一個新的項(xiàng)
5 向鏈表某個位置插入一個新的項(xiàng)
6 獲取對應(yīng)位置的元素
7 獲取元素在鏈表中的索引
8 修改某個位置的元素
9 從鏈表中刪除某位置節(jié)點(diǎn)
10 全部代碼

1 數(shù)組與鏈表的優(yōu)缺點(diǎn)

鏈表和數(shù)組一樣，都可以用于存儲一系列的元素，但是鏈表和數(shù)組的實(shí)現(xiàn)機(jī)制完全不同。

一般情況下，要存儲多個元素，數(shù)組可能是最常用的數(shù)據(jù)結(jié)構(gòu)。但是使用數(shù)組存儲有一些缺點(diǎn)：

數(shù)組的創(chuàng)建需要申請一段連續(xù)的內(nèi)存空間（一整塊的內(nèi)存），并且大小是固定的，所以當(dāng)當(dāng)前數(shù)組不能滿足容量需求時，就需要擴(kuò)容（一般情況下會申請一個更大的數(shù)組，比如2倍，然后將原數(shù)組中的元素復(fù)制過去）。
在數(shù)組的開頭或中間位置插入數(shù)據(jù)的成本很高，需要進(jìn)行大量元素的位移。

存儲多個元素的另一個選擇就是鏈表，但是不同于數(shù)組，鏈表中的元素在內(nèi)存中不必是連續(xù)的空間，鏈表的每個元素由一個存儲元素本身的節(jié)點(diǎn)和指向下一個元素的引用（指針）組成。

那么和數(shù)組相比，鏈表有一些優(yōu)勢：

內(nèi)存空間不是必須連續(xù)的，可以充分利用計算機(jī)的內(nèi)存，實(shí)現(xiàn)靈活的內(nèi)存動態(tài)管理；
鏈表不必在創(chuàng)建時就確定大小，并且大小可以無限延伸下去；
鏈表在插入和刪除數(shù)據(jù)時，時間復(fù)雜度可以達(dá)到O(1)，相對數(shù)組效率高很多；

鏈表也有一些缺點(diǎn)：

鏈表訪問任何一個元素的位置時，都需要從頭開始訪問，并且無法跳過第一個元素訪問任何一個元素
鏈表無法通過下標(biāo)直接訪問元素，需要從頭一個個訪問，直到找到對應(yīng)的元素

2 什么是鏈表

鏈表的每個元素由一個存儲元素本身的節(jié)點(diǎn)和指向下一個元素的引用（指針）組成。

它類似于火車，火車頭就是頭節(jié)點(diǎn)，火車車廂之間的連接類似于指針，火車上的乘客類似于數(shù)據(jù)。

接下來我們根據(jù)它的特性來手動封裝一個鏈表。

3 封裝鏈表結(jié)構(gòu)

首先我們來封裝一個鏈表類LindedList，用來表示我們的鏈表結(jié)構(gòu)。LindedList類中應(yīng)該有兩個屬性，鏈表的頭節(jié)點(diǎn)head和鏈表的長度length。

function LinkedList() {
    this.head = null; // 初始指向null
    this.length = 0; // 初始鏈表長度為0
}

在LindedList類內(nèi)部有一個ListNode類，用于創(chuàng)建節(jié)點(diǎn)，創(chuàng)建節(jié)點(diǎn)時應(yīng)該為節(jié)點(diǎn)傳入數(shù)據(jù)data，并且該節(jié)點(diǎn)有指向下一個節(jié)點(diǎn)的指針。

function LinkedList() {
    this.head = null; // 初始指向null
    this.length = 0; // 初始鏈表長度為0
    function ListNode(data) {
        this.data = data;
        this.next = null;
    }
}

到這里鏈表的基礎(chǔ)結(jié)構(gòu)就完成了，接下來我們來封裝鏈表的方法。

4 向鏈表尾部添加一個新的項(xiàng)

向鏈表尾部添加一個新的節(jié)點(diǎn)，有兩種情況：

當(dāng)鏈表本身為空時，頭節(jié)點(diǎn)就是新添加的節(jié)點(diǎn)
當(dāng)鏈表不為空時，讓鏈表最后一個節(jié)點(diǎn)指向新添加的節(jié)點(diǎn)

根據(jù)這個思路，我們可以實(shí)現(xiàn)append方法如下：

LinkedList.prototype.append = function (data) { // data是新節(jié)點(diǎn)的值
    let node = new ListNode(data); // 創(chuàng)建新的節(jié)點(diǎn)
    if (this.length === 0) { // 如果鏈表為空，則新節(jié)點(diǎn)就是頭節(jié)點(diǎn)
        this.head = node;
    } else { // 如果鏈表不為空，新節(jié)點(diǎn)添加到鏈表尾部
        let current = this.head; // 將current指向頭節(jié)點(diǎn)
        // 鏈表無法直接訪問到最后的節(jié)點(diǎn)，只能通過一次次遍歷來訪問
        while (current.next) { // 當(dāng)達(dá)到最后一個節(jié)點(diǎn)時，循環(huán)結(jié)束
            // 當(dāng)下一個節(jié)點(diǎn)存在時，就讓current指針移動到下一個節(jié)點(diǎn)上
            current = current.next;
        }
        // 最后一個節(jié)點(diǎn)指向新節(jié)點(diǎn)
        current.next = node;
    }
    this.length += 1; // 鏈表的長度+1
}

5 向鏈表某個位置插入一個新的項(xiàng)

在鏈表的任意位置插入節(jié)點(diǎn)時，也分為兩種情況：

當(dāng)插入到第一個位置時，新節(jié)點(diǎn)變成了頭節(jié)點(diǎn)，那么新節(jié)點(diǎn)要指向原來的頭節(jié)點(diǎn)，屬性head也應(yīng)該變成新節(jié)點(diǎn)
當(dāng)插入到其他位置時，首先通過循環(huán)找到該位置，同時保存上一個節(jié)點(diǎn)和下一個節(jié)點(diǎn)，然后將上一個節(jié)點(diǎn)指向新節(jié)點(diǎn)，新節(jié)點(diǎn)指向下一個節(jié)點(diǎn)

插入insert方法代碼實(shí)現(xiàn)如下：

// position為節(jié)點(diǎn)要插入的位置，data為節(jié)點(diǎn)的值
LinkedList.prototype.insert = function (position, data) {
    // 對position進(jìn)行越界判斷，當(dāng)該值小于0或者大于鏈表長度時，不能進(jìn)行插入操作
    if (position <= 0 || position > this.length) return false;
    let node = new ListNode(data); // 創(chuàng)建新節(jié)點(diǎn)
    if (position === 0) { // 如果節(jié)點(diǎn)要插入第一個位置
        node.next = this.head; // 新節(jié)點(diǎn)指向原來的頭節(jié)點(diǎn)
        this.head = node; // 頭節(jié)點(diǎn)修改為新節(jié)點(diǎn)
    } else {
        let previous = null; // 指向前一個位置
        let current = this.head; // 指向下一個位置
        let index = 1; // 記錄循環(huán)的位置
        // 循環(huán)結(jié)束，previous和current之間就是插入的節(jié)點(diǎn)
        while (index < position) {
            previous = current;
            current = current.next;
            index++;
        }
        previous.next = node; // 在正確的位置插入元素
        node.next = current;
    }
    this.length += 1; // 長度加1
}

6 獲取對應(yīng)位置的元素

獲取某個位置上的元素，也要通過循環(huán)鏈表來找到當(dāng)前元素，get方法實(shí)現(xiàn)如下：

LinkedList.prototype.get = function (position) {
    // 越界判斷，如果位置小于0或者大于鏈表長度，不能獲取到元素
    if (position <= 0 || position > this.length) return null;
    let index = 1; // 記錄當(dāng)前位置
    let current = this.head; // current指向頭節(jié)點(diǎn)
    // 循環(huán)結(jié)束，current指向該位置上的節(jié)點(diǎn)
    while (index < position) {
        current = current.next;
        index++;
    }
    return current.data;
}

7 獲取元素在鏈表中的索引

獲取索引時，要循環(huán)遍歷鏈表，將鏈表的每一個節(jié)點(diǎn)值都和給定的值比較，如果相等返回當(dāng)前節(jié)點(diǎn)的位置，如果沒找到，則返回-1。indexOf方法實(shí)現(xiàn)如下：

// 獲取某個元素的位置
LinkedList.prototype.indexOf = function (data) {
    let current = this.head;
    let index = 1; // 記錄元素的位置
    while (current) { // 循環(huán)遍歷鏈表
        if (current.data === data) { // 如果當(dāng)前節(jié)點(diǎn)的值等于元素的值
            return index; // 返回位置
        } else { // 如果不等于，繼續(xù)循環(huán)
            current = current.next;
            index++;
        }
    }
    return -1; // 循環(huán)結(jié)束了，說明沒找到
}

8 修改某個位置的元素

修改某個位置的元素時，循環(huán)遍歷鏈表，找到給定的位置，修改該位置上元素的值。update方法實(shí)現(xiàn)如下：

// 修改某個位置的元素
LinkedList.prototype.update = function (position, data) {
    // 越界判斷
    if (position <= 0 || position > this.length) return false;
    let current = this.head;
    let index = 1;
    while (index < position) {
        current = current.next;
        index++;
    }
    current.data = data; // 修改數(shù)據(jù)
    return true;
}

9 從鏈表中刪除某位置節(jié)點(diǎn)

刪除某個位置上的節(jié)點(diǎn)分為兩種情況：

刪除第一個位置上的節(jié)點(diǎn)時，要將第一個位置上的節(jié)點(diǎn)指向null，并且第二個位置上的節(jié)點(diǎn)成為頭節(jié)點(diǎn)
刪除其他位置上的節(jié)點(diǎn)，循環(huán)找到該位置，同時記錄該節(jié)點(diǎn)上一個節(jié)，將上一個節(jié)點(diǎn)指向該位置的下一個節(jié)點(diǎn)

刪除某位置節(jié)點(diǎn)removeAt方法實(shí)現(xiàn)如下：

LinkedList.prototype.removeAt = function (position) {
    if (position <= 0 || position > this.length) return false; // 越界判斷
    let current = this.head;
    if (position === 1) { // 如果刪除第一個位置上的節(jié)點(diǎn)（頭節(jié)點(diǎn)）
        this.head = this.head.next;
    } else { // 刪除其他位置的節(jié)點(diǎn)
        let index = 1; // 記錄當(dāng)前位置
        let previous = null;
        while (index < position) {
            previous = current;
            current = current.next;
            index++;
        }
        // 上一個節(jié)點(diǎn)指向當(dāng)前元素的下一個節(jié)點(diǎn)
        previous.next = current.next;
    }
    this.length--;
    return current; // 返回被刪除的節(jié)點(diǎn)
}

10 全部代碼

function LinkedList() {
    this.head = null; // 初始指向null
    this.length = 0; // 初始鏈表長度為0
    function ListNode(data) { // 創(chuàng)建新節(jié)點(diǎn)類
        this.data = data;
        this.next = null;
    }
    // 添加元素
    LinkedList.prototype.append = function (data) { // data是新節(jié)點(diǎn)的值
        let node = new ListNode(data); // 創(chuàng)建新的節(jié)點(diǎn)
        if (this.length === 0) { // 如果鏈表為空，則新節(jié)點(diǎn)就是頭節(jié)點(diǎn)
            this.head = node;
        } else { // 如果鏈表不為空，新節(jié)點(diǎn)添加到鏈表尾部
            let current = this.head; // 將current指向頭節(jié)點(diǎn)
            // 鏈表無法直接訪問到最后的節(jié)點(diǎn)，只能通過一次次遍歷來訪問
            while (current.next) { // 當(dāng)達(dá)到最后一個節(jié)點(diǎn)時，循環(huán)結(jié)束
                // 當(dāng)下一個節(jié)點(diǎn)存在時，就讓current指針移動到下一個節(jié)點(diǎn)上
                current = current.next;
            }
            // 最后一個節(jié)點(diǎn)指向新節(jié)點(diǎn)
            current.next = node;
        }
        this.length += 1; // 鏈表的長度+1
    }
    // 插入元素
    // position為節(jié)點(diǎn)要插入的位置，data為節(jié)點(diǎn)的值
    LinkedList.prototype.insert = function (position, data) {
        // 對position進(jìn)行越界判斷，當(dāng)該值小于0或者大于鏈表長度時，不能進(jìn)行插入操作
        if (position <= 0 || position > this.length) return false;
        let node = new ListNode(data); // 創(chuàng)建新節(jié)點(diǎn)
        if (position === 0) { // 如果節(jié)點(diǎn)要插入第一個位置
            node.next = this.head; // 新節(jié)點(diǎn)指向原來的頭節(jié)點(diǎn)
            this.head = node; // 頭節(jié)點(diǎn)修改為新節(jié)點(diǎn)
        } else {
            let previous = null; // 指向前一個位置
            let current = this.head; // 指向下一個位置
            let index = 1; // 記錄循環(huán)的位置
            // 循環(huán)結(jié)束，previous和current之間就是插入的節(jié)點(diǎn)
            while (index < position) {
                previous = current;
                current = current.next;
                index++;
            }
            previous.next = node; // 在正確的位置插入元素
            node.next = current;
        }
        this.length += 1; // 長度加1
    }
    // 獲取某個位置上的元素
    LinkedList.prototype.get = function (position) {
        // 越界判斷，如果位置小于0或者大于鏈表長度，不能獲取到元素
        if (position <= 0 || position > this.length) return null;
        let index = 1; // 記錄當(dāng)前位置
        let current = this.head; // current指向頭節(jié)點(diǎn)
        // 循環(huán)結(jié)束，current指向該位置上的節(jié)點(diǎn)
        while (index < position) {
            current = current.next;
            index++;
        }
        return current.data;
    }
    // 獲取某個元素的位置
    LinkedList.prototype.indexOf = function (data) {
        let current = this.head;
        let index = 1; // 記錄元素的位置
        while (current) { // 循環(huán)遍歷鏈表
            if (current.data === data) { // 如果當(dāng)前節(jié)點(diǎn)的值等于元素的值
                return index; // 返回位置
            } else { // 如果不等于，繼續(xù)循環(huán)
                current = current.next;
                index++;
            }
        }
        return -1; // 循環(huán)結(jié)束了，說明沒找到
    }
    // 修改某個位置的元素
    LinkedList.prototype.update = function (position, data) {
        // 越界判斷
        if (position <= 0 || position > this.length) return false;
        let current = this.head;
        let index = 1;
        while (index < position) {
            current = current.next;
            index++;
        }
        current.data = data; // 修改數(shù)據(jù)
        return true;
    }
    LinkedList.prototype.removeAt = function (position) {
        if (position <= 0 || position > this.length) return false; // 越界判斷
        let current = this.head;
        if (position === 1) { // 如果刪除第一個位置上的節(jié)點(diǎn)（頭節(jié)點(diǎn)）
            this.head = this.head.next;
        } else { // 刪除其他位置的節(jié)點(diǎn)
            let index = 1; // 記錄當(dāng)前位置
            let previous = null;
            while (index < position) {
                previous = current;
                current = current.next;
                index++;
            }
            // 上一個節(jié)點(diǎn)指向當(dāng)前元素的下一個節(jié)點(diǎn)
            previous.next = current.next;
        }
        this.length--;
        return current; // 返回被刪除的節(jié)點(diǎn)
    }
}

到此這篇關(guān)于JavaScript數(shù)據(jù)結(jié)構(gòu)之鏈表各種操作詳解的文章就介紹到這了,更多相關(guān)JS鏈表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: