线性数据结构：数组、受限数组（栈、队列）、线性表-Toy模板网

这篇具有很好参考价值的文章主要介绍了线性数据结构：数组、受限数组（栈、队列）、线性表。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1. 数组

数组定义

数组（Array）是有序的元素序列。属于线性结构（有且仅有一个前驱、有且仅有一个后继）。

数组特点

数组的关键在于在内存中的物理地址对应的是一段连续的内存。这意味着如果想要在任意位置删除/新增一个元素，那么该位置往后的所有元素，都需要往前挪/往后挪一个位置。假设数组的长度是 n，那么因增加/删除操作导致需要移动的元素数量，就会随着数组长度 n 的增大而增大，呈一个线性关系。所以说数组增加/删除操作对应的时间复杂度就是 O(n)。

在js中的数组比较特殊，如果我们在一个数组中只定义了一种类型的元素，比如：
const arr = [1,2,3,4]
它是一个纯数字数组，那么对应的确实是连续内存。
但如果我们定义了不同类型的元素：
const arr = ['haha', 1, {a:1}]
它对应的就是一段非连续的内存。此时，JS 数组不再具有数组的特征，其底层使用哈希映射分配内存空间，是由对象链表来实现的。
谨记“JS 数组未必是真正的数组”

2. 栈和队列（操作受限的数组）

栈

栈是一种后进先出(LIFO，Last In First Out)的数据结构。——只用 pop 和 push 完成增删的“数组”

只允许从尾部添加元素
只允许从尾部取出元素

队列

队列（Queue）是一种先进先出（FIFO，First In First Out）的数据结构。——只用 push 和 shift 完成增删的“数组”。在栈元素出栈时，我们关心的是栈顶元素（数组的最后一个元素）；队列元素出队时，我们关心的则是队头元素（数组的第一个元素）。

3. 链表

链表和数组相似，线性结构（有且仅有一个前驱、有且仅有一个后继），不同点在于，链表中，数据单位的名称叫做“结点”，而结点和结点的分布，在内存中可以是离散的。
一个内容为1->2->3->4->5的链表，在内存中的形态可以是散乱如下的：
线性数据结构：数组、受限数组（栈、队列）、线性表

在链表中，每一个结点的结构都包括了两部分的内容：数据域和指针域。JS 中的链表，是以嵌套的对象的形式来实现的：

{
    // 数据域
    val: 1,
    // 指针域，指向下一个结点
    next: {
        val:2,
        next: ...
    }
}

数据域存储的是当前结点所存储的数据值，而指针域则代表下一个结点（后继结点）的引用。
线性数据结构：数组、受限数组（栈、队列）、线性表

创建链表:

function ListNode(val) {
    this.val = val;
    this.next = null;
}
const node = new ListNode(1)  
node.next = new ListNode(2)

链表元素的添加和删除操作，本质上都是在围绕 next 指针做文章，例如在节点1和节点2之间插入节点3：
线性数据结构：数组、受限数组（栈、队列）、线性表

// 如果目标结点本来不存在，那么记得手动创建
const node3 = new ListNode(3)     
// 把node3的 next 指针指向 node2（即 node1.next）
node3.next = node1.next
// 把node1的 next 指针指向 node3
node1.next = node3

删除节点3：