数据结构的的储存方式

也就是数据结构在内存中真正的实现方式，其实只有两种：数组（顺序存储）和链表（链式存储）。

一般来说：用数组实现的话，就会遇到扩容问题，因为数组在内存中是连续的嘛，如果是用链表实现的话就没有这个问题，因为链表的节点可以在内存中跳跃，但是因此就失去了随机访问的特性，不连续就无法推断某个点在内存中的位置。

详细讲：

数组：由于是紧凑连续存储,可以随机访问，通过索引快速找到对应元素，而且相对节约存储空间。但正因为连续存储，内存空间必须一次性分配够，所以说数组如果要扩容，需要重新分配一块更大的空间，再把数据全部复制过去，时间复杂度 O(N)；而且你如果想在数组中间进行插入和删除，每次必须搬移后面的所有数据以保持连续，时间复杂度 O(N)。

链表：因为元素不连续，而是靠指针指向下一个元素的位置，所以不存在数组的扩容问题；如果知道某一元素的前驱和后驱，操作指针即可删除该元素或者插入新元素，时间复杂度 O(1)。但是正因为存储空间不连续，你无法根据一个索引算出对应元素的地址，所以不能随机访问；而且由于每个元素必须存储指向前后元素位置的指针，会消耗相对更多的储存空间。

数据结构的基本操作

增删改查，没什么好说的，不同的数据结构实际上也是为了适应不同情况环境下的增删改查

拿查来说，就是遍历和访问，大致有两种：

1. 线性的，以通过 while for 迭代为代表
2. 非线性的，以递归为代表

简单看下链表的遍历：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

/* 基本的单链表节点 */
class ListNode {
    public:
        int val;
        ListNode* next;
};

void traverse(ListNode* head) {
    for (ListNode* p = head; p != nullptr; p = p->next) {
        // 迭代访问 p->val
    }
}

void traverse(ListNode* head) {
    // 递归访问 head->val
    traverse(head->next);
}

简单想一下：数组的遍历显然是线性循环遍历的，二叉树遍历显然是通过递归实现的非线性的

1
2
3
4
5
6
7
8
9
10
11

/* 基本的二叉树节点 */
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
};

void traverse(TreeNode* root) {
    traverse(root->left);
    traverse(root->right);
}

那N岔树呢？N岔树不过比二叉树多几个子节点而已，你在上述代码中把左右子节点用一个容器装起来，然后下面遍历子节点时加个循环不就得了？

继续推开，图不就是几颗N岔树？（其实也不是，因为图可能不同分叉上的子节点会连在一起，也就是环，但也无伤大雅，搞个布尔数组做标记就行）