4、设计一张表格来对比顺序表、单链表、堆栈和队列的不同之处

| 特性 | 顺序表 | 单链表 | 堆栈 | 队列 |
| ---- | ---- | ---- | ---- | ---- |
| 存储结构 | 连续的内存空间 | 链式存储结构 | 可以使用顺序表或链表实现 | 可以使用顺序表或链表实现 |
| 插入操作 | 需要移动后续元素 | 只需要修改指针即可 | 只能在栈顶插入或删除元素 | 只能在队尾插入元素，在队头删除元素 |
| 查找操作 | 可以通过下标直接访问 | 需要遍历链表 | 只能查找栈顶元素 | 只能查找队头或队尾元素 |
| 内存使用 | 可能会浪费部分空间 | 没有浪费空间 | 只需要额外的栈顶指针 | 只需要额外的队头和队尾指针 |
| 应用场景 | 数据量较小且需要随机访问 | 数据量较大或经常进行插入删除操作 | 后进先出的场景 | 先进先出的场景 |

相关问题

3、设计一张表格来对比顺序表、单链表、堆栈和队列在以下3个操作的时间复杂度：计算元素 个数、插入元素、删除

| 操作 | 顺序表 | 单链表 | 堆栈 | 队列 |
| :---: | :---: | :---: | :---: | :---: |
| 计算元素个数 | O(1) | O(n) | O(1) | O(1) |
| 插入元素 | O(n) | O(1) | O(1) | O(1) |
| 删除元素 | O(n) | O(1) | O(1) | O(1) |

说明：

- 计算元素个数：顺序表可以直接通过数组长度得到，时间复杂度为O(1)；单链表需要遍历整个链表才能计算出元素个数，时间复杂度为O(n)；堆栈和队列都可以通过记录元素个数来实现O(1)的时间复杂度。
- 插入元素：顺序表需要移动后续元素，时间复杂度为O(n)；单链表可以直接在需要插入的位置插入元素，时间复杂度为O(1)；堆栈和队列也可以在需要插入的位置插入元素，时间复杂度为O(1)。
- 删除元素：顺序表需要移动后续元素，时间复杂度为O(n)；单链表可以直接删除需要删除的元素，时间复杂度为O(1)；堆栈和队列也可以直接删除需要删除的元素，时间复杂度为O(1)。

顺序表和单链表都有ListInsert()函数，请根据代码说明两者不同之处。

顺序表和单链表都有ListInsert()函数，但是两者的实现方式不同。顺序表是把待插入元素依次向后移动，然后将元素插入到相应位置；而单链表的操作则需要先找到待插入位置的前一个节点，然后将新节点插入到该位置之后。因此，顺序表的插入操作需要移动元素，时间复杂度为O(n)，而单链表只需要修改指针，时间复杂度为O(1)。