线性表

零个或多个数据元素的有限序列，称为线性表。

线性表是一个序列，元素之间是有顺序的，若元素多个，则第一个元素无前驱，最后一个元素无后继。
线性表元素的个数 n(n >= 0)定义为线性表的长度，当 n = 0 时，称为空表。
在较复杂的线性表中，一个数据元素可以由若干个数据项组成。

线性表的顺序存储结构

线性表的顺序存储结构，指的是用一段地址连续的存储单元一次存储线性表的数据元素。

js 实现代码

class SqList {

    constructor() {
       this.data = [];
    }
}

function getElem(sqList, index) {
    if (sqList.data.length === 0 || index < 0 || index >= sqList.data.length) {
       throw new Error('无法获取该位置的值');
    }
　  return sqList.data[index];　
}

function insertList(sqList, item, index) {
    if (index < 0 || index > sqList.data.length) {
        throw new Error('插入位置错误');
    }
    sqList.data.splice(index, 0, item);
}

function deleteList(sqList, index) {
    if (index < 0 || index >= sqList.data.length) {
        throw new Error('删除位置错误');
    }
    return sqList.data.splice(index, 1);
}

优点

• 无须为表示表中元素之间的逻辑关系而增加额外的存储空间
• 可以快速地存取表中任一位置的元素，读数据的时间复杂度是 O(1)

缺点

• 插入和删除操作需要移动大量元素，删除和插入操作的时间复杂度是 O(n)
• 当线性表长度变化较大时，难以确定存储空间的容量
• 造成存储空间的碎片

线性表的链式存储结构

线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。
在链式结构中，除了要存数据元素外，还要存储后继元素的存储地址。存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域，指针域中存储的信息称做指针或域，这两部分信息组成数据元素的存储映像，称为结点(Node)。
每个结点只包含一个指针域，叫做单链表。
链表中第一个结点的存储位置叫做头指针。
在单链表的第一个结点钱附设一个结点，称为头结点。

js 实现代码

class LinkList {

    constructor(data, next) {
       this.data = data;
       this.next = next;
    }
}

function createLink() {
    let linkList = new LinkList(0, null);
    return linkList;
}

function getElem(linkList, index) {
    let i = 0;
    let p = linkList.next;
    while (p && i < index) {
        p = p.next;
        i++;
    }
    if (!p || i > index) {
        throw new Error('无法获取该位置的值');
    }
    return p.data;
}

function insertList(linkList, e, index) {
    let i = 0;
    let p = linkList;
    while (p && i < index) {
        p = p.next;
        i++;
    }
    if (!p || i > index) {
        throw new Error('插入位置错误');
    }
    let newNode = new LinkList(e);
    newNode.next = p.next;
    p.next = newNode;
    linkList.data += 1;
}

function deleteList(linkList, index) {
    let i = 0;
    let p = linkList;
    while (p.next && i < index) {
        p = p.next;
        i++;
    }
    if (!(p.next) || i > index) {
        throw new Error('删除位置错误');
    }
    let q = p.next;
    p.next = q.next;
    linkList.data -= 1;
    return q.data;
}

function clearList(linkList) {
    let p = linkList.next;
    while (p) {
        let q = p.next;
        p = null;
        p = q;
        linkList.data -= 1;
    }
    linkList.next = null;
}

let linkList = createLink();

insertList(linkList, 15, 0);
insertList(linkList, 10, 1);
insertList(linkList, 11, 2);
console.log(getElem(linkList, 0));
console.log(getElem(linkList, 1));
console.log(getElem(linkList, 2));

deleteList(linkList, 1);
console.log(getElem(linkList, 0));
console.log(getElem(linkList, 1));

clearList(linkList);
console.log(linkList.data);

对于插入或删除数据越频繁的操作，单链表的效率优势越是明显。

单链表结构与顺序存储结构优缺点

存储分配方式

• 顺序存储结构用一段连续的存储单元依次存储线性表的数据元素
• 单链表采用链式存储结构，用一组任意的存储单元存放线性表的元素

时间性能

• 查找
  • 顺序结构存储结构 O(1)
  • 单链表 O(n)
• 插入和删除
  • 顺序存储结构需要平均移动表长一半的元素
  • 单链表在找到某位置指针后，插入和删除事件仅为 O(1)
• 空间性能
  • 顺序存储结构需要预分配存储空间，分大了，浪费，分小了容易发生上溢
  • 单链表不需要分配存储空间，只要有就可以分配，元素个数也不受限制

循环列表

将单链表中终端结点的指针端由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称循环列表。

双向链表

在单链表的每个结点中，再设置一个指向其前驱结点的指针域，成为双向链表。

class DulSqList {

    constructor(data, next, prior) {
       this.data = data;
       this.next = next;
       this.prior = prior;
    }
}