进阶JavaSE(一)- List、栈、队列

在前面,我们讲完了JavaSE的基础语法部分,现在我们就来开始学习JavaSE最后很重要的一部分:集合。这一块,面试官也会经常问到,比如JDK1.8后,HashMap底层是如何实现的…… 话不多说,我们来看一下今天的主题:List。 在讲解List之前,我们先来看一下JavaSE集合的大致框架,分别包含了哪些集合,以及每个集合背后所多余的数据结构是什么。

进阶JavaSE(一)- List、栈、队列_第1张图片

进阶JavaSE(一)- List、栈、队列_第2张图片

以上全部就是JavaSE中的所有集合,后面的文章都是围绕这张图进行讲解。

前期文章

前言- IDEA如何配置?让你敲代码更轻松!

初识Java语言(一)- 基本数据类型及运算符

初识Java语言(二)- 方法以及递归

初识Java语言(三)- 数组

初识Java语言(四)-类和对象

初识Java语言(五)- 包和继承

初识Java语言(六)-多态、抽象类以及接口

初识Java语言(七)- String、StringBuilder和StringBuffer的区别

初识Java语言(八)- 异常

文章目录

  • 一、初始泛型(Generic)
  • 二、包装类
  • 三、Stack
  • 四、ArrayList
  • 五、LinkedList
  • 六、Queue
  • 七、Deque

一、初始泛型(Generic)

在前期我们学习JavaSE基础语法部分时,自己写的所有的类,都是固定了里面的元素类型,比如自己写的顺序表时,都是固定了写int类型,这样写本身是没有什么错的。但是不够通用。说的简单一点,假设现在我需要一个double类型的顺序表,只能自己重新在写一个类,很麻烦。

所以Java底层也是考虑到了这个情况,才引入了泛型(Generic)。顾名思义,泛型就是广泛的类型,其语法格式为: <类型>。 用一对尖括号,里面写着的就是类型名,将这个整体写到类的后面,我们才实例化这个类时,就可以给定相应的数据类型,如下:

进阶JavaSE(一)- List、栈、队列_第3张图片

//具体的使用方法
ArrayList<Integer> list = new ArrayList<>();

像上面这样,我们就实例化了一个顺序表,就可以在list里面进行顺序表的相关操作。

泛型,既有泛型类,也有泛型方法。这里我们只是初始泛型,具体的细节,我们会在后面专门来讲解这个。

泛型背后作用时期和背后的简单原理

  • 泛型是作用在编译期间的一种机制,也就是说在运行期间是没有泛型这个概念的。

泛型总结

  • 泛型是为了解决某些容器、算法等代码的通用性而引入的,并且能在编译期间做类型检查。
  • 泛型是利用Object是所有类的祖先类,并且父类的引用可以指向子类对象的特定而工作。
  • 泛型只是编译期间的一种机制,也就是说ArrayListArrayList是同一种类型。
  • 泛型是Java中一种合法的语法,标志是<>.
  • 泛型里面写的类型,必须是引用类型。基本数据类型,应书写相应的包装类。比如:int,写成泛型是

二、包装类

我们都是到java有8种基本数据类型,int、double等等。他们都是基本数据类型,我们前面文章讲过,除了基本数据类型以外,还有一个引用数据类型。而基本数据类型,每一个都有对应的包装类,这个包装类就是引用数据类型的。

进阶JavaSE(一)- List、栈、队列_第4张图片

如上图,8种基本数据类型所对应的包装类。除了char和int,其余的包装类,都是在原基础之上,将首字母大写即可。每一个包装类中,都有相应的方法可以使用,这里举一个例子:

进阶JavaSE(一)- List、栈、队列_第5张图片

包装类,能够拿到相应基本数据类型最大值和最小值等等。具体的,可以查看帮助手册。

自动装箱和自动拆箱

装箱:从基本数据类型的数据,转换为包装类的数据。拆箱反之。在使用过程中,java提供了自动机制,,如下代码:

int a = 10;
Integer aa = a; //自动装箱
Integer aaa = (Integer)a; //自动装箱

int b = aa; //自动拆箱
int bb = (int)aa; //自动拆箱

注:自动装箱和自动拆箱只是在编译期间的一种机制。 我们可以通过javap -c 类名进行反编译,查看底层是如何进行编译的。

三、Stack

Stack,是Java底层实现的一个栈。栈的特性:先进后出。

进阶JavaSE(一)- List、栈、队列_第6张图片

//实例化
Stack<String> stack = new Stack<>();
stack.push("hello world"); //将字符串压入栈
String str1 = stack.peek(); //返回栈顶的元素,并不会删除栈顶元素
String str2 = stack.pop()l //将栈顶元素弹出栈,但是会删除栈顶元素。注意与peek的区别
boolean flag = stack.empty(); //判断栈的是否还有元素

以上就是Stack,最基本的的使用操作。也比较简单,反反复复就是这些操作。

四、ArrayList

ArrayList,底层是一个顺序表,也就是一个数组。那我们来看一下,这个底层大致是怎么实现的?

进阶JavaSE(一)- List、栈、队列_第7张图片

由图可知,add方法默认是将元素放到数组的最后的

接下来分析ArrayList的实现:

进阶JavaSE(一)- List、栈、队列_第8张图片

看图,实例化ArrayList的时候,是赋值了一个空数组。那么为什么在往里面添加元素的时候,没有报异常呢?我们接着来看一下add方法。

add方法

进阶JavaSE(一)- List、栈、队列_第9张图片

总结:在实例化ArrayList的时候,调用无参的构造方法,构造的是一个没有容量的空数组,而只有在第一次添加元素的时候,add方法才会进行扩容(1.5倍),然后当ArrayList数组满了之后,add方法就会再次以1.5倍进行扩容。

以下就是ArrayList一些常用的方法:

进阶JavaSE(一)- List、栈、队列_第10张图片

//常用方法示例
ArrayList<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(2,3); //在下标为2的位置,插入元素3
System.out.println(list.contains(3)); //查询list中,是否有3这个元素
System.out.println(list.get(2)); //返回下标为2的元素。常用

int index = list.indexOf(3); //返回元素3,在表中第一次出现的位置。返回值是下标
list.remove(index); //删除index位置的元素
int size = list.size(); //返回当前list表中的元素个数

ArrayList中,底层是数组,那么从中间插入、删除元素。都是需要移动数组后面的元素的,跟数组的操作一模一样的。所以ArrayList这种集合,更适合于插入删除少的,但是查询次数比较多的场景。查询时间复杂度O(1),而插入删除操作时间复杂度O(N)。

五、LinkedList

讲完了ArrayList,现在就来讲解与之对应的LinkedList。LinkedList底层是一个双链表。如下:

进阶JavaSE(一)- List、栈、队列_第11张图片

双链表应该就不用多说了吧,即可以在头部插入删除,也可以在尾部插入删除。是一种比较灵活的数据结构。我们具体来看一下一些常用的方法:

进阶JavaSE(一)- List、栈、队列_第12张图片

图中红色框中,是使用LinkedList经常使用到的方法,无需记忆,用多了就记住了。

LinkedList<Integer> list = new LinkedList<>();
list.add(1); //在末尾添加元素
list.addFirst(10); //在头部添加元素
list.addLast(11); //在末尾添加元素
int num1 = list.getFirst(); //拿到队头元素,不会删除
int num2 = list.getLast(); //拿到队尾元素,不会删除

System.out.pritnln(list.contains(11)); //该表中是否有这个元素

//以下几种方法,本质上就是栈和队列中方法
int a = list.peek(); // 返回队头元素,并不删除这个元素
int b = list.peekFirst(); // 返回队头元素,并不删除这个元素
int c = list.peekLast(); //返回队尾元素,并不删除这个元素
int d = list.poll(); //弹出队头元素,并且会删除
int f = list.pollFirst(); //弹出队头元素,并删除
int g = list.pollLast(); //弹出队尾元素,并删除

六、Queue

Queue是Java语言实现的一个队列,满足先进先出的特性。Queue是一个接口类型,不能直接进行实例化,我们需要实例化一个LinkedList,用Queue来引用。二者之间的关系,请看上文中的那个集合图。

Queue<Integer> queue = new LinkedList<>(); 

进阶JavaSE(一)- List、栈、队列_第13张图片

图中,add方法和offer方法。两个方法都是在队尾加入元素。功能是一样的。在容量已满的情况下,add() 方法会抛出IllegalStateException异常,offer() 方法只会返回 false 。其他的方法,跟上面LinkedList中的方法差不多。remove方法,是删除队头的元素,而不是队尾的元素。队列是满足先进先出的原则的。

七、Deque

Deque,双端队列。也就是说既可以在队头插入和删除,也可以在队尾进行插入和删除。说白了,本质上还是一个LinkedList,只不过这是一个接口,实例化时,还是需要实例LinkedList。

Deque<Integer> deque = new LinkedList<>(); 

进阶JavaSE(一)- List、栈、队列_第14张图片

具体的方法,还是跟LinkedList差不多,只是可以在队头进行插入和删除,在队尾进行插入和删除。有一些方法名有点差别而已。无非就是add、offer、poll、isEmpty、size等等,以及一些变形的名字。

好啦,本期更新就到此结束啦!这篇文章主要就是介绍了这些集合的一些方法,比较多。各位同学无需记忆,在日常刷算法题的过程中,用多了,也就记住了。

好啦,我们下期见!!!

你可能感兴趣的