在上一篇文章中我們聊了線性表的相關(guān)概念，對(duì)于線性表的獲取數(shù)據(jù)、插入數(shù)據(jù)、刪除數(shù)據(jù)的算法實(shí)現(xiàn)我們沒(méi)談，這篇文章就來(lái)談?wù)劸€性表的算法操作。市面上的教材書(shū)籍談及算法實(shí)現(xiàn)，絕大多數(shù)都是用 C 語(yǔ)言來(lái)實(shí)現(xiàn)的，在這里，我們選擇用 JavaScript 去實(shí)現(xiàn)。實(shí)際上算法和語(yǔ)言關(guān)系不大，很多數(shù)據(jù)結(jié)構(gòu)的教材也鼓勵(lì)讀者使用自己熟悉的語(yǔ)言去重寫(xiě)書(shū)上的算法代碼，今天就來(lái)做一個(gè)嘗試。

如果對(duì)線性表的相關(guān)概念還不是很熟，請(qǐng)看上一篇文章。

在下面的算法實(shí)現(xiàn)中，我們假定待被操作的 List 是一個(gè)人員名單的集合，單個(gè)數(shù)據(jù)元素包含姓名（name）和年齡（age）兩個(gè)數(shù)據(jù)項(xiàng)，為了便于查看 List ，也為了方便操作，我們使用 HTML 做了一個(gè)界面，通過(guò)界面上的操作來(lái)實(shí)現(xiàn)對(duì)線性表的插入數(shù)據(jù)、獲取數(shù)據(jù)和刪除數(shù)據(jù)的操作，界面如下：

線性表操作實(shí)例

我們知道在 JavaScript 這種高級(jí)編程語(yǔ)言中，其實(shí)已經(jīng)內(nèi)置了很多對(duì)數(shù)組直接操作的函數(shù)，如：push、splice等，但是在 C 語(yǔ)言這種底層語(yǔ)言中是沒(méi)有的，所以在下面的算法代碼中，我們不會(huì)采用這些內(nèi)置的操作函數(shù)，而是按照底層語(yǔ)言的實(shí)現(xiàn)思路和步驟，用高級(jí)語(yǔ)言去實(shí)現(xiàn)。

順序存儲(chǔ)結(jié)構(gòu)

先睹為快，查看完整代碼請(qǐng)戳：完整代碼-在線預(yù)覽。

插入數(shù)據(jù)

在線性表 List 中的第 i 個(gè)位置插入新元素 e， 實(shí)現(xiàn)思路如下：

1. 如果插入位置不合理，拋出異常；
2. 如果線性表長(zhǎng)度大于等于數(shù)組長(zhǎng)度 ，則拋出異?；騽?dòng)態(tài)增加容量；
3. 從最后一個(gè)元素開(kāi)始向前遍歷到第 i 個(gè)位置，分別將他們都向后移動(dòng)一個(gè)位置；
4. 將要插入元素填入位置 i 處；
5. 表長(zhǎng)加 1。

我們按照這個(gè)思路，用 JavaScript 實(shí)現(xiàn)如下：

/**
* 初始條件：鏈表 list 已經(jīng)存在且 1 ≤ index ≤ list.length
* 功能: 在 list 中第 index 個(gè)位置之前插入新的數(shù)據(jù)元素 data
* @param {object} data
* @param {number} index
*/
function insertItem(data, index) {
    const obj = data;
    if(index < 0 || index >= list.length) {
        alert(`非法的索引位置：${i}`);
        return;
    } else {
        for(let k = list.length - 1; k > index - 1; k--) {
            list[k + 1] = list[k];
        }
        list[index] = obj;
    }
}

算法復(fù)雜度為：O(1)。

獲取數(shù)據(jù)

獲取線性表 List 中的第 i 個(gè)位置的元素值，只要 i 的數(shù)值在數(shù)組下標(biāo)范圍內(nèi)，就把數(shù)組第 i-1 下標(biāo)的值返回即可，按照這個(gè)思路，用 JavaScript 實(shí)現(xiàn)如下：

/**
* 初始條件：鏈表 list 已經(jīng)存在且 1 ≤ index ≤ list.length
* 獲取數(shù)據(jù)
* @param {number} index
*/
function getItem(index) {
    if (index < 0 || index > list.length - 1) {
        alert(`非法的索引位置：${index}`);
        return;
    }
    for (let k = 0; k < list.length; k++) {
        if (k === index) {
            return list[k];
        }
    }
}

算法復(fù)雜度為：O(n)。

刪除數(shù)據(jù)

刪除算法的思路如下：

1. 如果刪除位置不合理，拋出異常；
2. 取出刪除元素；
3. 從刪除元素位置開(kāi)始遍歷到最后一個(gè)元素位置，分別將他們都向前移動(dòng)一個(gè)位置；
4. 表長(zhǎng)減 1。

用 JavaScript 實(shí)現(xiàn)如下：

/**
* 初始條件：鏈表 list 已經(jīng)存在且 1 ≤ index ≤ list.length
* 刪除數(shù)據(jù)
* @param {number} index
*/
function delItem(index) {
    const delList = list[index];
    if (list.length === 0) {
        alert(`線性表為空`);
        return;
    }
    if (index < 0 || index > list.length - 1) {
        alert(`非法的索引位置：${index}`);
        return;
    } else if (index <
        list.length - 1) {
        for (let k = index; k < list.length - 1; k++) {
            list[k] = list[k + 1];
        }
    }
    list.length--;
    return list;
}

算法復(fù)雜度為：O(n)。

總結(jié)

線性表的順序存儲(chǔ)結(jié)構(gòu)，在存、讀取數(shù)據(jù)時(shí)候，不管是哪個(gè)位置，時(shí)間復(fù)雜度都是 O(1)，而插入或者刪除時(shí)，時(shí)間復(fù)雜度都是 O(n)。這就說(shuō)明它比較適合元素個(gè)數(shù)不太變化，而更多是存取數(shù)據(jù)的應(yīng)用。

鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

查看完整代碼請(qǐng)戳：完整代碼-在線預(yù)覽。

插入數(shù)據(jù)

單鏈表第 i 個(gè)數(shù)據(jù)插入結(jié)點(diǎn)的算法思路是這樣的：

1. 聲明一結(jié)點(diǎn) p 指向鏈表第一個(gè)結(jié)點(diǎn)，初始化 j 從 1 開(kāi)始；
2. 當(dāng) j < i 時(shí)，就遍歷鏈表，讓 p 的指針向后移動(dòng)，不斷指向下一結(jié)點(diǎn)，j 累加 1；
3. 若到鏈表末尾 p 為空，則說(shuō)明第 i 個(gè)元素不存在；
4. 否則查找成功，在系統(tǒng)中生成一個(gè)空結(jié)點(diǎn) s；
5. 將數(shù)據(jù)元素 e 賦值給 s->data；
6. 單鏈表的插入標(biāo)準(zhǔn)語(yǔ)句 s->next=p->next; p->next=s;
7. 返回成功。

我們按照這個(gè)思路，用 JavaScript 實(shí)現(xiàn)如下：

/**
* 單鏈表插入數(shù)據(jù)
* @param {array} list
* @param {number} index
* @param {object} data
*/
function insertItem(list, index, data) {
    let obj = list;
    let k = 1;
    while(obj && index < k) {
        ++k;
        obj = obj.next;
    }
    if(!obj || k > index) {
        alert('插入位置不正確');
        return;
    }
    const sNode = new LinkNode(data, obj.next);
    obj.next = sNode;
    list.data += 1;
    return list;
}

算法復(fù)雜度為：O(n)。

獲取數(shù)據(jù)

獲取鏈表第 i 個(gè)數(shù)據(jù)的算法思路如下：

1. 申明一個(gè)節(jié)點(diǎn) p 指向鏈表第一個(gè)結(jié)點(diǎn)，初始化 j 從 1 開(kāi)始；
2. 當(dāng) j < 1 時(shí)，就遍歷鏈表，讓 p 的指針向后移動(dòng)，不斷指向下一結(jié)點(diǎn)，j 累加 1；
3. 若到鏈表末尾 p 為空，則說(shuō)明第 i 個(gè)元素不存在；
4. 否則查找成功，返回節(jié)點(diǎn) p 的數(shù)據(jù)。

我們按照這個(gè)思路，用 JavaScript 實(shí)現(xiàn)如下：

/**
* 獲取數(shù)據(jù)
* @param {array} list
* @param {number} index
*/
function getItem(list, index) {
    let j = 1;
    let obj = list.next;
    while (obj && j < index) {
        ++j;
        obj = obj.next;
    }
    if(!obj || j > index) {
        alert('元素不存在');
        return;
    }
    return obj;
}

算法復(fù)雜度為：O(n)。

由于單鏈表的結(jié)構(gòu)中沒(méi)有定義表長(zhǎng)，所以不能實(shí)現(xiàn)知道要循環(huán)多少次，因此不方便使用 for 來(lái)控制循環(huán)，其主要核心思想就是工作指針后移，這其實(shí)也是很多算法常用的技術(shù)。

刪除數(shù)據(jù)

單鏈表第 i 個(gè)數(shù)據(jù)刪除節(jié)點(diǎn)的算法思路：

1. 聲明一結(jié)點(diǎn) p 指向鏈表第一個(gè)結(jié)點(diǎn)，初始化 j 從 1 開(kāi)始；
2. 當(dāng) j < i 時(shí)，就遍歷鏈表，讓 p 的指針向后移動(dòng)，不斷指向下一個(gè)結(jié)點(diǎn)，j 累加 1；
3. 若到鏈表末尾 p 為空，則說(shuō)明第 i 個(gè)元素不存在；
4. 否則查找成功，將欲刪除的結(jié)點(diǎn) p->next 賦值給 q；
5. 單鏈表的刪除標(biāo)準(zhǔn)語(yǔ)句 p->next=q->next;
6. 將 q 結(jié)點(diǎn)中的數(shù)據(jù)賦值給 e，作為返回;
7. 釋放 q 結(jié)點(diǎn)；
8. 返回成功。

我們按照這個(gè)思路，用 JavaScript 實(shí)現(xiàn)如下：

/**
* 刪除數(shù)據(jù)
* @param {array} list
* @param {number} index
*/
function delItem(list, index) {
    let j = 1;
    let obj = list;
    while(obj.next && j < index) {
        ++j;
        obj = obj.next;
    }
    if(!(obj.next) || j > index) {
        alert('非法的刪除位置');
        return;
    }
    let item = obj.next;
    obj.next = item.next;
    list.data -= 1;
    item = null;
    return list;
}

算法復(fù)雜度為：O(n)。

總結(jié)

單鏈表的插入和刪除算法，其實(shí)都是由兩部分組成：

• 第一部分就是遍歷查找第 i 個(gè)元素
• 第二部分就是插入和刪除元素

我們已經(jīng)得出上述對(duì)單鏈表的操作算法復(fù)雜度都是 O(n)，如果在我們不知道第 i 個(gè)元素的指針位置，單鏈表數(shù)據(jù)結(jié)構(gòu)在插入和刪除操作上，與線性表的順序存儲(chǔ)結(jié)構(gòu)是沒(méi)有太大優(yōu)勢(shì)的；但如果，我們希望從第 i 個(gè)位置，插入 10 個(gè)元素，對(duì)于順序存儲(chǔ)結(jié)構(gòu)就意味著，每一次插入都需要移動(dòng) n-i 個(gè)元素，每次都是 O(n)，而對(duì)單鏈表，我們只需要在第一次時(shí)，找到第 i 個(gè)位置的指針，此時(shí)為 O(n)，接下來(lái)只是簡(jiǎn)單地通過(guò)賦值移動(dòng)指針而已，時(shí)間復(fù)雜度都是 O(1)，這就說(shuō)明對(duì)于插入或刪除數(shù)據(jù)越頻繁的操作，單鏈表的效率優(yōu)勢(shì)就越明顯。