数据结构学习笔记

1. 数组 (Array)

定义

数组是一种线性数据结构，用于存储固定大小的相同类型元素集合。每个元素都有一个索引，用于快速访问。

特点

• 优点：访问速度快，通过索引直接访问O(1)时间复杂度。
• 缺点：大小固定，插入和删除元素效率低（需移动后续元素）。插入元素的时间复杂度为O(n)，删除元素的时间复杂度同样为O(n)。

应用场景

适合于元素数量固定且频繁查询的场景，如排序数组、查找表等。多维数组常用于表示矩阵、图像、游戏地图等需要多个维度来描述的数据结构。

2. 链表 (Linked List)

定义

链表是一种由节点组成的数据结构，每个节点包含存储数据的部分以及指向下一个节点的指针。通过节点之间的指针连接，形成了链表的结构。链表可以分为单链表、双向链表和循环链表等不同类型，它们各自具有特定的特点和应用场景。

• 数据元素：节点存储的实际数据。数据可以是任意类型，例如整数、字符、字符串、对象等。
• 指针（或引用）：指向下一个节点的指针。它存储了下一个节点在内存中的地址，通过这个指针可以找到链表的下一个节点。
• 

类型

单向链表

• 单链表是最简单的链表类型，每个节点包含一个数据元素和一个指向下一个节点的指针。单链表的尾节点指针为空，表示链表的结束。单链表的插入、删除操作相对简单高效，但随机访问的效率较低。

单向链表的特点

• 非连续存储：单链表中的节点在内存中可以是任意位置，不要求连续存储。每个节点通过指针指向下一个节点，从而将它们连在一起。
• 动态性：相较于数组，单链表的长度可以动态地增减，不需要预先分配内存空间。这使得单链表在需要频繁插入和删除节点的场景中更加灵活。
• 搜索效率相对较低：由于单链表的节点只能通过指针一个一个地遍历，因此搜索某个特定的节点需要遍历整个链表，时间复杂度为O(n)，其中n是链表的长度。相比之下，数组可以使用索引直接访问元素，搜索效率更高。
• 内存空间的额外开销：单链表中的每个节点除了存储数据外，还需要存储下一个节点的指针，这导致了额外的内存开销。
• 插入和删除效率较高：相对于数组，单链表在插入和删除节点时效率较高。插入一个节点只需要改变相邻节点的指针，而删除一个节点只需要改变前一个节点的指针指向下一个节点，不需要移动其他元素。
• 灵活性：单链表可以方便地进行节点的插入和删除操作，可以根据实际需要进行自由调整。

双向链表

• 每个节点包含数据、指向前一个节点和指向下一个节点的指针。
• 

双向链表的特点

• 支持双向遍历：相对于单向链表，双向链表支持双向遍历，可以从前往后、从后往前遍历链表。
• 插入、删除节点效率更高：相较于单向链表，双向链表在插入和删除某个节点时，只需要改变相邻两个节点的指向，效率更高，尤其是在删除链表中某个元素时更加便捷。
• 需要更多的内存空间：相比单向链表，双向链表需要更多的内存空间来存储额外的指针，增加了额外的空间开销。
• 内存存储不连续：相对于数组，链表中节点的内存存储位置不连续，需要使用指针进行串联，这可以更加灵活地进行插入、删除和移动节点的操作。
• 操作复杂度较高：插入、删除、移动等操作，需要修改前后节点的指针信息，操作比较繁琐。

循环链表

• 链表的最后一个节点指向链表的第一个节点，形成闭环。
• 

循环链表特点

• 首位相连：循环链表的最后一个节点指向链表的第一个节点，使得链表成为一个环形结构。这样，链表的结束节点与开始节点相连，可以实现无限循环，更加灵活和方便。
• 操作始终成立：由于循环链表始终是一个环形的结构，因此操作（例如插入、删除、查找等）始终处于链表中，这也保证了操作始终能够完成。
• 遍历循环：与单向链表相比，在遍历时需要注意指针不要陷入死循环。否则会导致遍历永远无法结束。
• 内存空间的额外开销：与单向链表相比，循环链表需要多一个指向头部节点的指针，增加了额外的空间开销。
• 插入和删除效率较高：相对于数组，循环链表在插入和删除节点时效率比较高。插入一个节点时只需要修改相邻节点的指针即可，而删除一个节点时只需要改变前一个节点的指针指向下一个节点即可。

优缺点

• 优点：动态分配内存，插入和删除操作快（O(1)，只需改变指针）。
• 缺点：访问速度慢，需从头节点遍历（最坏情况下O(n)）。

应用场景

适用于频繁插入和删除操作的场景，如实现堆栈、队列等。

3. 栈 (Stack)

定义

栈是一种特殊的线性结构，遵循后进先出（LIFO, Last In First Out）原则。只允许在一端（栈顶）进行插入和删除操作。

操作

• 压栈（Push）：在栈顶添加元素。
• 弹栈（Pop）：移除栈顶元素。
• 栈的插入和删除操作只能在栈顶进行，因此栈是一个只能从一端访问的数据结构。

应用场景

回溯算法、函数调用栈、括号匹配等。

4. 队列 (Queue)

定义

队列是一种线性结构，遵循先进先出（FIFO, First In First Out）原则。一端添加元素（队尾），另一端移除元素（队头）。

操作

• 入队（Enqueue）：在队尾添加元素。
• 出队（Dequeue）：从队头移除元素。

应用场景

任务调度、缓冲区管理等。

栈和队列的对比：

结构：栈和队列都是线性结构，但栈只有一个入口（栈顶）和一个出口（栈顶），而队列有一个入口（队尾）和一个出口（队头）。
插入和删除操作：栈的插入和删除操作只能在栈顶进行，而队列的插入操作在队尾进行，删除操作在队头进行。
访问顺序：栈按照后进先出的顺序访问元素，而队列按照先进先出的顺序访问元素。
应用场景：栈常用于函数调用、表达式求值、回溯算法等场景，而队列常用于任务调度、消息传递、缓冲区管理等场景。

5. 哈希表 (Hash Table)

定义

哈希表是一种通过哈希函数将键（Key）直接映射到值（Value）的数据结构，提供了快速的查找、插入和删除操作。

哈希表的实现就是映射函数构造，哈希表的映射函数构造方法也有很多，常见的有：直接定址法、 除留余数法、 乘余取整法、 数字分析法、 平方取中法、 折叠法、 随机数法等。

特点

• 优点：平均时间复杂度为O(1)。
• 缺点：可能遇到哈希冲突，需要解决冲突策略（如开放寻址法、链地址法）。

应用场景

字典、缓存、数据库索引等。

6. 树 (Tree)

定义

树是一种分层的非线性数据结构，由节点（Node）和边（Edge）组成，每个节点有零个或多个子节点，且只有一个根节点。

• 树是由一个或多个节点（或称为顶点）的有限集合构成。
• 在任何非空树中，存在唯一一个称为根（Root）的节点，没有父节点。
• 除根节点外的每个节点都有一个父节点。
• 每个节点可以有零个或多个子节点（子树）。
• 树中的节点形成一种层次关系，没有环路（即节点之间不存在重复路径）。
• 子树之间相互独立，即任意两个子树的节点集合不会相交。

基本术语

• 节点（Node）：树中的基本单位，存储数据元素。
• 边（Edge）：连接树中节点的链接，表示父子关系。
• 根节点（Root Node）：没有父节点的节点。
• 叶节点（Leaf Node）：没有子节点的节点。
• 子节点（Child Node）：某个节点的直接下一级节点。
• 父节点（Parent Node）：直接位于某节点之上的节点。
• 兄弟节点（Sibling Node）：具有相同父节点的节点。
• 度（Degree）：节点的子节点数目。
• 层次（Level）：从根开始到某个节点的距离，根节点处于第0层。
• 高度（Height）：树中节点的最大层次数。

操作

• 创建树：初始化一个空树或构造指定结构的树。
• 插入节点：在树的指定位置添加新节点。
• 删除节点：移除树中的某个节点并保持树的特性。
• 查找节点：在树中搜索特定值的节点。
• 遍历树：按照某种顺序访问树中的所有节点，常见的遍历方法有前序遍历、中序遍历、后序遍历和层序遍历。

特殊类型的树

• 二叉树：每个节点最多有两个子节点的树。
• 二叉搜索树（BST）：二叉树的一种，左子树所有节点的值小于其父节点，右子树所有节点的值大于其父节点。
• 平衡二叉树（如AVL树、红黑树）：自平衡的二叉搜索树，确保树的高度大致保持对数级别。
• B树、B+树：适用于文件系统和数据库索引的自平衡树。
• 堆：一种完全二叉树，常用于优先队列实现。

应用场景

• 文件系统、数据库索引、表达式解析等。

7. 图 (Graph)

定义

图是由顶点（Vertex）和边（Edge）组成的非线性数据结构，边可以连接任意两个顶点，形成更复杂的关系网络。

类型

• 有向图 / 无向图
• 加权图 / 非加权图

应用场景

社交网络、地图导航、网络路由等。