必背八股文-数据结构篇

数组与链表有什么区别？

• 存储结构：数组是一种顺序存储结构，它将元素存储在一段连续的内存空间中；而链表是一种链式存储结构，它将元素存储在多个独立的节点中，并通过指针来链接这些节点。
• 插入和删除操作：对于数组，插入和删除操作需要将后续的元素进行移动，因此时间复杂度为O(n)；而对于链表，插入和删除操作只需要修改指针的指向，因此时间复杂度为O(1)。
• 随机访问操作：由于数组的元素是连续存储的，因此支持随机访问操作，时间复杂度为O(1)；而链表的元素是通过指针链接的，不支持随机访问，需要进行遍历操作，时间复杂度为O(n)。
• 空间复杂度：由于数组需要一段连续的内存空间来存储元素，因此空间复杂度固定；而链表的元素是通过独立的节点来存储的，因此空间复杂度会比数组高出一定的开销。

栈和队列的区别？

• 元素的添加和删除方式：在栈中，元素的添加和删除都是在栈顶进行的，因此它是一种“先进后出”（LIFO）的数据结构；而在队列中，元素的添加是在队尾进行的，元素的删除是在队头进行的，因此它是一种“先进先出”（FIFO）的数据结构。
• 访问顺序：在栈中，只能访问栈顶的元素，而不能访问其他元素；在队列中，可以访问队头和队尾的元素，可以进行遍历操作。
• 应用场景：栈常用于需要后进先出的场景，例如函数调用、表达式求值等；而队列常用于需要先进先出的场景，例如消息队列、任务调度等。

set和list的区别？

1. 元素的存储方式：List是一种有序的容器类型，它将元素按照插入的顺序存储；而Set是一种无序的容器类型，它将元素按照哈希值或者比较函数的返回值进行存储。
2. 元素的访问方式：List支持通过下标或者迭代器访问元素，可以根据元素的位置进行随机访问；而Set不支持通过下标进行访问，只能通过迭代器进行顺序访问，不支持随机访问。
3. 元素的重复性：List允许元素重复，即可以在容器中添加多个相同的元素；而Set不允许元素重复，即添加重复元素时只会保留一个。
4. 查找效率：由于Set采用了哈希表的数据结构，因此在查找元素时可以达到O(1)的时间复杂度，比List要高效。

内存中的堆和栈

内存中的堆和栈，第一个区别就是申请方式的不同：栈是系统自动分配空间的，而堆则是程序员根据需要自己申请的空间。由于栈上的空间是自动分配自动回收的，所以栈上的数据的生存周期只是在函数的运行过程中，运行后就释放掉，不可以再访问。而堆上的数据只要程序员不释放空间，就一直可以访问到，不过缺点是一旦忘记释放会造成内存泄露。

申请效率的比较：栈由系统自动分配，速度较快。但程序员是无法控制的。堆是由new分配的内存，一般速度比较慢，而且容易产生内存碎片，不过用起来最方便。

散列查找：（hash表）

构造方法：

数字关键词：1. 直接定址法；例如年龄或者出生年。2. 除留余数法。

字符串关键词：1. ASCII码加和法；例如a3、b2和c1散列值相等。2. 前3个字符移位法。3. 移位法。

处理冲突的方法：

开放地址法：1. 线性探测法，增量序列1，2.。。。；2. 平方探测法，增量序列1^2，2^2.。。。；3. 双散列探测法；4. 再散列法。

分离链接法：通过结点链接存储在同一个单链表中。

简述一下什么是红黑树

红黑树（Red-Black Tree）是一种自平衡二叉搜索树，它能