02 数据结构原理

不念不忘少年蓝@ 2023-06-15 10:00 17阅读 0赞

# 02 数据结构原理 #

## 数组 ##

数组是最常用的数据结构，创建数组必须在内存中找出一段连续的内存空间，并且是相同数据类型。

比如我们创建一个长度为10的数组，数据类型为整型的数组，在内存中地址为0x1000开始。

![如下图][format_png]

数组是连续的存储空间，所以我们可以通过数组下表找到对应的元素，可以对元素进行读写操作。

想要查找数组某个元素，我们需要挨个遍历数组，因此数组的时间复杂度为O（1）

## 链表 ##

链表和数组一样都是线性表，唯一不同于数组的是链表不需要一段连续的存储空间，链表可以使用零散的存储空间，内存不比是连续的。

链表中元素之间通过指针指向前后的元素，指向前一个和后一个元素，如下图所示。

![链表][format_png 1]

链表不是连续的存储的，查找元素只能和数组一样遍历，因此时间复杂度也是O（1）

链表不是连续的，所以插入和删除，仅仅只需将元素前后的指针指向删除元素的前后指向，或者新增的元素即可。

![如下图][format_png 2]

## Hash 表 ##

数组通过下标查询元素，数组中找到这个数据，还是需要遍历数组，时间复杂度为O（1）

Hash 表的物理存储其实是一个数组，不过Hash表是以key-value形式存储数据，Value 写入 Hash 表，可以通过key查询到对应的value ，存储的时候通过key计算出下标，然后存储在数组中。

数组下标是通过Hash表的数组长度对HashCode求余，余数就是Hash表数组的额下标，通过这个下标就可以直接访问到Hash表中存储的key,value 。

![如下图][format_png 3]

读取数据时候，通过key 先求去它的HashCode 然后对8取模，得到余数，通过这个余数去数组中查找元素。

但是还有种情况，比如109 和 101 对8 取模都是5 但是数组中只能存取一个元素，那多个元素如何存储呢，这种情况被称作 “hash冲突”，解决 Hash 冲突常用的方法是链表法。

相同的下标再去链表中查询下标相同的元素，如下图。

![hash冲突][hash]

因为有 Hash 冲突的存在，所以“Hash 表的时间复杂度为什么是 O(1)？”这句话并不严谨，极端情况下，如果所有 Key 的数组下标都冲突，那么 Hash 表就退化为一条链表，查询的时间复杂度是 O(N)。但是作为一个面试题，“Hash 表的时间复杂度为什么是 O(1)”是没有问题的。

## 栈 ##

栈是在线性表的基础上增加了限制条件：后面添加的数据，必须先删除，先进栈的数据后出，后进的数据先出！ 例如：往桶里放入东西，先放进去的东西，在最底部，后放进的东西在最上面、或者 手枪弹匣，子弹往里面压，先压进去的后出来。

如下图  
![栈][format_png 4]

由于栈进出数据的遵循先进后出（或者后进先出）的特点，栈不需要在中间进行一些删除，增加操作。

## 队列 ##

队列也是一种操作受限制的线性表，跟栈不同的是 栈属于先进后出，而队列是先进先出。

![队列][format_png 5]

通常我们在写多读少的情况下会用到队列，这样子可以减少系统并发压力。

我们常用的tomcat 处理请求线程池也是这样，如果线程池线程数量用完了，请求会放入队列中等待执行。

## 树 ##

数组，队列，栈，链表都属于线性表。

线性表的基本概念
    对于同一个线性表，其每一个数据元素的值虽然不同，但必须具有相同的数据类型；
    数据元素之间具有一种线性的或“一对一”的逻辑关系。
    第一个数据元素没有前驱，这个数据元素被称为开始节点；
    最后一个数据元素没有后继，这个数据元素被称为终端节点；
    除了第一个和最后一个数据元素外，其他数据元素有且仅有一个前驱和一个后继。

而树属于非线性表,如下图

![format_png 6][]

例如我们一些部门图，组织架构等都是这种数据结构类型。

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9zdGF0aWMwMDEuZ2Vla2Jhbmcub3JnL3Jlc291cmNlL2ltYWdlLzAxLzI2LzAxODdiMWEwZDJkMjY0MjY0MTVhZTRmNmQwMzE4MzI2LnBuZw?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9zdGF0aWMwMDEuZ2Vla2Jhbmcub3JnL3Jlc291cmNlL2ltYWdlLzJmL2U2LzJmODVmNWYzMWI1OTg1YzQ2YjAyOTE5YWE0ODA5ZmU2LnBuZw?x-oss-process=image/format,png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9zdGF0aWMwMDEuZ2Vla2Jhbmcub3JnL3Jlc291cmNlL2ltYWdlLzA0LzAxLzA0NjBhNWZjMTJkN2Q1MjI3ZjQzNmE2MDg2ODRlYTAxLnBuZw?x-oss-process=image/format,png
[format_png 3]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9zdGF0aWMwMDEuZ2Vla2Jhbmcub3JnL3Jlc291cmNlL2ltYWdlL2UyL2NiL2UyZDMxOTFiMDg3ZDkwMjk4MDU5NWFlYjFiZTc5ZGNiLnBuZw?x-oss-process=image/format,png
[hash]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9zdGF0aWMwMDEuZ2Vla2Jhbmcub3JnL3Jlc291cmNlL2ltYWdlL2VhLzlhL2VhODliZWMzODVlYmZlNWMwM2IzMDZkZWVhZDAzYzlhLnBuZw?x-oss-process=image/format,png
[format_png 4]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9zdGF0aWMwMDEuZ2Vla2Jhbmcub3JnL3Jlc291cmNlL2ltYWdlLzg1LzgxLzg1NzUyYWRjMWZjMjY0NTNlMjIzNmYwYThiMDFjMDgxLnBuZw?x-oss-process=image/format,png
[format_png 5]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9zdGF0aWMwMDEuZ2Vla2Jhbmcub3JnL3Jlc291cmNlL2ltYWdlL2EzL2E1L2EzOTZhYjUwMzEyYjVmYWEyOWM3YjkzZjZhZDRiN2E1LnBuZw?x-oss-process=image/format,png
[format_png 6]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9zdGF0aWMwMDEuZ2Vla2Jhbmcub3JnL3Jlc291cmNlL2ltYWdlLzg4L2NkLzg4OTA2YWQ0NTUwNGFlM2QxOTVkYWRjOWI3YTQ1NWNkLnBuZw?x-oss-process=image/format,png