0. 简介
- 线性表是具有 n个 相同类型元素 的有限序列 (n>=0)
- 常见的线性表有：
数组、链表、栈、队列、哈希表(散列表)
1. 数组（Array）
- 数组(Array)：是一种 顺序存储 的线性表，所有元素的内存地址 是连续的
- java中内置动态数组类：java.util.ArrayList
数组
2. 链表（Linked List）
- 链表(Linked List)：是一种 链式存储 的线性表，所有元素的内存地址 不一定是连续的
- java中内置链表类：java.util.LinkedList
(1) 链表
链表
(2) 双向链表
双向链表
(3) 循环链表
循环链表
(4) 双向循环链表
双向循环链表
(5) 虚拟头结点
- 虚拟头结点：在最前面增加虚拟的头结点(不存储数据)
虚拟头结点
(6) 复杂度分析
复杂度分析
- 动态数组：开辟、销毁内存空间的次数相对 较少，但可能 造成内存空间浪费。（可以通过缩容解决）
- 双向链表：开辟、销毁内存空间的次数相对 较多，但不会 造成内存空间浪费。
3. 栈（Stack）
- 栈(Stack)：是一种特殊的线性表，只能在 一端 进行操作
- 入栈(push)：往栈中 添加元素 的操作
- 出栈(pop)：往栈中 移除元素 的操作
- LIFO(Last In First Out)：后进先出的原则
栈
4. 队列（Queue）
(1) 队列
- 队列(Queue)：是一种特殊的线性表，只能在 头尾两端 进行操作
- 入队(enQueue)：只能从 队尾(rear) 添加元素
- 出队(deQueue)：只能从 队头(front) 移除元素
- FIFO(First In First Out)：先进先出的原则
队列
(2) 双端队列
- 双端队列(Deque)：是能在 头尾两端 添加、删除的队列
deque：double ended queue
双端队列
(3) 循环队列
- 循环队列(Circle Queue)：
- 循环双端队列(Circle Deque Queue)：可以进行 两端 添加、删除操作的循环队列
