筑基期
1. 什么是数据结构？数据结构和算法之间的关系是什么？
数据结构是一种组织和存储数据的方式，让我们可以更高效的对数据进行访问和修改。
算法则是在数据结构的基础上操作数据的步骤及方法。
我们可以把数据结构理解为存放数据的容器（如列表、栈、队列等），而算法就是在这些容器里进行操作的工具（如排序、搜索等）。
数据结构是存储数据的基础，而算法则是处理数据的规则。选择合适的数据结构可以让算法更高效。
2. 数组和链表的区别是什么？分别有哪些优缺点？
数组：是一块连续的内存区域，所有元素的大小固定，数组通过索引直接访问元素。
优点：通过索引访问查找速度快，内存紧凑。
缺点：插入、删除元素操作时需要移动大量数据，速度慢；初始化时确定大小，长度不可变。
链表：由节点组成，每个节点包含数据和指向下一个节点的指针。
优点：插入、删除操作灵活，动态扩展内存。
缺点：查找时需要从头遍历，速度慢，额外存储指针消耗内存。
假设现在有一串人排队（数组），想在中间插入一个人，需要把后面的人都挪开（移动数据）。
如果是链表，插入时只需改变两个邻近人的手拉手关系（调整指针）即可。
3. 什么是栈？栈的基本操作有哪些？栈的应用场景是什么？
栈 是一种遵循 后进先出（LIFO）原则的数据结构，想象一个叠盘子的场景，最后放上去的盘子最先取下来。
基本操作：
压栈（Push）：把元素放到栈顶。
出栈（Pop）：从栈顶移除元素。
查看栈顶元素（Peek）：查看栈顶的元素但不移除它。
栈常用于处理需要回溯的场景，如浏览器的前进/后退功能、递归调用的函数栈等。
就像吃饭时一层层叠盘子，最上面的盘子（最后放的）必须先拿下来，其他盘子才能动。
4. 队列和栈有什么区别？队列的主要操作是什么？
队列 遵循 先进先出（FIFO）原则，想象排队买票，排在最前面的人先服务，排在最后的最后才轮到。
栈 遵循 后进先出（LIFO）原则，最新加入的元素最先被移除。
队列的主要操作：
入队：将元素添加到队尾。
出队：从队首移除元素。
排队买票时，最早来的人先买到票，排在后面的人只能等前面的人买完了再轮到自己。
5. 什么是链表？链表的基本操作有哪些？
链表 是一系列节点组成的线性数据结构，每个节点包含两个部分：数据和指向下一个节点的指针。
链表不像数组那样占用连续的内存，元素可以动态插入或删除；链表可以分为单向链表、双向链表、循环链表。
基本操作：
插入节点：可以在链表的任意位置插入节点，只需调整相邻节点的指针。
删除节点：可以删除任意节点，调整指针使得前后的节点连接在一起。
遍历：从头节点开始，依次访问链表的每个节点。
就像一串手拉手的孩子（节点），我们可以随时插入新孩子到任何位置，只需改变相邻孩子的拉手顺序（调整指针）。
6. 如何反转一个单向链表？
逐步遍历链表并调整每个节点的指针方向，使得链表的指向由前向后变为由后向前。
思路：
定义三个指针：
prev（前一个节点），current（当前节点），和next（下一个节点）。遍历链表，对每个节点将它的
next指针指向prev，然后更新prev和current，直到链表的尾部。最后，
prev就是反转后的新头节点。
总的来说就是改变指针，例如我们有单向链表：A -> B -> C -> D。
反转时从 A 开始遍历，将 A 的 next 指向取消，将 B 的 next 指向 A，依次类推，最终 C 就会变成头部。
7. 什么是哈希表？哈希表的原理是什么？哈希冲突如何解决？
哈希表 是一种通过 哈希函数 将 键 映射到数组索引位置的数据结构，支持快速插入、删除和查找操作。
哈希表通过将键值对（key-value）映射到一个数组的索引位置来存储数据，哈希函数负责将键转换为对应的索引。
简单来说就是哈希表的底层其实是一个数组，每个 key 通过哈希函数计算后可以得到一个数组下标，没那么将这个键值对存储到数组对应的这个下标位置即可。
当两个键被映射到相同的索引位置时，称为哈希冲突。常见的解决方法有：
链地址法：在哈希表的每个索引位置上存放一个链表，冲突的元素依次添加到链表中。
开放地址法：如果发生冲突，通过一定的探测机制（如线性探测）寻找下一个可用位置。
想象一个班级中的抽屉柜（哈希表），每个抽屉都有一个编号（索引），我们可以根据某个规则（哈希函数）把学生的书放入指定的抽屉。
如果两本书要放进同一个抽屉（哈希冲突），我们可以让书排成一排（链地址法）或找其他空抽屉（开放地址法）。