线性表

动态数组（实现顺序表）

• 特点：内存连续

1. 优点

   • 下标访问（随机访问）时间复杂度是O(1)
   • 尾删、尾插时间复杂度是O(1)
   • 访问元素前后相邻位置的元素非常方便

2. 缺点

   • 非末尾位置增删元素需要进行大量的数据移动

   • 搜索的时间复杂度

     • 无序数组：线性搜索O(n)
     • 有序数组：二分搜索O($\log{n}$)

     数组扩容消耗比较大

3. 注意事项

   • 数组的查找（搜索）和下标访问（随机访问）是不同的概念！ 前者是根据元素找到对应的索引，后者是根据索引给出对应的元素。

链表

• 特点：每一个节点都是在堆内存上独立new出来的，节点内存不连续

1. 优点
   • 内存利用率高，不需要大块连续内存
   • 插入和删除节点不需要移动其他节点，时间复杂度O(1)
   • 不需要专门进行扩容操作
2. 缺点
   • 内存占用量大，每一个节点多处存放地址的空间
   • 节点内存不连续，无法进行内存随机访问
   • 链表搜索效率不高，只能从头结点开始逐节点遍历
3. 总结
   • 对于使用智能指针管理的链表，常用原始指针进行遍历，使用智能指针进行节点管理
   • 对于循环链表，用cur_ptr是否等于头节点进行判断；而对于非循环链表，用cur_ptr是否为空进行判断
   • 对于单项链表，由于节点的所有权在上一个节点，因此常用双链表进行节点操作
   • 对于有尾节点的链表，需要注意边界问题。

单向链表

• 特点：
  1. 每一个节点除了数据域，还有一个next指针指向下一个节点的地址。 但是无法回退到前一个节点
  2. 末尾节点的指针域是nullptr

单向循环链表

• 特点：末尾节点的地址域存储的是首节点的地址

双向链表

• 特点：

1. 每一个节点除了数据域，还有next指针指向下一个节点，pre指针指向前一个节点
2. 头结点的pre是nullptr，末尾节点的next是nullptr

双向循环链表

• 特点：

1. 每一个节点除了数据域，还有next指针指向下一个节点，pre指针指向前一个节点
2. 头节点的pre指向末尾节点，末尾节点的pre指向头节点

栈

• 特点：先进后出，后进先出

顺序栈

依赖数组实现

链式栈

依赖链表实现

队列

• 特点：先进先出，后进后出