Lang's blog

# 数组

数组（Array），是有限个相同类型的变量所组成的有序集合，数组中的每一个变量被称为元素。

# 特点

  • 数组中的每一个元素也有着自己的“下标”，下标从0开始
  • 数组在内存当中顺序存储，，可以很好地实现逻辑上的“顺序表”

什么叫做顺序存储呢？
内存是由一个个连续的内存单元所组成的，每一个内存单元都有着自己的地址。在这些内存单元中，有些被其他数据占用了，有些是空闲的。
数组中的每一个元素，都存储在小小的内存单元当中，并且元素之间紧密排列，既不能打乱存储顺序，也不能“跳过”存储单元。

上面图中，蓝色的格子代表着空闲的存储单元，紫色的格子代表已占用的存储单元，而绿色的连续格子，代表着数组在内存中的位置。

# 操作

# 查找

var array = [1, 2, 3, 4]

console.log(array[0])  // 1
1
2
3

通过下标直接读取array[0] ,时间复杂度为O(1)。

# 更新

var array = [1, 2, 3, 4]

array[0] = 0
console.log(array)  // [0, 2, 3, 4]
1
2
3
4

更新直接利用数组下标，就可以把新的值赋给该元素，时间复杂度为O(1)。

# 插入

插入时，数组的实际元素数量有可能小于数组的长度，比如下面的情形：

由此，数组插入元素的操作分成了三种情况：尾部插入、中间插入、以及超范围插入。

  • 尾部插入，是最简单的情况，直接把插入的元素放在数组尾部的空闲位置即可，等同于更新元素操作。
  • 中间插入，首先把插入位置以及后面的元素向后错开，腾出地方，再把要插入的元素放到对应的数组位置上。
  • 超范围插入，需要对数组进行扩容，再把旧数组的元素通通复制过去

插入时，后面的每个元素都要跟着移动位置，因此时间复杂度为O(n)。

# 删除

数组的删除操作和插入操作是相反的过程，如果删除的元素位于数组中间，其后的元素都需要向前挪一位。时间复杂度为O(n)。

# 时间复杂度

操作 复杂度
查询 O(1)
修改 O(1)
插入 O(n)
删除 O(n)

# 链表

链表（Linked List），它是一种在物理上非连续、非顺序的数据结构，由若干个节点（node）所组成。

节点是链表的基本单元

  • 单向链表的每一个节点都包含两个部分，一部分是存放数据的变量data，一部分是指向下一个节点的指针next，终点指向null。
  • 双向链表比单向链表稍微复杂一些，每一个节点除了拥有data和next指针，还拥有指向前置节点的prev指针。

# 存储方式

数组在内存中占用了连续完整的存储空间。

而链表则是采用了“见缝插针”的方式，每一个节点分布在内存的不同位置，依靠next指针关联起来。这样可以灵活有效地利用零散的碎片空间。

# 操作

# 查找

在查找元素时，链表不像数组那样可以通过下标快速定位元素，只能是从头节点向后，一个个节点逐一来查找。

比如给定一个链表，我们要查找从头节点开始的第3个节点：

  1. 第1步，查找的指针定位到头节点
  2. 第2步，根据头节点的next指针，定位到第2个节点
  3. 第3步，根据第2个节点的next指针，定位到第3个节点，查找完毕

链表中的数据只能够按顺序进行访问，最坏时间复杂度是O（n）。

# 更新

如果不考虑查找节点的过程，数组和链表的更新过程都同样简单，直接把旧数据替换成新数据即可，时间复杂度为O(1)。

# 插入

和数组类似，链表插入节点时，同样分为三种情况：

  • 尾部插入，是最简单的情况，把最后一个节点的next指针指向新插入的节点即可
  • 头部插入，可以分成两个步骤：
    1. 把新节点的next指针指向原先的头节点
    2. 把前置节点的next指针，指向刚刚插入的新节点。
  • 中间插入，同样分为两个步骤：
    1. 把新节点的next指针，指向前置节点next所指向的位置。
    2. 把前置节点的next指针，指向刚刚插入的新节点。

只要内存空间允许，链表能插入的元素是无穷无尽的，并不需要像数组那样考虑扩容的问题。

# 删除

链表的删除操作同样分为三种情况：

  • 尾部删除，是最简单的情况，把倒数第二个节点的next指向空即可：
  • 头部删除，把链表的头节点设为原先头节点的next即可：
  • 中间删除，只需把要删除节点的前置节点的next指针，直接指向要删除元素的后继节点即可

# 时间复杂度

查找：时间复杂度是O(n)
如果不考虑更新，插入，删除之前查找元素的过程，只考虑纯粹的更新,插入,删除操作，时间复杂度都是O（1）。

# 数组和链表的对比

# 数组的优势

拥有非常高效的随机访问能力，只要给出下标，就可以用常量时间找到对应元素。

# 数组的劣势

体现在插入和删除方面。由于数组元素连续紧密地存储在内存中，插入删除都导致大量元素被迫移动，影响效率。

数组所适合的是 读多写少 的场景

# 链表的优势

在于灵活的插入和删除，如果需要在尾部频繁插入删除，用链表更合适一些。

# 链表的劣势

无法根据下标进行快速定位，只能从链表头节点开始，一个一个往下去找。

链表所适合的是 写多读少 的场景

# 性能比较

← 栈和队列 →