面试的时候，一般会问不用的数据结构都有哪些特点？给你一个场景让你设计不同的数据结构数据结构：数据的存储格式以及它的组成格式。
1、首先先回答涉及的数据结构是什么样子的
2、然后再问答涉及到的数据结构它的有缺点分别是什么，怎么去弥补缺点。
需求：我想把A,B,C三个元素插入到栈数据结构中，怎么做？
存放的顺序：A、B、C
取出的顺序：C、B、A
栈的数结构特点：先进后出
举例现实生活中有哪些栈的实例：
1、子弹夹
2、煤炉烧煤球
队列需求：我想把A、B、C三个元素放入队列中，怎么做呢？
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-muoWEhEN-1644584699752)(C:UsersstuAppDataRoamingTyporatypora-user-imagesimage-20220211202132069.png)]
存放的顺序：A、B、C
取出的顺序：A、B、C
队列的数据结构的特点：先进先出
举例现实生活中有哪些队列的案例：
1、排队做核酸
数组长度是固定的，存储的元素数据类型是一直的，拥有下表索引，方便我们通过索引获取对应位置上的元素值，怎么定义一个数组？
静态数组：int [] arr = {11,22,33,44,55};
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-SXVTHyNt-1644584699753)(C:UsersstuAppDataRoamingTyporatypora-user-imagesimage-20220211202510717.png)]
数组的特点：查询快，增删慢
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-kjZTypz2-1644584699754)(C:UsersstuAppDataRoamingTyporatypora-user-imagesimage-20220211202605992.png)]
链表一个链条有多个节点组成的数据结构
结点：是有两部分组成，是由数据域和指针域组成，包含了数据和指针。需求：将11，22，33，44，55存放到链表中
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-gBR3KKVi-1644584699754)(C:UsersstuAppDataRoamingTyporatypora-user-imagesimage-20220211202754166.png)]
链表的特点：查询慢，增删快
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-1qLHvj8l-1644584699754)(C:UsersstuAppDataRoamingTyporatypora-user-imagesimage-20220211202906075.png)]
树Tree 它是由根和叶子节点组成的数据结构
叶子节点，当结点下面没有任何分支的时候，我们称之为叶子结点
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-CzAKGNfx-1644584699755)(C:UsersstuAppDataRoamingTyporatypora-user-imagesimage-20220211203711285.png)]
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-DSwdc5xp-1644584699755)(C:UsersstuAppDataRoamingTyporatypora-user-imagesimage-20220211203744941.png)]
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-fx0tZoXc-1644584699755)(C:UsersstuAppDataRoamingTyporatypora-user-imagesimage-20220211203730924.png)]
二叉树的遍历顺序 ：前序遍历，中序遍历，后序遍历，注意：这里的前中后指的是根的顺序
前序遍历：根左右，从最顶层的根开始遍历：11，22，44，33，55，66
中序遍历：左根右，从最顶层的根开始遍历：22，44，11，55，33，66
后序遍历：左右根：44，22，55，66，33，11
工作面试必备哈弗曼树（最小生成二叉树）哈夫曼树相关的几个名词当用 n 个结点（都做叶子结点且都有各自的权值）试图构建一棵树时，如果构建的这棵树的带权路径长度最小，称这棵树为“最优二叉树”，有时也叫“赫夫曼树”或者“哈夫曼树”。
路径：在一棵树中，一个结点到另一个结点之间的通路，称为路径。图 1 中，从根结点到结点 a 之间的通路就是一条路径。
路径长度：在一条路径中，每经过一个结点，路径长度都要加 1 。例如在一棵树中，规定根结点所在层数为1层，那么从根结点到第 i 层结点的路径长度为 i - 1 。图 1 中从根结点到结点 c 的路径长度为 3。
结点的权：给每一个结点赋予一个新的数值，被称为这个结点的权。例如，图 1 中结点 a 的权为 7，结点 b 的权为 5。
结点的带权路径长度：指的是从根结点到该结点之间的路径长度与该结点的权的乘积。例如，图 1 中结点 b 的带权路径长度为 2 * 5 = 10 。
树的带权路径长度为树中所有叶子结点的带权路径长度之和。通常记作 “WPL” 。例如图 1 中所示的这颗树的带权路径长度为：
WPL = 7 * 1 + 5 * 2 + 2 * 3 + 4 * 3
B+树 红黑树 自平衡二叉树图需要掌握红黑树的生成过程，红代表什么，黑代表什么？
有什么特点？
单一节点存储更多的元素，使得查询的IO次数更少。所有查询都要查找到叶子节点，查询性能稳定。所有叶子节点形成有序链表，便于范围查询。大数据中有哪些红黑树的案例？
需要掌握参数的变导致红黑树的变化，怎么去变化的？
红黑树的目的是什么？
将来有哪些优化方式？
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-50syFDlY-1644584699756)(C:UsersstuAppDataRoamingTyporatypora-user-imagesimage-20220211205259577.png)]
哈希表[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-I9xJWnLJ-1644584699756)(C:UsersstuAppDataRoamingTyporatypora-user-imagesimage-20220211205333318.png)]
集合ArrayList需求：使用ArrayList存储字符串并遍历（如果字符串有重复的需要去除）
public class ArrayListDemo1 { public static void main(String[] args) { //创建集合对象 ArrayList list = new ArrayList(); //向集合中添加元素 list.add("hello"); list.add("world"); list.add("java"); list.add("hadoop"); list.add("Hive"); list.add("hello"); list.add("world"); System.out.println("去重之前的集合为：" + list); //创建新的集合对象 ArrayList list2 = new ArrayList(); //创建迭代器 Iterator iterator = list.iterator(); //遍历旧的集合 while(iterator.hasNext()){ String s = (String) iterator.next(); //获取到元素之后，拿着这个元素去新集合中查找，如果找到说明重复，就不添加，反之添加到新集合中 if(!list2.contains(s)){ list2.add(s); } } System.out.println("去重之后的集合为：" + list2); }}
使用ArrayList存储自定义对象并遍历（并去重）
学生对象：姓名和年龄都一样的时候，表示是同一个人。
我们按照处理字符串重复的逻辑来处理自定义对象重复，发现结果并没有进行去重
为什么呢？
要想知道为什么，就得知道问题出现在了哪一行代码中。
经过简单地分析后发现，问题出现了在判断是否包含的那一行代码中
因为只有当if语句为true的时候，才会将元素添加到新集合中
说明我们这里判断，一直都是为true的，换句话contains这个方法并没有生效
要搞清楚为什么不会生效，就得搞清楚contains这个方法底层是怎么做的。contains方法底层调用的是equals方法，但是呢，Student类中并没有重写equals方法
所以调用的是Object类中的equals方法，而Object类中的equals方法比较的是地址值，学生对象都是new出来的
地址值必然不一样，equals比较的结果永远是false，加上我们代码中的！,结果永远是为true，所以无论如何都会添加到
新集合中，最终结果没有去重。解决方法：元素类重写equals()方法 自动生成即可
public class ArrayListDemo2 { public static void main(String[] args) { //创建集合对象 ArrayList list1 = new ArrayList(); //向集合中添加数据 Student stu1 = new Student("张飞",18); Student stu2 = new Student("马超",19); Student stu3 = new Student("关羽",20); Student stu4 = new Student("刘备",21); Student stu5 = new Student("张飞",18); list1.add(stu1); list1.add(stu2); list1.add(stu3); list1.add(stu4); list1.add(stu5); System.out.println(list1); //创建新的集合对象 ArrayList list2 = new ArrayList(); //迭代器 Iterator iterator = list1.iterator(); while(iterator.hasNext()){ Student student = (Student) iterator.next(); //注意这里contains里面包含的是equals方法，若Student类中没有重写equals方法的时候，运用的是Object的equals的方法 //相当于 == if(!list2.contains(student)){ list2.add(student); } } System.out.println(list2); }}
集合VectorVector:
底层数据结构是数组，查询快，增删慢
线程安全，效率低(虽然它是线程安全的，我们今后也不会去使用它，后面会说一个线程安全的类代替它)Vector特有的方法：
public void addElement(Object obj)
将元素添加到集合的末尾 效果上和add()一样
public Object elementAt(int index)
获取指定索引处的元素 get(int index)
public Enumeration elements()
返回此向量的组件的枚举。
public class VectorDemo { public static void main(String[] args) { //创建Vector集合对象 Vector vector = new Vector(); //向集合中添加元素 //public void addElement(Object obj) 将元素添加到集合的末尾 效果上和add()一样 vector.addElement("hello"); vector.addElement("java"); vector.add("hello"); vector.add("java"); System.out.println(vector); //public Object elementAt(int index) 获取指定索引处的元素 get(int index) System.out.println(vector.elementAt(3)); System.out.println(vector.get(3)); System.out.println("============================================="); //public Enumeration elements() 返回此向量的元素的枚举。 //简单记忆 你就把这个对象看作成一个迭代器 Enumeration elements = vector.elements(); while (elements.hasMoreElements()) { Object o1 = elements.nextElement(); String s = (String) o1; System.out.println(s); } }}
集合linkedListlinkedList:
1、底层数据结构是双链表，查询慢，增删快
2、线程是不安全的，效率高linkedList特有的方法：
1、添加功能：
public void addFirst(Object e) 在集合的开头添加元素
addLast(Object e) 在结合末尾添加元素，等同于add()方法
2、获取功能：
public Object getFirst() 获取集合中的第一个元素
getLast() 获取集合中的最后一个元素
3、删除功能：
public Object removeFirst() 从集合中删除第一个元素并返回
public Object removeLast() 从集合中删除最后一个元素并返回
public class linkedListDemo1 { public static void main(String[] args) { //创建linkedList集合对象 linkedList linkedList = new linkedList(); //向集合中添加元素 //public void addFirst(Object e) 在集合的开头添加元素 //addLast(Object e) 在结合末尾添加元素，等同于add()方法 linkedList.add("hadoop"); linkedList.addFirst("hello"); linkedList.addLast("java"); System.out.println(linkedList); System.out.println("========================"); //public Object getFirst() 获取集合中的第一个元素 //getLast() 获取集合中的最后一个元素 System.out.println(linkedList.getFirst()); System.out.println(linkedList.getLast()); System.out.println("========================"); //public Object removeFirst() 从集合中删除第一个元素并返回 //public Object removeLast() 从集合中删除最后一个元素并返回 System.out.println(linkedList.removeFirst()); System.out.println(linkedList.removeLast()); System.out.println(linkedList); }}
面试题：请用linkedList模拟栈数据结构的集合，并测试
栈的特点：先进后出
题目真正的意思是，自己写一个集合类，底层是linkedList,调用自己定义的方法实现栈数据结构。
class MyStack{ private linkedList linkedList; //构造无参的构造方法，初始化linkedList MyStack(){ linkedList = new linkedList(); } //自定义的添加方法 public void MyAdd(Object obj){ //想要先进后出，所有得将新加入的放在前面 linkedList.addFirst(obj); } //自定义的获取元素的方法 public Object MyGet(){ //如果使用linkedList.getLast()的话、获取的都是同一个元素// return linkedList.getLast(); return linkedList.removeFirst(); } //判断是否为空 public boolean myIsEmpty(){ return linkedList.isEmpty(); }}public class linkedListTest1 { public static void main(String[] args) { //创建自定义的集合 MyStack myStack = new MyStack(); myStack.MyAdd("hello"); myStack.MyAdd("java"); myStack.MyAdd("bigdata"); while(!myStack.myIsEmpty()){ Object o = myStack.MyGet(); System.out.println(o); }// //创建集合对象// linkedList linkedList = new linkedList();// linkedList.add("hello"); linkedList.add("world"); linkedList.add("java");// linkedList.addFirst("hello");// linkedList.addFirst("world");// linkedList.addFirst("java");//// //遍历// Iterator iterator = linkedList.iterator();// while (iterator.hasNext()){// Object next = iterator.next();// System.out.println(next);// }//// //如果面试的时候，遇到这样的题目// //按照上面的做法，一分都没有 }}
泛型泛型：
把明确数据类型的工作，提前到了编译时期，在创建集合的时候明确存储元素的数据类型。
这样的做法有点向把数据类型当作参数一样传递，所以泛型还有一个叫法：参数化类型泛型的语句定义格式：
<引用数据类型>
注意：尖括号中的数据类型只能是引用数据类型泛型的好处：
1、将我们运行时期出现的问题，提前到编译时期
2、不需要做强制类型转换
3、优化了代码。消除了不必要的黄色警告线，使代码看起来更简洁通过观察API发现，泛型可以出现在类，接口，方法上面，我们看到的类似于这样的都叫泛型，一般来说，泛型出现大多使用的集合中。
public class GenericDemo { public static void main(String[] args) { //创建一个List集合对象 //在JDK1.7之后，泛型会进行自动类型推断 ArrayList
/遍历
// Iterator iterator = list.iterator();
// while (iterator.hasNext()) {
// Object next = iterator.next();
//
// String s = (String) next; //ClassCastException
//
// System.out.println(next);
// }
//遍历 Iterator
}