常用的数据结构基础（结合java）

淡淡的烟草味﹌ 2023-02-26 10:26 25阅读 0赞

### 常用的数据结构基础（结合java） ###

*  数组
 *  链表
 *  数组和链表区别
 *  栈
 *  队列
 *  散列表
 *  散列表扩容
 *   *  为什么需要扩容
     *  扩容的判断标准
 *  树
 *  二叉树
 *  二叉堆

**看了小灰的漫画算法中数据结构相关部分后，整理记录一些内容用于之后学习**

# 数组 #

*  数组的英文名是array，是有限个相同类型的变量所组成的**有序集合**，数组中的每一个变量被称为元素。
 *  索引范围为 0 到 数组长度-1
 *  读取，更新元素时根据下标操作元素，这种读取方式叫做**随机读取**。**时间复杂度为O(1)**。
 *  插入元素分为**尾部插入**，**中间插入**(插入位置及之后的元素向后移动)，**超范围插入**(需要扩容，创建一个原数组两倍长度的数组，复制原数组再添加)。**时间复杂度为O(n)**

# 链表 #

*  链表是一种物理上**非连续，非顺序**的数据结构，由若干\*\*节点(node)\*\*所组成。
 *  **单向链表**的每一个节点包含两部分，一部分是存放数据的变量**date**，另一部分是指向下一个节点的**next**。
 *  **双向链表**的每一个节点包含三部分，除了date和next指针，还包含**prev**指针。
 *  链表的第一个节点被称为头节点，最后一个节点被称为尾节点，尾节点的next指针指向空，同理双向链表头节点prev指针指向空。
 *  链表中查找某个节点需要从头节点开始向后一个一个查找。**时间复杂度为O(n)**
 *  更新，插入，删除不考虑查找情况下，直接处理旧数据即可。**时间复杂度为O(1)**

# 数组和链表区别 #

1.  数组在内存中占用了连续完整的存储空间，链表则采用见缝插针
2.  链表不存在扩容问题
3.  数组适用于读操作多的情况，链表适用于写操作多的情况

# 栈 #

*  java中Stack类，Stack一一Vector-------AbstractList-------List一一Collection
 *  栈是一种线性逻辑结构，可以用数组实现，也可以用链表实现。
 *  栈中的元素只能先入后出
 *  基本操作有入栈push，出栈pop。**时间复杂度为O(1)**
 *  绝大多数递归问题都可以使用栈来解决。因为递归和栈都有回溯的特性。

# 队列 #

*  java中Queue接口，Queue一一Collection
 *  队列是一种线性逻辑结构，可以用数组实现，也可以用链表实现。
 *  队列中的元素只能先入先出
 *  基本操作有入队，出队。**时间复杂度为O(1)**

# 散列表 #

*  散列表也叫做**哈希表**，这种数据结构提供了键和值的的映射关系。
 *  散列表主要基于数组实现，所以只要给出一个Key，就可以高效查找到它所匹配的Value，**时间复杂度接近于O(1)**。
 *  通过**哈希函数**将key和数组下标进行转换。
 *  JDK中哈希函数没有采用一般的取模运算，而是采用了位运算来进行优化。
 *  当发生哈希冲突时，Java集合类中HashMap采用链表法解决hash冲突。当新来的Entry映射到与之冲突的数组位置时，只需要插入到对应的链表中即可（jdk1.8加入了红黑树进行优化）。

# 散列表扩容 #

## 为什么需要扩容 ##

散列表达到一定饱和度，Key映射位置发生冲突的概率会逐渐提高。这样一来会形成很长的链表，对后续的插入和查询操作的性能都有很大的影响。

## 扩容的判断标准 ##

1.  Capacity (HashMap当前长度)
2.  LoadFactor (负载因子，默认值0.75)

当 HashMap.Size >= Capacity \* LoadFactor 时，就是HashMap中现有元素个数大于 HashMap长度 \* 0.75时扩容

# 树 #

*  树是n(n>=0)个节点的有限集。
 *  当n=0时为空树。
 *  对于非空树有两个特点

1.  有且仅有一个特定的成为根节点
2.  当n>1时，其余节点可分为m个互不相交的有限集，每一个集合本身又是一个数，并被称为根的子树

# 二叉树 #

每个节点最多有两个孩子节点，孩子节点分为左节点和右节点，不可以混淆。

两种特殊的二叉树：