数据结构基本概念

什么是数据结构

数据结构是数据对象的集合，以及数据对象之间的关系和在数据上的操作。

分类

1. 线性结构：
   • 数组：具有固定大小的数据元素的集合，这些元素在存储中是连续的，并可以通过索引访问。
   • 链表：由节点组成，每个节点包含数据部分和指向下一个节点的指针。
   • 栈：后进先出 (LIFO) 的数据结构，只允许在顶部添加或删除元素。
   • 队列：先进先出 (FIFO) 的数据结构，允许在一端添加元素，并在另一端删除元素。
2. 非线性结构
   • 树：由节点组成的分层结构，其中有一个根节点，其他节点分为多个子树。
     • 二叉树：每个节点最多有两个子节点。
     • 平衡树、搜索树、红黑树 等是树的特殊类型。
   • 图：由节点（或称为顶点）和边组成的结构。
3. 散列结构：使用哈希函数将键转换为数组的索引，以便能够在常数时间内找到相关的值。

数据结构和算法

有效的算法通常依赖于选择合适的数据结构，而数据结构的实现和操作往往需要算法。

数据结构的选择直接影响到算法的性能。例如，数据的搜索在哈希表中可能是 O(1) 的复杂度，而在数组或链表中可能是 O(n) 的复杂度。