每日八股：数据结构

数组和链表区别是什么？

访问效率：数组可以通过索引直接访问任意位置的元素，访问效率高，时间复杂度为O(1)，而链表需要从头节点开始遍历到目标位置，访问效率低，时间复杂度为O(n)。

插入和删除操作效率：数组插入和删除元素可能需要移动其他元素，时间复杂度为O(n)，而链表是需要修改指针的指向，时间复杂度为O(1)。

缓存命中率：由于数组元素在内存中连续存储，可以提高CPU缓存的命中率，而链表节点不连续存储，可能导致CPU缓存的命中率较低，频繁的缓存失效会影响性能。

应用场景：数组适合静态大小，频繁访问元素的场景，链表适合动态大小，频繁插入和删除元素的场景。

说一下队列和栈的区别

主要区别在于元素的插入和删除方式以及元素的访问顺序。

插入和删除方式：

队列：队列采用先进先出（FIFO）的方式，即新元素插入队尾，删除操作发生在队首。

栈：栈采用后进先出（LIFO）的方式，即新元素插入栈顶，删除元素也发生在栈顶。

元素的访问顺序：

队列：队列的元素按照插入的顺序进行访问，先插入的元素先被访问到。

栈：栈的元素按照插入的顺序进行访问，但是最后插入的元素最先被访问到。

队列适用于需要按照插入顺序进行处理的场景，例如任务调度。

栈适用于需要维护最近操作状态的场景，例如函数调用。

红黑树说一下，跳表说一下？

红黑树是一种自平衡的二叉搜索树，它在插入和删除操作后能够通过旋转和重新着色来保持树的平衡。红黑树的特点如下：

1.每个节点都有一个颜色，红色或黑色。

2.根节点是黑色的。

3.每个叶子节点都是黑色的。

4.如果一个节点是红色的，则它的两个子节点都是黑色的。

5.从根节点到叶子节点或空子节点的每条路径上，黑色节点的数量是相同的。

红黑树通过这些特性来保持树的平衡，确保最长路径不超过最短路径的两倍，从而保证了在最坏情况下的搜索、插入和删除操作的时间复杂度都为O(logN)。

跳表是一种基于链表的数据结构，它通过添加多层索引来加速搜索操作。

跳表的特点如下：

1.跳表中的数据都是有序的。

2.跳表中的每个节点都包含指向下一层和右侧节点的指针。

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

二叉树搜索最坏的时间复杂度，为什么会这样？以及用什么结果解决？

当每次插入的元素都是二叉查找树中最大的元素，二叉查找树就会退化成一条链表，查找数据的时间复杂度变成了O(n)。

为了解决这一问题，提出了平衡二叉查找树（AVL树）。主要是在二叉查找树的基础上增加了一些条件约束：每个节点的左子树和右子树的高度差不能超过1。也就是说节点的左子树和右子树仍然为平衡二叉树，这样查询操作的时间复杂度就会一直维持在O(logn)

B+树的特点是什么？

1.B+树是一种自平衡的多路查找树，所有叶节点都位于同一层，保证了树的平衡，使得搜索、插入和删除操作的时间复杂度为对数级别的。

2.非叶节点仅包含索引信息，不存储具体的数据记录，它们只用来引导搜索到正确的叶节点。非叶节点的子树指针与关键字数量相同，每个子树指针指向一个子树，子树中的所有键值都在某个区间内。

3.所有数据记录都存储在叶节点中，且叶节点中的数据是按关键字排序的。叶节点包含实际的数据和关键字，它们是数据存储和检索的实体单元。叶节点之间通过指针相互链接，形成一个链表，便于范围查询和顺序遍历。

堆是什么？

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

LRU是什么？如何实现？

LRU是一种缓存淘汰算法，当缓存空间已满的时候，优先淘汰最长时间未被访问的数据。实现的方式是哈希表+双向链表结合。

具体实现步骤：

1.使用哈希表存储数据的键值对，键为缓存的键，值为对应的节点。

2.使用双向链表存储数据节点，链表头部为最近访问的节点，链表尾部为最久未访问的节点。

3.当数据被访问时，如果数据存在于缓存中，则将对应节点移动到链表头部；如果数据不存在于缓存中，则将数据添加到缓存中，同时创建一个新节点并插入到链表头部。

4.当缓存空间已满时，需要淘汰最久未访问的节点，即链表尾部的节点。

LRU算法可以在O(1)的时间复杂度内实现数据的插入、查找和删除操作。每次访问数据时，都会将对应的节点移动到链表头部，保证链表头部的节点是最近访问的数据，而链表尾部的节点是最久未访问的数据。当缓存空间不足时，淘汰链表尾部的节点即可。

说几个你懂的排序算法，并说明其时间空间复杂度

1.冒泡排序：通过相邻元素的比较和交换，每次将最大（或最小）的元素逐步冒泡到最后（或最前）。时间复杂度：最好情况下O(n)，最坏情况下O(n^2),平均情况下O(n^2)。空间复杂度O(1)。

2.插入排序：将待排序元素逐个插入到已排序序列的合适位置，形成有序序列。时间复杂度：最好情况下O(n)，最坏情况下O(n^2),平均情况下O(n^2)。空间复杂度O(1)。

3.选择排序：通过不断选择未排序部分的最小（或最大）元素，并将其放置在已排序部分的末尾（或开头）。时间复杂度：最好情况下O(n^2)，最坏情况下O(n^2),平均情况下O(n^2)。空间复杂度O(1)。

4.快速排序：通过选择一个基准元素，将数组划分为两个子数组，使得左子数组的元素都小于（或等于）基准元素，右子数组的元素都大于（或等于）基准元素，然后对子数组进行递归排序。时间复杂度：最好情况下O(nlogn)，最坏情况下O(n^2),平均情况下O(nlogn)。空间复杂度：最好情况下O(logn)，最坏情况下O(n)。

5.归并排序：将数组不断分割为更小的子数组，然后将子数组进行合并，合并过程中进行排序。时间复杂度：最好情况下O(nlogn)，最坏情况下O(nlogn),平均情况下O(nlogn)。空间复杂度O(n)。

6.堆排序：通过将待排序元素构建成一个最大堆（或最小堆），然后将堆顶元素与末尾元素交换，再重新调整堆，重复该过程直到排序完成。时间复杂度：最好情况下O(nlogn)，最坏情况下O(nlogn),平均情况下O(nlogn)。空间复杂度O(1)。