链表（Linked List）:
单向链表（Singly Linked List）
单向链表是最简单的链表形式，每个节点只包含指向下一个节点的指针。它的特点是插入和删除节点的操作效率高，但访问节点的效率较低。
(插入和删除节点的时间复杂度为O(1)，但查找节点的时间复杂度为O(n)。)
单向链表基本操作
-
创建链表：初始化一个空链表。
-
插入节点：在链表的任意位置插入一个新节点。
-
删除节点：从链表中删除指定节点。
-
遍历链表：按顺序访问链表中的每个节点。
双向链表（Doubly Linked List）
双向链表在单向链表的基础上，每个节点除了包含指向下一个节点的指针外，还包含指向上一个节点的指针。它的特点是插入、删除和访问节点的操作效率都较高。
(插入和删除节点的时间复杂度为O(1)，但查找节点的时间复杂度为O(n))
双向链表基本操作
-
创建链表：初始化一个空链表。
-
插入节点：在链表的任意位置插入一个新节点。
-
删除节点：从链表中删除指定节点。
-
遍历链表：按顺序访问链表中的每个节点。
循环链表（Circular Linked List）
最后一个节点的指针指向第一个节点，形成一个循环。 遍历链表需要定义一个结束条件，以避免无限循环。
(插入和删除节点的时间复杂度为O(1)，但查找节点的时间复杂度为O(n)。)
循环链表基本操作：
-
创建链表：初始化一个空链表。
-
插入节点：在链表的任意位置插入一个新节点。
-
删除节点：从链表中删除指定节点。
-
遍历链表：按顺序访问链表中的每个节点。
数据结构与STL库（Data Structures ）:
栈和队列(Stack and Queue)
栈和队列是两种常见的数据结构，它们都用于存储和操作数据，但在数据的访问和删除方式上有所不同。
栈(Stack):
栈是一种后进先出的数据结构，类似于一摞盘子。只能在栈的顶部进行插入和删除操作，最后插入的元素最先被删除，而最先插入的元素则在栈中保持不变，直到其他元素被删除。栈的基本操作包括入栈（Push）和出栈（Pop）。
队列(Queue):
队列是一种先进先出的数据结构，类似于排队等待的人群。数据可以从队列的一端插入（入队，Enqueue），从另一端删除（出队，Dequeue），即最先插入的元素最先被删除，而最后插入的元素则在队列中保持不变，直到其他元素被删除。队列的基本操作包括入队和出队，以及获取队列长度和判断队列是否为空。
关于(About):
栈和队列在实际应用中有各自的特点和用途： - 栈常用于递归调用、表达式求值、括号匹配、深度优先搜索等场景，其特点是后进先出，可以用于实现回退操作或者撤销操作。 - 队列常用于广度优先搜索、任务调度、消息传递等场景，其特点是先进先出，保证了按照顺序处理数据。
动态数组（Dynamic Array）
动态数组是一种可以自动调整大小的数组数据结构。它具有数组的特性，可以通过索引访问和修改元素，但与静态数组不同的是，动态数组的大小可以根据需要进行动态调整。
动态数组的主要特点包括：
-
动态调整大小：动态数组可以根据需要自动增加或减少其大小，以容纳更多或更少的元素。这使得动态数组在需要频繁插入或删除元素的情况下非常有用。 - 随机访问：与静态数组类似，动态数组可以通过索引直接访问和修改元素。这使得在任意位置插入、删除或修改元素成为可能。
-
连续存储：动态数组的元素在内存中是连续存储的，这使得在访问元素时具有较好的性能，尤其是随机访问。
-
动态数组的实现一般使用底层的静态数组作为存储空间，并通过动态分配和释放内存来调整数组的大小。
3.集合(Set)
集合（Set）是一种常见的数据结构，用于存储一组不重复的元素。集合中的元素没有特定的顺序，可以快速地进行插入、删除和查找操作。
集合的主要特点包括：
-
无序性：集合中的元素没有特定的顺序，不像数组或列表那样按照索引进行访问。这意味着在集合中不能通过索引来访问元素，只能通过元素本身来进行操作。
-
唯一性：集合中的元素是唯一的，不允许重复。如果尝试将重复的元素插入到集合中，集合会自动忽略重复的元素。
-
插入、删除和查找的效率高：由于集合使用了一些高效的数据结构（如哈希表），插入、删除和查找元素的效率都很高。
映射(Map)
映射map是一种数据结构，用于存储键值对（key-value pairs）。每个键都唯一对应一个值，可以通过键来访问对应的值。映射map提供了快速的查找和插入操作，适用于需要根据键来查找值的场景。
常见的映射map实现：
-
哈希表（Hash Map）：使用哈希函数将键映射到桶（bucket），每个桶存储一个键值对。哈希表提供了常数时间的查找、插入和删除操作。
-
二叉搜索树（Binary Search Tree）：使用二叉搜索树的结构来存储键值对，保持树的左子节点小于父节点，右子节点大于父节点。二叉搜索树提供了对键的有序访问，查找、插入和删除操作的平均时间复杂度为O(log n)。
-
红黑树（Red-Black Tree）：是一种自平衡的二叉搜索树，通过维护节点的颜色和平衡性质来保持树的平衡。红黑树提供了对键的有序访问，查找、插入和删除操作的平均时间复杂度为O(log n)。
常用的映射map操作：
-
插入（Insert）：将一个键值对插入到映射map中。
-
查找（Find）：根据给定的键查找对应的值。 - 删除（Erase）：根据给定的键删除对应的键值对。
-
更新（Update）：根据给定的键更新对应的值。
-
迭代（Iterate）：遍历映射map中的所有键值对。
前缀和、差分、双指针（Prefix Sum、Difference、Two pointers）:
1.前缀和（Prefix Sum）
前缀和（Prefix Sum） 1前缀和是指原始数组中从第一个元素开始到当前位置的所有元素的和。
(计算方法：可以通过遍历数组，累加当前位置的元素与前一个位置的前缀和得到当前位置的前缀和。)
应用场景：
-
子数组和：可以通过前缀和计算子数组的和，如计算区间 [i, j] 的和可以通过前缀和数组 sum[j] - sum[i-1] 得到。
-
数组区间操作：可以通过前缀和计算数组区间的操作，如对区间 [i, j] 的每个元素加上一个值可以通过更新前缀和数组 sum[i] += k，sum[j+1] -= k 得到。
-
数组元素频次统计：可以通过前缀和统计数组中某个元素出现的频次，如统计数组中元素等于 k 的个数可以通过前缀和数组 sum[i] == k 的个数得到。
2.差分（Difference）
差分是指原始数组中相邻元素之间的差值构成的数组。
（计算方法：可以通过遍历数组，计算当前位置的元素与前一个位置的元素的差值得到差分数组。）
应用场景：
-
数组区间操作：可以通过差分数组进行数组区间的操作，如对区间 [i, j] 的每个元素加上一个值可以通过更新差分数组 diff[i] += k，diff[j+1] -= k 得到。
-
数组还原：可以通过差分数组还原原始数组，如通过差分数组 diff[i] 还原原始数组的第 i 个元素可以通过累加差分数组得到原始数组。
双指针（Two Pointers）
双指针是指在数组或链表中使用两个指针分别指向不同的位置，通过移动指针来解决问题的一种技巧。
使用方法：
-
快慢指针：通过设置两个指针，一个快指针每次移动两步，一个慢指针每次移动一步，来判断链表是否有环或找到链表的中间节点。
-
左右指针：通过设置两个指针，一个指向数组的起始位置，一个指向数组的末尾位置，来找到满足条件的子数组或区间。
-
对撞指针：通过设置两个指针，一个指向数组的起始位置，一个指向数组的末尾位置，根据问题的性质移动指针来逼近目标。