数组 #

数组在实现上使用的是连续的内存空间，可以借助 CPU 的缓存机制，预读数组中的数据，所以访问效率更高。

数组的两个典型特性

1. 线性表（Linear List）。顾名思义，线性表就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。其实除了数组，链表、队列、栈等也是线性表结构。

2. 连续的内存空间和相同类型的数据。正是因为这两个限制，它才有了一个堪称“杀手锏”的特性：“随机访问”。但有利就有弊，这两个限制也让数组的很多操作变得非常低效，比如要想在数组中删除、插入一个数据，为了保证连续性，就需要做大量的数据搬移工作。

数组的底层实现

base_address   首地址
data_type_size 每个元素的大小

a[i]_address = base_address + i * data_type_size

面试的时候，常常会问数组和链表的区别，很多人都回答说，“链表适合插入、删除，时间复杂度 O(1)；数组适合查找，查找时间复杂度为 O(1)”。

实际上，这种表述是不准确的。数组是适合查找操作，但是查找的时间复杂度并不为 O(1)。即便是排好序的数组，你用二分查找，时间复杂度也是 O(logn)。所以，正确的表述应该是，数组支持随机访问，根据下标随机访问的时间复杂度为 O(1)。

链表 #

链表和数组相似，它们都是有序的列表、都是线性结构（有且仅有一个前驱、有且仅有一个后继）。不同点在于，链表中，数据单位的名称叫做“结点”，而结点和结点的分布，在内存中可以是离散的，所以对 CPU 缓存不友好，没办法有效预读。

链表和数组的区别 链表比较适合

链表的每个节点的 next 链接着下一个节点的地址。

链表的添加

1. 把新节点的 next 等于前置节点的 next(也就是后置节点)

2. 再把前置节点的 next 等于新节点

   javascript

   // 目前是的链表是 node1 - node2 在中间插入一个node3
   // 创建一个新节点
   const node3 = new ListNode(3);
   // 把node3的 next 指针指向 node2（即 node1.next）
   node3.next = node1.next;
   // 把node1的 next 指针指向 node3
   node1.next = node3;
   

链表的删除

1. 前置节点的 next 等于 前置节点的 next.next(直接跳过要删除的节点 直接指向后置节点)

   java

   // 当前有node1 - node3 - node2
   直接 node1.next = node1.next.next
   或者 node1.next = node3.next
   

力扣链表题 206，141，21，19，876