常见数据结构介绍（顺序表，单链表，双链表，单向循环链表，双向循环链表、内核链表、栈、队列、二叉树）
顺序表
顺序表是在计算机内存中以数组形式保存的线性表。它使用一组地址连续的存储单元依次存储线性表中的各个元素，通过数据元素物理存储的相邻关系来反映其逻辑上的相邻关系。
特点
存储结构：内存空间连续，数据元素按线性顺序存储，可通过元素下标直接访问。
固定大小：创建后大小固定，无法动态扩容或缩小，需事先确定存储元素个数。
访问速度：凭借下标访问元素，速度快，时间复杂度为 O (1)。
插入删除效率：插入或删除元素时，需移动后续元素，效率低，时间复杂度为 O (n)。
适用场景：适合静态存储数据，不太适合频繁动态增删的场景。
运算操作
插入操作：在表尾插入，先判断表是否已满，未满则插入；在任意位置插入，需先将插入位置及之后的元素后移，再插入新元素。
删除操作：删除表尾元素，直接操作即可；删除任意元素，需先定位元素位置，将其后元素前移，并更新表中元素个数。
查找操作：可根据元素值或位置查找。按值查找需遍历全表，按位置查找直接返回对应位置元素值。
遍历操作：可遍历全表，也可指定部分元素遍历，通过循环结构实现。
链表
链表是一种物理存储结构上非连续、非顺序的线性表，数据元素的逻辑顺序通过指针链接次序实现。
单链表
单链表中每个节点包含数据域和指向下一个节点的指针域。
特点
按需申请空间：插入新节点时动态分配内存，不用时释放，空间利用率高。
插入删除高效：在头部或中间插入、删除节点，只需修改指针，无需大量移动元素。
内存开销：每个节点需额外存储指针，增加内存开销。
访问方式：不支持随机访问，访问第 i 个元素需从头遍历，时间复杂度为 O (n)。
常见操作
创建新节点：动态分配内存，设置数据域和指针域。
打印链表：遍历链表，输出每个节点的数据。
尾插：找到尾节点，将新节点链接到尾节点之后。
头插：将新节点插入头节点之后。
尾删：删除尾节点，需先找到尾节点的前驱节点。
头删：删除头节点之后的第一个节点。
查找：根据给定值遍历链表查找节点。
在指定节点后插入：修改相关指针，将新节点插入指定节点之后。
在指定节点前插入：需先找到指定节点的前驱节点，再进行插入操作。
删除指定节点：修改前驱和后继节点的指针，绕过要删除的节点。
删除指定节点后节点：直接操作指定节点的后继指针。
销毁链表：依次释放每个节点的内存空间。
双链表
双链表每个数据节点包含两个指针，分别指向直接后继和直接前驱节点。
特点
双向访问：可方便地从前向后或从后向前遍历链表。
操作灵活：插入或删除节点时，只需修改相邻节点的指针，无需遍历全表找前驱节点。
基本操作
初始化：创建头结点，设置其前驱和后继指针都指向自身，形成闭环。
插入：在指定位置插入新节点，需修改新节点及相邻节点的前驱和后继指针。
删除：删除指定节点，修改相邻节点指针绕过该节点，并释放其内存。
查找：根据条件查找节点，可双向遍历，查找更灵活。
单向循环链表
单向循环链表是单链表的变种，尾节点的 next 指针指向头节点（或首节点），形成闭环。
特点
闭环结构：从任意节点出发可遍历整个链表。
头节点作用：头节点不存储有效数据，常作为哨兵节点简化插入 / 删除操作。若带头节点，链表判空条件为 head->next == head。
操作与单链表区别
创建：最后一个节点的指针指向头节点。
插入：新插入节点指针指向下一个节点，即使插入在最后位置，其下一个节点也是头节点。
删除：结合单向链表删除过程和单向循环链表特性，注意维护闭环结构。
双向循环链表
双向循环链表是特殊的双向链表，头结点的前向指针指向最后一个结点，后向指针指向第一个结点，最后一个结点的后向指针指向头结点。
特点
结合了双向链表和循环链表的优点，支持双向遍历，操作更灵活。
操作与双向链表区别
初始化：头结点的前驱和后继指针分别指向尾节点和首节点，尾节点的后继指针指向头节点。
插入删除：除修改相邻节点指针外，还需确保循环结构的完整性。
内核链表
内核链表是操作系统内核中使用的链表数据结构，用于管理内核对象（如进程、线程、文件等）。不同操作系统内核链表实现方式有差异，但都具备高效插入、删除和遍历的特点，以满足内核高效管理资源的需求。例如 Linux 内核中，链表操作通过宏定义实现，简化了代码编写，提高了执行效率。
栈
栈是一种特殊的线性表，仅在表尾进行插入和删除操作，遵循后进先出（LIFO）原则。
特点
操作受限：只允许在栈顶进行插入（入栈）和删除（出栈）操作。
数据存储：数据按后进先出顺序存储和访问。
常见操作
初始化：创建一个空栈。
入栈：将元素添加到栈顶。
出栈：移除并返回栈顶元素。
获取栈顶元素：返回栈顶元素但不删除。
判断栈是否为空：检查栈中是否有元素。
获取栈的大小：返回栈中元素个数。
应用场景
表达式求值：用于计算算术表达式，如后缀表达式求值。
函数调用栈：记录函数调用关系和局部变量等信息。
深度优先搜索（DFS）：在图或树的遍历中使用。
队列
队列也是一种特殊的线性表，只允许在表的一端进行插入（入队），在另一端进行删除（出队），遵循先进先出（FIFO）原则。
特点
操作受限：入队操作在队尾进行，出队操作在队头进行。
数据存储：数据按先进先出顺序存储和访问。
常见操作
初始化：创建一个空队列。
入队：将元素添加到队尾。
出队：移除并返回队头元素。
获取队头元素：返回队头元素但不删除。
判断队列是否为空：检查队列中是否有元素。
获取队列的大小：返回队列中元素个数。
应用场景
广度优先搜索（BFS）：在图或树的遍历中使用。
任务调度：操作系统中任务队列按顺序调度任务。
缓存管理：如网页浏览器的缓存队列，按访问顺序淘汰缓存。
二叉树
二叉树是每个节点最多有两个子树的树结构，子树分别称为左子树和右子树 。
特点
层次结构：具有明显的层次，根节点在顶层，向下延伸出子树。
节点度数：每个节点的子节点个数不超过 2。
常见类型
满二叉树：除最后一层无任何子节点外，每一层上的所有节点都有两个子节点。
完全二叉树：除最后一层外，每一层上的节点数均达到最大值；在最后一层上只缺少右边的若干节点。
遍历方式
前序遍历：先访问根节点，再递归访问左子树，最后递归访问右子树。
中序遍历：先递归访问左子树，再访问根节点，最后递归访问右子树。
后序遍历：先递归访问左子树，再递归访问右子树，最后访问根节点。
层序遍历：按层次从根节点开始，逐层从左到右访问节点。
应用场景
搜索算法：二叉搜索树用于高效查找数据。
表达式树：表示算术表达式，方便求值和分析。
赫夫曼树：用于数据压缩等领域。