数据结构
- 数据结构是相互之间存在一种或者多种特定关系的数据元素的集合。数据元素之间的关系称为结构，分为以下几种：
- 集合关系
- 线性结构：一对一关系
- 树形结构：一对多关系
- 图状结构：多对多关系
- 数据元素在计算机中的存储结构分为顺序存储结构（数据相邻）和链式存储结构（借助指针）。
线性结构
- 特点如下：
- 存在唯一一个被称为第一个的元素
- 存在唯一一个被称为最后一个的元素
- 除第一个元素外，其他数据元素均只有一个前驱
- 除最后一个元素外，其他元素均只有一个后继
- 分类
- 顺序存储的线性表：顺序表（数组）
- 链式存储的线性表：链表
1.顺序表
- 查找元素时可以使用下标，时间复杂度为O(1)
- 插入或者删除元素时，极端情况下时间复杂度为O(N)，效率低
- 存储时需要合理分配空间
2.链表
为每个元素设置节点，节点包括数据域和指针域，指针域中存储指向下一个节点的指针next。
- 查找元素节点时需要遍历链表，时间复杂度为O(N)
- 插入元素到链表头时需要两步：将head的next指针赋值给新节点的next；将新节点赋值给head的next
3.队列
先进先出（FIFO）的线性表
4.栈
后进先出（LIFO）的线性表