[TOC]

线性表

线性表定义：线性表即同类型元素构成的有序序列 线性表作用：用于存储有顺序关系的同类型元素 线性表分类：

1. 数组：数组存储的数据是连续的，逻辑上相邻的元素在物理空间上也是连续的，数组是一段连续的内存空间，因此使用数组前需要预设其大小。 访问时间复杂度：O(1) 插入、删除时间复杂度：O(n) 查找时间复杂度：O(n)

2. 链表：链表由节点组成，每个节点包含一个数据域和指针域，数据域用于存储数据，指针域用于存储后继结点的位置，因此链表在物理空间上是可以不连续的。 访问时间复杂度：O(n) 插入、删除时间复杂度：O(1) 查找时间复杂度：O(n)

3. 队列：特殊的线性表，队列不支持随机访问，必须按照先进先出原则。 基于简单循环数组实现： 入队、出队时间复杂度：O(1) 基于动态循环数据实现： 入队、出队时间复杂度：O(1) 基于链表实现： 入队、出队时间复杂度：O(1)

4. 栈：特殊的线性表，栈不支持随机访问，必须按照先进后出原则。 基于简单数组实现： 入栈、出栈时间复杂度：O(1) 基于动态数组实现： 数组头为栈顶： 入栈、出栈时间复杂度为O(n) 数组尾为栈顶 入栈、出栈时间复杂度为O(1) 基于链表实现： 入栈、出栈时间复杂度为O(1)