常见的数据结构有哪些？它们的特点是什么？

常见的数据结构包括数组、链表、栈、队列、树、图、哈希表（散列表）和堆。这些结构根据其存储方式和操作规则被分为线性结构和非线性结构（如所示），它们在数据访问和修改方面各有特点，适用于不同应用场景。

1. 数组 (Array)
   • 特点：
     • 线性结构，通过连续的内存空间存储相同类型的数据元素。
     • 支持基于下标的快速随机访问（时间复杂度为 O(1)）和高效遍历操作。
     • 缺点包括固定大小、难以扩容，以及插入或删除元素时需移动其他元素（可能导致 O(n) 时间复杂度）。
   • 应用场景：适用于频繁查询但较少增删的场景（如集合遍历）。
2. 链表 (Linked List)
   • 特点：
     • 线性的、非连续存储结构，由节点组成，每个节点包含数据域和指针域。
     • 支持动态添加和删除节点（操作时间复杂度为 O(1)），内存利用灵活。
     • 缺点包括不支持高效随机访问（需遍历，O(n)），同时指针占用额外内存。
   • 类型分为单向、双向和循环链表；应用在数据量小且需频繁增删的场景（如实时队列管理）。
3. 栈 (Stack)
   • 特点：
     • 线性 LIFO（后进先出）结构，仅允许在栈顶执行操作（例如入栈 push 和出栈 pop）。
     • 优点为操作简单且高效（O(1)）；缺点是元素数量受限制。
   • 应用场景：递归算法实现（如斐波那契数列）、表达式求值。
4. 队列 (Queue)
   • 特点：
     • 线性的 FIFO（先进先出）结构，支持在队尾添加元素（入队 enqueue）和在队头移除元素（出队 dequeue）。
     • 操作高效（O(1)），但受限于队列大小设置。
   • 应用场景：事务处理日志或多线程任务调度（阻塞队列）。
5. 树 (Tree)
   • 特点：
     • 非线性层次结构，元素通过父子关系连接（常见二叉树）。
     • 优点包括高效的搜索和排序（平衡树时间复杂度为 O(log n)），缺点为实现复杂。
     • 变体如 B+ 树支持数据库索引，红黑树用于维护有序映射结构。
   • 应用场景：数据库索引、文件系统管理和层次数据存储。
6. 图 (Graph)
   • 特点：
     • 非线性的复杂结构，由节点和边表示关系，支持动态连接（如社交网络）。
     • 高效处理多对多关系，缺点为操作实现耗费内存和遍历耗时。
   • 应用场景：路径搜索算法（如地图导航）、依赖关系建模。
7. 哈希表 (Hash Table)
   • 特点：
     • 非线性结构，通过哈希函数映射键值对（支持高数据访问效率）。
     • 平均搜索、插入和删除时间复杂度为 O(1)，但当哈希冲突出现时效率下降。
   • 应用场景：缓存实现、快速查找表（如缓存数据库）。
8. 堆 (Heap)
   • 特点：
     • 特殊树形结构（常为完全二叉树），支持高效的优先队列操作（如 min-heap 或 max-heap）。
     • 插入和删除（调整堆）时间复杂度为 O(log n)，但排序依赖递归复杂度。
   • 应用场景：排序算法（堆排序）、优先队列管理（如调度任务）。

综合这些数据结构可知，它们在解决查询、增删等特定操作时提供了不同的优化方案（如数组适用查询而堆适用排序），选择需基于时间复杂度权衡空间利用（常见结构列表参考）。