数据结构八股

线性数据结构

• 数组:数组的内存空间是连续的，随机访问的时间复杂度是01，适用于需要按索引访问元素的场景，但是插入和删除元素较慢，时间复杂度是On
• 链表:链表是由节点组成，节点之间是分散存储的，内存不连续，每个节点存储数据和指向下一个节点的指针。适用于频繁插入和删除元素的场景，随机访问元素较慢。
• 栈:栈是一种后进先出（LIFO）的数据结构，只允许在栈顶进行插入和删除操作。
• 队列:队列是一种先进先出(FIFO)的数据结构，允许在队尾插入元素，在队首除元素
• 树:树是一种非线性数据结构，由节点和边组成，每个节点可以有多个子节点。树适用于表示层次关系的场景，例如文件系统、组织结构等。

数组和链表区别是什么?=>ArrayList与LinkedList

• 访问效率:数组可以通过索引直接访问任何位置的元素，访问效率高，时间复杂度为0(1)，而链表需要从头节点开始遍历到目标位置，访问效率较低，时间复杂度为O(n)。
• 插入和删除操作效率:数组插入和删除操作可能需要移动其他元素，时间复杂度为0(n)，而链表只需要修改指针指向，时间复杂度为O(1)。
• 应用场景:数组适合静态大小、频繁访问元素的场景，而链表适合动态大小、频繁插入、删除操作的场景

栈

两个栈实现队列效果

树

二叉树--->平衡二叉树--->红黑树--->B树--->B+树

红黑树（hashmap与epoll）

特点

1. 每个节点都有一个颜色，红色或黑色。
2. 根节点是黑色的。
3. 每个叶子节点(NIL节点)都是黑色的。
4. 如果一个节点是红色的，则它的两个子节点都是黑色的。
5. 从根节点到叶子节点或空子节点的每条路径上，黑色节点的数量是相同的。

实现效果（重点）

确保最长路径不超过最短路径的二倍，避免像完全平衡二叉树一样，插入和删除都会导致数据结构发生改变

为什么HashMap选择红黑树而不是平衡二叉树

确保最长路径不超过最短路径的二倍，避免像完全平衡二叉树一样，插入和删除都会导致数据结构发生改变-->这也是为什么Hashmap使用红黑树的原因

为什么epoll会选择红黑树

传统的 select 和 poll 使用 数组或链表 存储监听的文件描述符，需要 线性扫描（O(N)） 整个文件描述符集合，性能会随 FD 数量增长而下降。
epoll 通过红黑树存储监听的文件描述符，每次插入、删除或查找 只需 O(log N)，大幅优化了 epoll_ctl() 操作的效率。

跳表（Redis的Zset)

特点：

1.跳表中的数据是有序的。
2.跳表中的每个节点都包含一个指向下一层和右侧节点的指针。

实现思想

跳表通过多层索引的方式来加速搜索操作。最底层是一个普通的有序链表，而上面的每一层都是前一层的子集，每个节点在上一层都有一个指针指向它在下一层的对应节点。这样，在搜索时可以通过跳过一些节点，直接进入目标区域，从而减少搜索的时间复杂度。

实现原理

创建一个节点，生成0-1的随机数，<0.25就增加一层高，直到>0.25确定最后的层数(最高为64)。

复杂度

跳表的平均搜索、插入和删除操作的时间复杂度都为O(logN)，与红黑树相比，跳表的实现更加简单，但空间复杂度稍高。跳表常用于需要高效搜索和插入操作的场景，如数据库、缓存等。

堆

堆是一颗完全二叉树，这样实现的堆也被称为二叉堆。堆中如果节点的值都大于等于其子节点的值，我们把它称为大顶堆，如果都小于等于其子节点的值，我们将其称为小顶堆。

图形

1. 深度优先搜索（DFS）

原理：DFS 采用 回溯 思想，优先沿着某一条路径走到底，再回溯到上一个分支点继续探索其他路径，直到遍历完所有可能的路径。

2. 广度优先搜索（BFS）

原理：BFS 采用 队列 结构，从起点开始，按层级依次遍历所有相邻节点，再向外扩展。

3.DFS 和 BFS 的比较