数据结构概念

一、介绍

数据结构是计算机科学中的一个核心概念，它涉及到如何在计算机中有效地组织、存储和管理数据，以支持各种算法和应用程序的高效运行。

数据结构不仅是数据元素（如整数、字符串、对象等）的集合，更关键的是这些数据元素之间的关系以及对这些关系的操作。

二、常见类型

2.1 数组

• 定义
  • 数组是相同类型数据元素的有序集合，这些元素在内存中以连续的方式存储。
• 优点
  • 随机访问：通过索引（下标）可以在常数时间内直接访问任何位置的元素。
  • 空间利用率高：如果已知数据规模，可以预先分配固定大小的内存空间，减少碎片。
• 缺点
  • 大小固定：一旦创建，容量难以动态调整，若需扩容通常需要创建新的数组并复制所有元素。
  • 插入/删除复杂度高：在非末尾位置插入或删除元素时，可能需要移动大量后续元素以保持连续性。

2.2 链表

• 定义
  • 链表由一系列节点组成，每个节点包含数据和指向下一个节点的指针。根据指针方向和循环特性，可分为单链表、双链表和循环链表。
• 优点
  • 项目动态扩展：无需预先分配固定大小的内存，可以根据需要轻松添加或删除节点。
  • 插入/删除高效：在指定位置插入或删除元素仅需调整相邻节点的指针，时间复杂度为O(1)（平均情况下，对于双链表而言）。
• 缺点
  • 随机访问困难：访问任意元素需从头节点开始逐个遍历，时间复杂度为O(n)。
  • 额外空间开销：每个节点需存储指向下一个节点的指针，导致存储空间略大于实际数据。

2.3 栈

• 定义
  • 栈是一种遵循后进先出（LIFO）原则的线性数据结构，仅允许在一端（通常称为栈顶）进行插入（入栈，push）和删除（出栈，pop）操作。
• 优点
  • 操作简单：入栈和出栈操作时间复杂度均为O(1)，实现容易。
  • 应用广泛：适用于撤销/重做操作、表达式求值、函数调用等需要“后进先出”特性的场景。
• 缺点
  • 受限的访问模式：只能访问栈顶元素，对其他元素无直接访问权限。
  • 可能导致溢出：如果不合理控制栈的大小，持续入栈可能导致内存空间耗尽。

2.4 队列

• 定义
  • 队列是一种遵循先进先出（FIFO）原则的线性数据结构，允许在一端（队尾）插入元素（入队，enqueue），在另一端（队头）删除元素（出队，dequeue）。
• 优点
  • 操作简单：入队和出队操作时间复杂度通常为O(1)，实现容易。
  • 公平调度：适用于任务调度、消息传递、缓冲区管理等需要“先进先出”公平处理的场景。
• 缺点
  • 受限的访问模式：只能从队头删除和从队尾添加元素，对中间元素无直接访问权限。
  • 可能导致溢出或阻塞：如果不合理控制队列大小或处理速度不均，可能导致内存空间耗尽或等待时间过长。

2.5 树

• 定义
  • 树是一种非线性数据结构，由n（n≥1）个有限节点构成一个具有层次关系的集合。每个节点有零个或多个子节点，除根节点外，每个节点有且仅有一个父节点。
• 优点
  • 递归结构：便于进行递归算法设计。
  • 灵活查询：适用于表示层次关系、查找、排序（如二叉搜索树）等场景。
• 缺点
  • 操作复杂度各异：不同类型的树（如二叉树、平衡树、红黑树等）其插入、删除、查找等操作的时间复杂度不同，需要根据应用场景选择合适的树结构。
  • 空间消耗大：相比于线性数据结构，树结构通常占用更多内存。

2.6 图

• 定义
  • 图由顶点（Vertex）集合和边（Edge）集合组成，顶点间通过边连接，可以是有向的（箭头指向一个方向）或无向的（没有方向）。边可以有权重（Weight）。
• 优点
  • 灵活表示复杂关系：适用于建模多对多关系、网络结构（如社交网络、交通网络等）、最短路径问题等。
• 缺点
  • 操作复杂：图的遍历、搜索、最短路径计算等操作相对复杂，时间复杂度较高。
  • 空间消耗大：存储图结构通常需要邻接矩阵或邻接表，空间需求取决于顶点数和边数。

2.7 堆

• 定义
  • 堆是一种特殊的树形数据结构，通常是一个完全二叉树，满足堆序性质（即父节点的关键字值大于或小于其子节点的关键字值，形成最大堆或最小堆）。
• 优点
  • 高效实现优先队列：插入、删除最大（最小）元素时间复杂度为O(log n)。
  • 常用于排序：例如，堆排序算法基于堆结构实现。
• 缺点
  • 操作相对复杂：维护堆序性质需要特定的调整算法（如上浮、下沉）。
  • 用途相对专门：主要用于优先队列和特定排序场景，不如数组、链表等通用。

2.8 散列表

• 定义
  • 散列表（哈希表）通过哈希函数将键（Key）映射到数组的某个位置（索引），实现快速查找、插入和删除操作。
• 优点
  • 常数时间复杂度：理想情况下，查找、插入、删除等操作的时间复杂度为O(1)。
  • 无需有序：无需对数据进行排序即可快速访问。
• 缺点
  • 哈希冲突：不同的键可能映射到同一位置，需要解决冲突（如开放寻址法、链地址法）。
  • 空间效率依赖负载因子：负载因子过高会导致冲突增多，影响性能；过低则浪费空间。