数据结构 (1)

数据结构 (1) - 简单数据

数组

数组：有序、内存连续的数据集，

数组是有序的，顺序就是插入的顺序，先插入的值排在前面，
内存连续：在内存分配时，数组中的值的内存空间是分配在一起的
所以在我们使用数组时，推荐在申明时申明数组的长度，不然在后续插入值时可能会导致之前的数据内存空间不够，需要重新分配整个数据内存空间

数组的索引就是数组中值的下标：从0开始计数。
数组的查找通过索引，所以快。
而增删、修改时，当插入一个值，则需要将后面的数据都后移，删除也是类似。

数组查询快，增删慢
查询：O(1)
增删：O(n)
修改：O(n)

数组查询原理

我们知道通过数组查询快，但是为何快呢。

因为数组是内存连续的，当我们通过下标查询时，
其实是通过数组0处内存地址+下标 得出该下标对应的内存地址，然后获取存储的对象。

所以查询会快。

链表

链表：无序、内存非连续、每个节点都具有下一个节点的地址

链表是无序的，内存非连续，因为每一个节点都含有下一个节点的地址，
相比于数组，内存非连续，则当数据增多，也不会存在内存空间的问题，因为只需随便分配下一个节点的内存，然后将上一个节点的中含有的下一个节点地址指向最新分配的地址即可。

链表数据第一个、最后一个节点的值是明确的。
因为链表是无序的。所以查询慢，因为想要获取一个节点的值，需要先获取上一个节点，通过上一个节点获取到下一个节点的地址。

查询：O(n)
增删：O(1)
修改：O(1)

链表分为：
单链表、双链表、循环链表

广义表

参考地址： https://blog.csdn.net/calculate23/article/details/108750041

hash表

参考地址： https://blog.csdn.net/xqs196301/article/details/123095920

栈

栈是一种只允许在一端进行插入或删除的线性表

栈的操作只有两种：出栈、进栈
特点：先进后出(FILO:first in last out)

只允许对栈顶的元素操作。
最先进入的元素将会被压入栈底

栈可以通过数组实现，也可以通过链表实现

堆

参考： https://blog.csdn.net/qq_51086532/article/details/120104501

集合

队列

FIFO

树

参考： https://baijiahao.baidu.com/s?id=1681663951861444437&wfr=spider&for=pc