数据结构

数据结构概述:

数据结构是计算机存储、组织数据的方式。
是指相互之间存在一种或多种特定关系的数据元素的集合
通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率

1. 常见数据结构之栈

栈分栈顶(一端开口)和栈底(一端封闭)
栈是一种数据先进后出的模型

数据进入栈模型的过程称为：压/进栈
数据在栈顶被称为栈顶元素，在栈底是栈底元素
数据进栈的顺序是从栈底元素到栈顶元素 A-> B-> C-> D
image.png
数据离开栈模型的过程称为：弹/出栈
数据出栈的顺序是从栈顶元素到栈底元素 D-> C-> B-> A
image.png

2. 常见数据结构之队列

image.png
队列一端开头是前端，一端开口是后端
数据从后端进入队列模型的过程称为: 入队列
数据从前端离开队列模型的过程称为: 出队列
image.png
队列是一种数据先进先出的模型

总结:栈和队列区别

栈分栈顶(一端开口)和栈底(一端封闭)，栈是一种数据先进后出的模型—> 放盘子
队列一端开头是前端，一端开口是后端， 队列是一种数据先进先出的模型 —> 排队买票

3. 常见数据结构之数组

image.png
查询数据通过索引定位，查询任意数据耗时相同，查询速度快
删除数据时，要将原始数据删除，同时后面每个数据前移，删除效率低
添加数据时，添加位置后的要将每个数据后移，再添加元素，添加效率极低

4. 常见数据结构之链表

链表中元素（结点）存储位置（地址）
链表中的元素被称为结点—> 结点中包含存储的数据以及 下一个结点的地址
image.png
每一个链表都有一个 头结点 : head 空地址: ^(表示结束)
image.png
链表存储以及添加方式
image.png
链表存储以及删除方式
image.png
链表存储以及查询方式
如果向查询数据D是否存在，必须从头结点（head）开始查询，无论查询那个数据都是从head开始查询

总结：列表和数组的区别

链表是一种增删比较快的模型（相对于数组而言）
链表是一种查询比较慢的模型（相对于数组而言）

5. 常见数据结构之哈希表

哈希表
在JDK8之前,底层采用数组+链表实现, 可以说是一个元素为链表的数组
在JDK8以后, 在长度比较长度时候, 底层实现了优化
哈希表存储方式 : 首先通过hashCode()计算每个元素的哈希值
哈希表是个数组, HashSet默认的长度是16, 索引的值就是 (0 - 15)
如何将元素存入哈希表中, 将元素的哈希值对16取余 ,得出来的值就是该元素的位置
例如: “hello”.hashCode() = 99162322 % 16 = 2
“world”.hashCode()= 113318802 % 16 = 2
“java”.hashCode() = 3254818 % 16 = 2
“world”.hashCode()= 113318802 % 16 = 2
“通话”.hashCode() = 1179395 % 16 = 3
“重地”.hashCode() = 1179395 % 16 = 3

哈希表存储过程: 如果位置相同, 先比较哈希值 ,不同则以链表形式存储在相同位置, 如果地址相同, 哈希值相同, 同时内容也相同 判断该元素是重复元素则不存储
image.png
但是当哈希表中出现如果地址相同, 哈希值相同, 但是内容不同时 ,该元素同样以链表形式存储在哈希表中
image.png