数组

数组是一种线性表数据结构，用一组连续的内存空间来存储数据

• 线性表： 线性表就是数据排成像一条线一样的结构，每个线性表上的数据最多只有前和后两个方向，

  其他线性表数据结构：链表、队列、栈。

• 非线性表： 数据之间不是简单的前后关系

链表

与数组不同， 他并不需要一块连续的内存空间，他可以通过指针将一组零散的内存块串联起来使用。

最常见的三种链表结构： 单链表，双向链表，循环链表。

单链表

链表通过指针将一串零散的内存块串联在一起，其中，内存块称为链表的节点，为了把所有的节点串起来，每个链表的节点除了存储数据外，还需要记录下一个链表的地址，我们把这个记录下个节点地址的指针叫做后继指针 next

头节点和尾节点两个节点比较特殊，

• 头结点用来记录链表的基地址，有了它，就可以遍历得到整条链表。
• 尾结点则指向一个空地址 null，表示这是链表的最后一个节点。

循环链表

循环链表是特殊的单链表，和单链表的区别就在于尾结点，循环链表的尾结点指向链表的头结点

双向链表

单链表只有一个方向，节点只有一个后继指针 next 指向后面的节点，双向链表则多了一个前驱指针 prev 指向前面的节点，支持双向遍历，增加了灵活性。 同样的，既然多出一个空间用来存储前驱节点，所以，当存储同样多的数据时，双向链表要比单链表占据更多的内存空间

链表的相关操作

插入节点

1
2
3

// 将节点插入到node后面
new_node->next = node->next
node = new_node

删除节点

1
2

// 删除节点node的后继节点
node->next = node->next->next

总结： 数组和链表的区别：

• 存储结构：

  • 数组： 连续的内存空间；可以借助 CPU 的缓存机制，预读数组中的数据，访问效率更高。
  • 链表： 一组零散的内存块；对 CPU 缓存不友好，没办法有效预读。

• 插入，删除操作的复杂度：

  • 数组： 数组结构的在进行插入、删除操作时，为了保证整体的连续性，需要做大量的数据迁移，时间复杂度为 O(n)。
  • 链表： 链表的存储空间本身就是不连续的，只需要关注考虑相邻接点的指针改变，总时间复杂度是 O(1)。

  （延伸：尽管单纯的删除操作， 时间复杂度是 O(1)，但删除某个节点 q，需要知道上一个节点的地址，单链表寻找上一个节点仍需遍历查找，时间复杂度为 O(n)，总时间为找+删=O(n)；）

• 随机访问：

  • 数组： 可以通过下标计算出对应的内存地址，时间复杂度为 O(1)。
  • 链表： 因为链表数据不是不是连续储存的，所以无法像数组一样根据首地址和下标计算出对应的内存地址，只能通过指针一个个节点进行遍历的方法寻找相应的节点。链表的每个节点都只知道自己的下一个节点的地址，当我们想知道第 k 个节点的时候，只能从第一个开始往下数，时间复杂度是 O(n)。