概述

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

逻辑结构

集合：数据结构中的元素之间除了“同属一个集合”的相互关系外，无其他关系；
线性结构：数据结构中的元素存在一对一的相互关系；
树形结构：数据结构中的元素存在一对多的相互关系；
图形结构：数据结构中的元素存在多对多的相互关系；

物理结构（存储结构）

顺序存储：连续的内存空间
链式存储：不连续的内存空间
索引存储：为了方便查找，整体无序，但索引块之间有序，需要额外的存储空降，存储索引表
哈希存储（散列存储）：选取某个函数，数据元素根据函数计算存储位置，可能存在多个数据元素存储在同一位置，引起地址冲突（哈希碰撞）

8种常用数据结构

数组（Array）

【应用场景】：存储固定大小的元素集合；快速随机访问元素；
【优点】：快速访问、内存连续
【缺点】：大小固定，无法动态扩展，不适合频繁的插入和删除操作

栈（stack）

【应用场景】：后进先出（LIFO）的数据处理场景，求表达式、浏览器后退功能等
【优点】：实现简单，易于理解
【缺点】：功能有限，通常需要封装链表或数组来实现

队列（Queue）

【应用场景】：先进先出（FIFO）的数据处理场景，任务调度、消息传递等
【优点】：实现简单，易于理解
【缺点】：通常需要封装链表或数组来实现

链表（Linked List）

【应用场景】：存储元素集合，尤其是需要频繁插入和删除操作；实现栈和队列
【优点】：动态大小、插入和删除操作效率高
【缺点】：访问元素效率较低，需要遍历链表

树（Tree）

【应用场景】：
1. 需要高效的插入、删除、查找数据，如文件系统、路由算法
2. 实现二叉搜索树（Binary Search Tree）、AVL树、红黑树等
【优点】：可以提供高效的插入、删除、搜索操作
【缺点】：实现复杂，需要平衡或自平衡来避免性能下降

图（Graph）

【应用场景】：表示实体之间的关系，如社交网络、地图导航等；实现图的遍历算法如DFS和BFS。
【优点】：能够表示复杂的关系
【缺点】：实现和维护复杂，特别是在大型图中

堆（Heap）

【应用场景】：实现优先队列，如任务调度、堆排序等；实现最小堆或最大堆
【优点】：可以高效地获取最大或最小元素
【缺点】：不支持快速查找操作，只能通过堆化过程来调整结构

散列表（Hash）

【应用场景】：需要快速查找、插入和删除键值对；实现关联数组或字典
【优点】：查找效率高（平均情况下O(1)时间复杂度）
【缺点】：不保证元素的顺序，扩容时可能影响性能