常用数据结构
常用数据结构的简要总结
数组
1. 介绍
- 数组可以存储基本数据类型，字符串以及对象（存的是引用）
- 适合查询多，增删少的情景
2. 优缺点
-
优点
- 按照索引查询元素速度快
- 可以按照索引遍历数组
-
缺点
- 数组的大小固定后就无法扩容
- 插入、删除中间的元素时，会移动其他的元素，效率低
- 数组只能存储同一类元素
链表
1. 介绍
- 链表是物理存储单元上非连续的、非顺序的存储结构
- 数据元素的逻辑顺序是通过链表的指针地址实现
- 每个元素包含两个结点，一个是存储元素的数据域 (内存空间)，另一个是指向下一个结点地址的指针域
- 根据指针的指向，链表能形成不同的结构，例如单链表，双向链表，循环链表等
- 适合查询少，增删多的情景
2. 优缺点
-
优点
- 不需要初始化容量，可以任意加减元素
- 添加、删除元素时只需要改变前后两个元素结点的指针域指向地址即可，效率高
-
缺点
- 因为含有大量的指针域，占用空间较大
- 查找元素需要遍历链表来查找，非常耗时
栈
1. 介绍
- 栈是一种特殊的线性表
- 先进后出，后进先出
- 栈常应用于实现递归功能方面的场景
- 添加元素叫入栈，取出元素叫出栈
2. 实现
class ArrayStack<T> {
private T data[];
private int maxSize;
private int top;
//构造函数初始化
public ArrayStack(int maxSize) {
this.maxSize = maxSize;
this.data = (T[]) new Object[maxSize];
this.top = -1;
}
//判空
public boolean isEmpty() {
return top <= -1;
}
//判满
public boolean isFull() {
return top >= maxSize - 1;
}
//压栈
public boolean push(T value) {
if (isFull()) {
return false;
}
top++;
data[top] = value;
return true;
}
//出栈
public T pop() {
if (isEmpty()) {
return null;
}
T temp = data[top];
data[top] = null;
top--;
return temp;
}
}
队列
1. 介绍
- 队列是一种特殊的线性表
- 先进先出
- 添加元素叫入队，取出元素叫出队
- 常用于阻塞队列
2. 实现
class ListQueue<T> {
private List<T> data;
private int length;
//构造函数初始化
public ListQueue() {
this.data = new ArrayList<>();
this.length = 0;
}
//入队
public boolean push(T value) {
length++;
return data.add(value);
}
//出队
public T pop() {
if (data.size() > 0) {
return data.remove(0);
}
return null;
}
}
class ArrayQueue<T> {
private T data[];
private int index;//队尾元素所在的位置
public ArrayQueue(int size) {
this.data = (T[]) new Object[size];
this.index = -1;
}
//入队
public boolean push(T value) {
if (index==data.length-1){
return false;
}
index++;
data[index] = value;
return true;
}
//出队
public T pop() {
if(index==-1){
return null;
}
T temp = data[0];
move();
return temp;
}
//移动元素
private void move() {
for (int i = 0; i < index; i++) {
data[i] = data[i + 1];
}
index--;
}
}
//循环队列
class ArrayQueueCycle<T> {
private T data[];
private int front;
private int rear;//队尾元素所在的位置
public T[] getData() {
return data;
}
public int getFront() {
return front;
}
public int getRear() {
return rear;
}
public ArrayQueueCycle(int size) {
this.data = (T[]) new Object[size];
this.front = 0;
this.rear = -1;
}
//入队
public boolean push(T value){
if(rear!=-1 && (rear+1)%data.length==front){ //判满
return false;
}
rear=(rear+1)%data.length;
data[rear] = value;
return true;
}
//出队
public T pop(){
if(rear==front){//判空
return null;
}
T temp = data[front];
data[front] = null;
front=(front+1)%data.length;
return temp;
}
}
树
1. 介绍
- 每个节点有零个或多个子节点
- 没有父节点的节点称为根节点
- 每一个非根节点有且只有一个父节点
- 除了根节点外，每个子节点可以分为多个不相交的子树
- 结点拥有的子树数目称为结点的度
2. 二叉树
- 每个结点最多有两颗子树，结点的度最大为2
- 左子树和右子树是有顺序的，次序不能颠倒
- 即使某结点只有一个子树，也要区分左右子树
3. 优缺点
-
优点
- 它添加，删除元素都很快，并且在查找方面也有很多的算法优化
- 二叉树既有链表的好处，也有数组的好处，是两者的优化方案，在处理大批量的动态数据方面非常有用
-
缺点
- 缺点就是比数组和链表难学一些，当然，树比较难学是我的缺点，不是树的缺点
4.二叉树遍历
- 前序遍历，中序遍历，后序遍历中的序，指的是父节点的遍历顺序
- 层序遍历就是一层一层的遍历
堆
1. 介绍
- 堆中某个节点的值总是不大于或不小于其父节点的值
- 堆总是一棵完全二叉树
- 根节点的元素最大的堆叫做最大堆或大根堆
- 根节点的元素最小的堆叫做最小堆或小根堆
散列表
1. 介绍
- 散列表，也叫哈希表，是根据关键码和值 (key和value) 直接进行访问的数据结构
- 通过key和value来映射到集合中的一个位置，这样就可以很快找到集合中的对应元素
- 只能进行等值查询，和hash索引一样
2. 优缺点
-
优点
- 散列表的插入、删除、查找操作的时间复杂度可以做到常量级的O(1)，非常高效
- 可以按照索引遍历数组
-
缺点
- 散列表中的数据是无序存储的，如果要输出有序的数据，需要先进行排序
- 散列表扩容耗时很多，而且当遇到散列冲突时，性能不稳定，效率可能非常低
- 为了解决hash冲突，加大装载因子，就会浪费空间
图
1. 介绍
- 图真的就比较复杂了
- 图一般是多对多
- 带权图，可以用来计算路线最短距离
- 有向图可以存储好友关系，比如微信，你删了别人就看不到别人了，别人还能看到你
2. 存储方式
-
邻接矩阵
- 拥有n个顶点的图，就用一个n*n的矩阵存储
- 行就是出发顶点，列就是到达定点，如果是可达的记为1，不可达记为0
- 很明显，图比较大的时候，邻接矩阵就会有很多0，浪费空间
-
邻接表
- 类似与hashmap的数组链表
- 链表投是一个定点，后面存储的是可达的定点
- 邻接表避免了存储不可点的节点关系，节约空间
- 邻接表直观的记录了某节点可以到达哪些节点
- 但是要查找能到达某一点的其他点，就比较麻烦
-
逆邻接表
- 顾名思义，就是和邻接表相反的
- 逆邻接表记录了能到达某一点的所有节点
-
十字链表
- 把邻接表和逆邻接表的内容存在了一起