重学数据结构（三）：线性表的算法实现（JS）

在上一篇文章中我们聊了线性表的相关概念，对于线性表的获取数据、插入数据、删除数据的算法实现我们没谈，这篇文章就来谈谈线性表的算法操作。市面上的教材书籍谈及算法实现，绝大多数都是用 C 语言来实现的，在这里，我们选择用 JavaScript 去实现。实际上算法和语言关系不大，很多数据结构的教材也鼓励读者使用自己熟悉的语言去重写书上的算法代码，今天就来做一个尝试。

如果对线性表的相关概念还不是很熟，请看上一篇文章。

在下面的算法实现中，我们假定待被操作的 List 是一个人员名单的集合，单个数据元素包含姓名（name）和年龄（age）两个数据项，为了便于查看 List ，也为了方便操作，我们使用 HTML 做了一个界面，通过界面上的操作来实现对线性表的插入数据、获取数据和删除数据的操作，界面如下：

我们知道在 JavaScript 这种高级编程语言中，其实已经内置了很多对数组直接操作的函数，如：push、splice等，但是在 C 语言这种底层语言中是没有的，所以在下面的算法代码中，我们不会采用这些内置的操作函数，而是按照底层语言的实现思路和步骤，用高级语言去实现。

顺序存储结构

先睹为快，查看完整代码请戳：完整代码-在线预览。

插入数据

在线性表 List 中的第 i 个位置插入新元素 e， 实现思路如下：

1. 如果插入位置不合理，抛出异常；
2. 如果线性表长度大于等于数组长度 ，则抛出异常或动态增加容量；
3. 从最后一个元素开始向前遍历到第 i 个位置，分别将他们都向后移动一个位置；
4. 将要插入元素填入位置 i 处；
5. 表长加 1。

我们按照这个思路，用 JavaScript 实现如下：

/**
* 初始条件：链表 list 已经存在且 1 ≤ index ≤ list.length
* 功能: 在 list 中第 index 个位置之前插入新的数据元素 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;
    }
}

复制代码

算法复杂度为：O(1)。

获取数据

获取线性表 List 中的第 i 个位置的元素值，只要 i 的数值在数组下标范围内，就把数组第 i-1 下标的值返回即可，按照这个思路，用 JavaScript 实现如下：

/**
* 初始条件：链表 list 已经存在且 1 ≤ index ≤ list.length
* 获取数据
* @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];
        }
    }
}

复制代码

算法复杂度为：O(n)。

删除数据

删除算法的思路如下：

1. 如果删除位置不合理，抛出异常；
2. 取出删除元素；
3. 从删除元素位置开始遍历到最后一个元素位置，分别将他们都向前移动一个位置；
4. 表长减 1。

用 JavaScript 实现如下：

/**
* 初始条件：链表 list 已经存在且 1 ≤ index ≤ list.length
* 删除数据
* @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;
}

复制代码

算法复杂度为：O(n)。

总结

线性表的顺序存储结构，在存、读取数据时候，不管是哪个位置，时间复杂度都是 O(1)，而插入或者删除时，时间复杂度都是 O(n)。这就说明它比较适合元素个数不太变化，而更多是存取数据的应用。

链式存储结构

查看完整代码请戳：完整代码-在线预览。

插入数据

单链表第 i 个数据插入结点的算法思路是这样的：

1. 声明一结点 p 指向链表第一个结点，初始化 j 从 1 开始；
2. 当 j < i 时，就遍历链表，让 p 的指针向后移动，不断指向下一结点，j 累加 1；
3. 若到链表末尾 p 为空，则说明第 i 个元素不存在；
4. 否则查找成功，在系统中生成一个空结点 s；
5. 将数据元素 e 赋值给 s->data；
6. 单链表的插入标准语句 s->next=p->next; p->next=s;
7. 返回成功。

我们按照这个思路，用 JavaScript 实现如下：

/**
* 单链表插入数据
* @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;
}
复制代码

算法复杂度为：O(n)。

获取数据

获取链表第 i 个数据的算法思路如下：

1. 申明一个节点 p 指向链表第一个结点，初始化 j 从 1 开始；
2. 当 j < 1 时，就遍历链表，让 p 的指针向后移动，不断指向下一结点，j 累加 1；
3. 若到链表末尾 p 为空，则说明第 i 个元素不存在；
4. 否则查找成功，返回节点 p 的数据。

我们按照这个思路，用 JavaScript 实现如下：

/**
* 获取数据
* @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;
}
复制代码

算法复杂度为：O(n)。

由于单链表的结构中没有定义表长，所以不能实现知道要循环多少次，因此不方便使用 for 来控制循环，其主要核心思想就是 工作指针后移 ，这其实也是很多算法常用的技术。

删除数据

单链表第 i 个数据删除节点的算法思路：

1. 声明一结点 p 指向链表第一个结点，初始化 j 从 1 开始；
2. 当 j < i 时，就遍历链表，让 p 的指针向后移动，不断指向下一个结点，j 累加 1；
3. 若到链表末尾 p 为空，则说明第 i 个元素不存在；
4. 否则查找成功，将欲删除的结点 p->next 赋值给 q；
5. 单链表的删除标准语句 p->next=q->next;
6. 将 q 结点中的数据赋值给 e，作为返回;
7. 释放 q 结点；
8. 返回成功。

我们按照这个思路，用 JavaScript 实现如下：

/**
* 删除数据
* @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;
}

复制代码

算法复杂度为：O(n)。

总结

单链表的插入和删除算法，其实都是由两部分组成：

• 第一部分就是遍历查找第 i 个元素
• 第二部分就是插入和删除元素

我们已经得出上述对单链表的操作算法复杂度都是 O(n)，如果在我们不知道第 i 个元素的指针位置，单链表数据结构在插入和删除操作上，与线性表的顺序存储结构是没有太大优势的；但如果，我们希望从第 i 个位置，插入 10 个元素，对于顺序存储结构就意味着，每一次插入都需要移动 n-i 个元素，每次都是 O(n)，而对单链表，我们只需要在第一次时，找到第 i 个位置的指针，此时为 O(n)，接下来只是简单地通过赋值移动指针而已，时间复杂度都是 O(1)，这就说明 对于插入或删除数据越频繁的操作，单链表的效率优势就越明显 。