1、数组 Array

1.1、概念

数组（Array）是一种线性表结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。

1.2、特性

1. 线性表（Linear List）
2. 连续的内存空间和相同类型的数据

比如长度为10的 int 类型的数组 int[] a = new int[10]，计算机给数组a[10]，分配了一块连续的内存空间 1000~1039，其中，内存块首地址为 base_address = 1000。

计算机会给每个内存单元分配一个地址，计算机通过地址来访问内存中的数据。计算机需要随机访问数组中某个元素时，会通过下面寻址公式

a[i]_address = base_address + i * data_type_size

其中，data_type_size 表示数组中每个元素大小，例子中是int类型，所以为4个字节。

二维数组的内存寻址公式，对于 m*n 的数组，a[i][j](i<m, j<n)

address = base_address + ( i * n + j) * type_size

1.3、小问题

数组和链表的区别？

数组支持随机访问，根据下标随机访问的时间复杂度为O(1)；链表适合插入、删除，时间复杂度为O(1)。

1.4、插入操作

1. 低效插入：将一个数据插入到数组的第k个位置，第k~n这部分元素都顺序往后挪一位。最优时间复杂度为O(1)，即数组的末尾插入，不需要移动数据。最坏时间复杂度为O(n)，数组开头插入，所有数据挪一位。平均复杂度为O(n)
2. 改进：只更换目标元素，假设数组a[10]包含 a,b,c,d,e，我们要插入x到a[3]，只需要将a[3]赋值为x，a[5]赋值为d，最后顺序为 a,b,c,x,e,d。时间复杂度为O(1)

1.5、删除操作

1. 低效删除：为了内存的连续，删除时需要搬移数据，时间复杂度和插入一致。
2. 改进：将多次删除操作集中在一起执行。

比如，数组a[10]中存储了：a,b,c,d,e,f,g,h，想要依次删除a,b,c

为了避免每次删除都要搬移元素，可以先记录要删除的元素，等数组没有更多内存空间时，再触发一次真正的删除操作

1.6、数据访问越界问题

int main(int argc, char* argv[]){
    int i = 0;
    int arr[3] = {0};
    for(; i<=3; i++){
        arr[i] = 0;
        printf("hello world\n");
    }
    return 0;
}

该代码会无限打印"hello world"，因为数组大小为3，a[0]，a[1]，a[2]，但是for循环的结束条件是 i <= 3，所以i=3的时候，数组a[3]访问越界。此时访问的是在开头定义的变量 i 的地址，那么a[3] = 0， 它指向的地址变量i也就变为了0，就导致了无限循环。这其实跟编译器有关，如果启动了堆栈保护，就只会循环4次。并且跟栈的方向有关，在linux中，栈是向上生长，x86中，栈是向下生长。

2、链表 Linked List

2.1、概念

链表（Linked list）是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现。

内存块称为链表的“结点”，记录下个结点地址的指针称为“后继指针”。

2.2、分类

1、单链表

第一个结点称为头结点，最后一个结点称为尾结点。其中，头结点用来记录链表的基地址，以此来遍历得到整条链表，尾结点的指针指向一个空地址NULL，表示链表上最后一个结点。

1. 插入和删除操作的时间复杂度为O(1)，因为只需要考虑相邻节点的指针变化
2. 查找的时间复杂度为O(n)，因为地址不连续，需要根据指针挨个遍历结点，知道找到为止

2、循环链表

在单链表的基础上，尾结点的指针指向了链表的头结点。

3、双向链表

每个结点都有两个指针，一个指向后面结点的后继指针next，一个指向前面结点的前驱指针prev。

因为双向链表需要额外的两个空间来存储后继结点和前驱结点的地址，会比单链表占用更多的内存空间。以为它支持双向遍历，可以在O(1)时间复杂度的情况下找到前驱结点，在某些情况下的插入、删除等比较高效。

从删除操作来看，一般为两种情况：

• 删除结点中“值等于某个给定值”的结点

虽然单向链表和双向链表的单纯删除操作时间复杂度为O(1)，但遍历查找的时间才是主要耗时，对应的时间复杂度为O(n)

• 删除给定指针指向的结点

已经找到要删除的结点，但删除某个结点q需要知道其前驱节点，而单链表不支持直接获取，需要从头结点开始遍历，知道p->next=q，说明p是q的前驱结点，时间复杂度为O(n)。而双向链表可以直接获取，时间复杂度为O(1)。

4、双向循环链表

3、数组和链表的区别

3.1、从底层的存储结构来看

• 数组 需要一块连续的内存空间来存储
• 链表 通过“指针”将一组零散的内存块串联起来使用

3.2、从性能上来看

3.3、实际使用

1. 数组需要大小固定，占用整块连续内存空间，如果声明的长度过大，没有足够的连续空间，会导致“内存不足”。举个极端例子，一个数组存储了1GB大小的数据，此时该内存已满，需要再插入数据，它会申请一个1.5GB大小的存储空间，并把原来的1GB数据拷贝到新的空间上，非常耗时。
2. 链表没有大小限制，支持动态扩容，因为需要存储指针，所占内存会稍微大点。并且对链表进行频繁的插入、删除操作，会导致频繁额度内存申请和释放，容易造成内存碎片，在一些语言中，会导致GC（垃圾回收）。

4、栈 Stack

4.1、概念

一种“操作受限”的线性表，只允许在一端插入和删除数据。对数据的操作原则为：先进后出，后进先出。

4.2、实现

栈既可以用数组实现，称为顺序栈，也可以用链表实现，称为链式栈 。对于一个固定大小的栈，其

• 时间复杂度：O(1) 只涉及栈顶个别数据操作
• 空间复杂度：O(1) 只维护在入栈和出栈过程中的链式变量存储空间

对支持动态扩容的顺序栈，需要底层依赖一个支持动态扩容的数组，当栈满了之后，申请一个更大的数组，将原有数据复制到新数组中，根据均摊分析法，均摊时间复杂度为O(1)。

4.3、实际应用

1、栈在函数调用中的应用

操作系统给每个县城分配了一块独立的内存空间，这块内存空间被组织成“栈”的数据结构，用来存储函数调用时的临时变量。每进入一个函数，就会将临时变量作为一个栈帧入栈，当被调用函数执行完成，返回之后，将这个函数对应的栈帧出栈。

int main() {
   int a = 1; 
   int ret = 0;
   int res = 0;
   ret = add(3, 5);
   res = a + ret;
   printf("%d", res);
   reuturn 0;
}

int add(int x, int y) {
   int sum = 0;
   sum = x + y;
   return sum;
}

其具体调用如图

2、表达式求值

对于正常算术运算，如34+13*9+44-12/3，在运行时，编译器通过两个栈来实现。一个保存操作数的栈，另一个保存运算符的栈。依次按两种类型入栈。

当前运算符，如果比运算符栈顶元素的优先级高，就将运算符压入栈；如果比栈顶元素的优先级低或者相同，从运算符栈中取栈顶运算符，从数字栈的栈顶取出2个数字，进行计算，将计算的结果压入数字栈，继续操作。

5、队列 Queue

5.1、概念

一种“操作受限”的线性表，进行插入操作的端称为队尾，进行删除操作的端称为队头。对数据的操作原则为：先进先出。

5.2、实现

1、顺序队列

基于数组实现的队列叫顺序队列

通过定义两个指针：一个是head指针，指向头；一个是tail指针，指向队尾。

考虑到，当队列发生出队操作，导致head指针向后移动，导致head~tail之间已满时，会发送整体数据搬移。所以这里需要在已经满队列，并有新数据入队时，将当前head~tail之间，整体搬移到数组0的位置。

2、链表队列

入队时，tail->next = new_code, tail = tail->next；出队时，head = head->next

3、循环队列

为了防止tial==n的时候，发生数据搬移，通过环形的循环队列来解决。

当队列满的时候，tail=3，head=4，n=8，即，判断队列满的条件为：(tail+1)%n=head。

满队列的时候，tail指针的位置是空的，所以会浪费一个数组的存储空间。

5.3、实际应用

1、阻塞队列

在队列为空的时候，从头取数据就会被阻塞，因为没有数据可取，直到存在数据才返回；

在队列满的时候，插入数据就会被阻塞，因为队列已经满了，直到有空闲位置再插入。

基于阻塞队列实现的“生产者 - 消费者”模型。

2、并发队列

线程安全的队列成为并发队列。

最简单的方式是在enqueue()、dequeue()的时候加锁，但锁粒度大，导致并发度降低。

实际上，基于数组的循环队列，利用CAS原子操作，可以实现高效的并发队列。

6、树 Tree

N个结点构成的有限集合。 树中有一个称为”根(Root)”的特殊结点 其余结点可分为若干个互不相交的树，称为原来结点的”子树”。A节点是B节点的父节点，B节点是A节点的子节点，B、C、D为兄弟节点，E为根节点，G、H、I、J、K、L为叶子节点。

1、二叉树 Binary Tree

每个节点最多有两个子节点，分别是左子节点、右子节点。

• 满二叉树：叶子节点全部在最底层，除叶子结点外，每个节点都有左右两个子节点
• 完全二叉树：叶子节点都在最底下两层，最后一层的叶子结点都靠左排列，并且除了最后一层，其他层的节点个数都达到最大。

1、如何存储一颗二叉树

1. 基于指针或引用的二叉链式存储法（大部分二叉树的实现）

每个节点有三个字段，一个存储数据，另外两个指向左右子节点的指针。

2. 顺序存储法（针对完全二叉树）

把根节点放在下标 i = 1的位置，那么左子节点存储在下标 2*i = 2 的位置，右子节点存储在 2*i+1 = 3的位置，以此类推。

上面是一颗完全二叉树，仅浪费了下标为 0 的存储位置，如果是非完全二叉树，会浪费较多的存储空间，

2、二叉树遍历

• 前序遍历：对于树中任意节点来说，先打印这个节点，然后再打印它的左子树，最后打印它的右子树
• 中序遍历：对于树中任意节点来说，先打印它的左子树，然后再打印它的本身，最后打印它的右子树

• 后序遍历：对于树种任意节点来说，先打印它的左子树，然后再打印它的右子树，最后打印这个节点本身

# 树
class TreeNode():
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

# 前序遍历
def pre_order(root):
    if root:
        yield root.val
        yield from pre_order(root.left)
        yield from pre_order(root.right)

# 中序遍历
def in_order(root):
    if root:
        yield from pre_order(root.left)
        yield root.val
        yield from pre_order(root.right)

# 后续遍历
def post_order(root):
    if root: 
        yield from pre_order(root.left)
        yield from pre_order(root.right)
        yield root.val

时间复杂度为 O(1)

2、二叉查找树 Binary Search Tree

又称二叉排序树

在树种的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值。

# 初始化 树
class TreeNode:
    def __init__(self, val=None):
        self.val = val
        self.left = None
        self.right = None
        self.parent = None

1、查找操作

先取根节点，如果它等于我们要查找的数据，那就返回。如果要查找的数据比根节点的值小，那就在左子树中递归查找；如果要查找的数据比根节点的值大，那就在右子树中递归查找。

def search(self, data):
	assert(isinstance(data, int))
    # 所有查找到的节点
    ret = []
    n = self.root
    while n:
        if data < n.val:
            n = n.left
        else:
            if data == n.val:
                ret.append(n)
            n = n.right
    return ret

2、插入操作

如果要插入的数据比节点数据大，并且节点的右子树为空，就将新数据直接插到右子节点的位置；如果不为空，就再递归遍历右子树，查找插入位置。同理，如果要插入的数据比节点数据小，则相反。

def insert(self, data):
	assert(isinstance(data, int))
    # 如果根节点不存在，新建
    if self.root is None:
        self.root = TreeNode(data)
    else:
        n = self.root
        while n:
            p = n
            if data < n.val:
                n = n.left
            else:
                n = n.right
        # 构建该节点
        new_node = TreeNode(data)
        new_node.parent = p
        if data < p.val:
			p.left = new_code
        else:
            p.right = new_code
    return True

3、删除操作

该操作需要分为三种情况

1. 如果删除的节点没有子节点，直接将父节点中，指向要删除节点的指针置为null。即删除节点55
2. 如果要删除的节点只有一个子节点，那么只更新父节点中，指向要删除节点的指针，让它指向要删除节点的子节点。即删除节点13

3. 如果要删除的节点有两个子节点，需要找到这个节点的右子树的最小节点，把他替换到要删除的节点上。然后再删除这个最小节点，因为最小节点肯定没有左子节点。即删除节点18

4、查找最值

1. 查找最小值：递归遍历左子树，直到最后一个叶子节点
2. 查找最大值：递归遍历右子树，直到最后一个叶子节点

def get_min(self, data):
	if self.root in None:
        return None
    n = self.root
    while n:
        n = n.left
    return n.val    

5、排序树

通过中序遍历二叉树，可以输出有序的数据序列，时间复杂度为O(n)

def in_order(self):
	if self.root in None:
        return []
    return self._in_order(self.root)

# 中序遍历
def _in_order(self, node):
    if node is None:
        return []
    ret = []
    n = node
    ret.extend(self._in_order(n.left))
    ret.append(n.val)
    ret.extend(self._in_order(n.right))
    
    return ret

3、红黑树 Red-Black Tree

1、定义

一种不严格的平衡二叉查找树，时间复杂度O(logn)其要求：

• 根节点是黑色的
• 每个叶子节点都是黑色的空节点（NIL），也就是，叶子节点不存储数据

• 任何相邻的节点都不能同时为红色，如 节点和它的父节点不能同时为黑色
• 每个节点，从该节点到其可达叶子节点的所有路径，都包含相同数目的黑色节点

2、左旋 rotate left 和 右旋 rotate right

1. 左旋：将 x 节点移动到该位置的左子节点，并将该位置的右子节点 y 的左子节点 b 移动到 x 节点的右子节点。将该位置的右子节点 y 放到该位置，节点 r 作为现在 y 节点的右子节点。
2. 右旋：将 x 节点移动到该位置的右子节点，并将该位置的左子节点 y 的右子节点 b 移动到 x 节点的左子节点。将该位置的左子节点 y 放到该位置，节点 a 作为现在 y 节点的左子节点。

4、递归树

利用递归树来求解时间复杂度

1、快速排序

假设每次分区的大小比例为 1：k，当 k = 9 的时候，也就是说，每次分区都很不均匀，一个分区是另一个分区的9倍，转为为递归树是：

快排中，每次分区都要遍历待分区区间的所有数据，所以，每一层分区操作所有遍历的数据的个数之和就是n。

快排的结束条件就是 待排序的小区间，大小为 1 ，也就是叶子节点里的数据规模是1，即树的高度。从根节点n到叶子节点 1，递归树中最短的路径每次都乘以 1/10，最长的一个路径每次都乘以 9/10。那么最短路径是 log₁₀ n，最长路径是 log _10/9 n，根据大O表示法，即为O(logn)

所以快排的时间复杂度为 O(nlogn)

2、斐波那契数列

def f(n):
    if n == 1: return 1
	if n == 2: return 2
	return f(n-1) + f(n-2)

转化为递归树

f(n)分解为 f(n-1)和f(n-2)，每次数据规模都是 -1 或 -2 ，叶子节点的数据时 1或者 2。所以，从根节点走到叶子节点，每条路径长短不一。最长，即每次都是 -1，为n；最短，即每次都是 -2， 为 n/2。

上面每次分解之后的合并操作，时间消耗记为 1，所以，从上往下，1，2，,4，一直到第k层，为2^k-1

• 如果路径长度都是n，那么总和就是

• 如果路径长度都是n/2，那么总和就是

所以时间复杂度介于 O(2ⁿ)和O(2^n/2)

3、全排列

n个数据的所有排列情况

如果确定了最后一位数据，那么就变成了求剩下 n-1 个数据的排列问题。而最后一位数据可以是n个数据中任意一个，因此它的取值就有n种情况。所以 该问题就转化为了 n 个 “n-1 个数据的排列”的子问题。

假设数组中存储的是1，2， 3...n。
        
f(1,2,...n) = {最后一位是1, f(n-1)} + {最后一位是2, f(n-1)} +...+{最后一位是n, f(n-1)}。

第一层分解有 n 次交换操作，第二层有 n个节点，每个节点分解需要 n-1 次交换，总交换次数就是 n(n-1)，第三层总的交换次数就是 n(n-1)(n-2)

n + n*(n-1) + n*(n-1)*(n-2) +... + n*(n-1)*(n-2)*...*2*1

最后一个数 n(n-1)(n-2)...21 等于 n！，前面 n-1 个数 都小于最后一个数，所以总和肯定小于 n *n!

所以时间复杂度介于 O(n!)，O(n*n!)

7、堆 Heap

• 堆是一个完全二叉树
• 堆中每一个节点的值都必须大于等于（或小于等于）其子树中每个节点的值

1、存储一个堆

可以单纯地通过数组的下标，就可以找到一个节点的左右节点和父节点。

其中，数组中下标为 i 的节点的左子节点，就是下标为 i*2的节点，右子节点就是下标为 i*2+1 的节点，父节点就是下标为 i/2 的节点。

2、插入元素

将新插入的元素放到堆的最后时，已经不符合堆的特性，就是需要重新调整，让其满足堆的特性，这个过程称为 堆化。

1、从下往上堆化

顺着节点所在路径，向上或向下，对比交换

因为一个包含n个节点的完全二叉树，树的高度不超过 logn，堆化的过程是顺着路径比价交换的，所以时间复杂度也为 O(logn)。

3、删除元素

堆顶元素存储的就是堆中数据的最大值或最小值。

2、从上往下堆化

如果构造的是大顶堆，堆顶元素就是最大元素，当删除堆顶元素的时候，将最后一个节点放在堆顶，然后利用同样的父子节点对比方法。

对于不满足父子节点大小关系的，互换两个节点，重复这个过程，直到父子节点满足大小关系。

因为一个包含n个节点的完全二叉树，树的高度不超过 logn，堆化的过程是顺着路径比价交换的，所以时间复杂度也为 O(logn)。

8、图 Graph

1、名词

图中的元素成为 顶点（vertex）

一个顶点可以与任意其他顶点建立连接关系，该关系称为 边（edge）

一个顶点相连接的边的条数，称为顶点的 度（degree）

无向图：

顶点的入度（In-degree），表示有多少条边指向这个顶点；

顶点的出度（Out-degree），表示有多少条边是以这个顶点为起点，指向其他顶点。

有向图：

带权图（weighted graph）：每条边都有一个权重（weight）

3、存储方法

1、邻接矩阵 Adjacency Matrix

邻接矩阵的底层依赖一个二维数组。对于无向图来说，如果顶点 i 与顶点 j 之间有边，我们就将 A[i][j]和 A[j][i]标记为 1；对于有向图来说，如果顶点 i 到顶点 j 之间，有一条箭头从顶点 i 指向顶点 j 的边，那我们就将 A[i][j]标记为 1。同理，如果有一条箭头从顶点 j 指向顶点 i 的边，我们就将 A[j][i]标记为 1。对于带权图，数组中就存储相应的权重。

• 优点：矩阵保存，运算方便，查询时间快
• 缺点：存储方法浪费存储空间，对于无向图来说，其 A[i][j] 与 A[j][i] 是相等的，所以，其对角线上下划分，有一半是浪费的。

2、邻接表 Adjacency List

每个顶点对应的链表里面，存储的是指向的顶点。

• 优点：节省空间
• 缺点：查询耗费时间

改进：将邻接表中的链表改为平衡二叉树，在实际开发中，可以选择红黑树，来快速查找两个顶点之间是否存在边。也可以将链表改为 有序动态数组，通过二分查找来快速定位两个顶点是否存在边。

如果存在比如查找某个用户关注了哪些用户，可以用邻接表；

如果某个用户都被哪些用户关注了，也就是用户的粉丝列表，需要用逆邻接表（存储指向这个顶点的顶点）