数据结构

数据结构是计算机存储、组织数据的方式，是指相互之间存在一种或多种特定关系的数据元素的集合。

数据是存储在计算机的内存里的，在存储时，决定了数据顺序和位置关系的便是“数据结构”，分为逻辑结构和物理结构。

数据结构往往同高效的检索算法和索引技术有关，通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。

逻辑结构

指数据元素之间逻辑关系的数据结构，这里的逻辑关系是指数据元素之间的前后间关系。一种数据结构的逻辑结构根据需要可以表示成多种存储结构。

• 线性结构：数据结构的元素之间存在一对一线性关系，所有结点都最多只有一个直接前趋结点和一个直接后继结点。常见的有数组、队列、链表、栈。
• 非线性结构：各个结点之间具有多个对应关系，一个结点可能有多个直接前趋结点和多个直接后继结点。常见的有多维数组、广义表、树结构和图结构等。

物理结构

指数据的逻辑结构在计算机存储空间中的存放形式称为数据的物理结构，也叫做存储结构。

• 顺序存储：存储顺序是连续的，在内存中用一组地址连续的存储单元依次存储线性表的各个数据元素。
• 链式存储：在内存中的存储元素不一定是连续的，用任意地址的存储单元存储元素，元素节点存放数据元素以及通过指针指向相邻元素的地址信息。
• 索引存储：除建立存储结点信息外，还建立附加的索引表来标识节点的地址。索引表由若干索引项组成。
• 散列存储：又称Hash存储，由节点的关键码值决定节点的存储地址。

存储方式

1. 数组（顺序存储）：紧凑连续存储,可以随机访问，通过索引快速找到对应元素，而且相对节约存储空间。但正因为连续存储，内存空间必须一次性分配够，所以说数组如果要扩容，需要重新分配一块更大的空间，再把数据全部复制过去，时间复杂度 O(N)；而且你如果想在数组中间进行插入和删除，每次必须搬移后面的所有数据以保持连续，时间复杂度 O(N)。
2. 链表（链式存储）：因为元素不连续，而是靠指针指向下一个元素的位置，所以不存在数组的扩容问题；如果知道某一元素的前驱和后驱，操作指针即可删除该元素或者插入新元素，时间复杂度 O(1)。但是正因为存储空间不连续，你无法根据一个索引算出对应元素的地址，所以不能随机访问；而且由于每个元素必须存储指向前后元素位置的指针，会消耗相对更多的储存空

如：Redis 提供列表、字符串、集合等等几种常用数据结构，但是对于每种数据结构，底层的存储方式都至少有两种，以便于根据存储数据的实际情况使用合适的存储方式。

常用的数据结构

名称	英文	结构	说明
数组	Array	顺序	线性表数据结构，用一组连续的内存空间来存储一组相同类型的数据
链表	Linked List	链式	物理存储单元上非连续，非顺序的存储结构。链表有一系列节点(元素)组成。每个节点包含两个数据，一个是存储元素的数据域（值），另一个是存储下一个节点地址的指针域(还可以增加一个数据存储上一个节点地址的指针域)
队列	Queue	顺序	线性排列的数据结构，FIFO(First in First Out)，操作数据从两端进行

• 栈(Stack): 线性排列的数据结构，LIFO(Last in First Out)，操作数据从顶端进行
• 散列表(Hash): 又称哈希表。存储的由键(key)和值(value)组成的数据，根据键直接访问存储在内存存储位置
• 树(Tree): 层级式的数据结构，由顶点(节点)和连接它们的边组成，非根节点有且只有一个父节点
• 堆(Heap): 完全二叉树(除了最后一层其他层的节点个数都是满的)。
• 图(Graph): 相对复杂的一种数据结构，由顶点(结点，Vertex)和连接每对顶点的边(Edge)所构成的图形