一、数组

内存结构：连续内存
寻址：
a[x] = base + size x
例如
base=1000,size=4
a[2] = 1000 + 4 2 = 1008
特点：
寻址快

二、链表

内存结构：非连续内容+next指针

1、遍历

2、查找

3、链表头插

4、链表尾插

5、链表尾插优化一：添加tail指针

6、链表尾插优化二：添加虚拟头结点

7、在链表给定的结点后插入

8、删除链表给定的结点之后的结点

9、删除给定的结点

三、链表解题技巧

链表相关的题目都会涉及到「遍历」，核心是通过「画图距离」确定遍历的「三要素」:

1、遍历结束的条件

p==null or p.next==null

2、指针的初始值

p=head or …

3、遍历的核心逻辑

看题目要求

特殊情况处理

是否需要对头结点、尾节点、空链表做特殊处理

引入虚拟节点

是否可以通过添加虚拟节点简化编程

4、其他链表