107 - Java入门极速版 - 进阶语法 - 集合 - ArrayList和LinkedList的对比

大家好，我是海波老师，我们继续来讲Java集合中的list，前面已经讲了，咱们list接口中的两个时间类，一个叫a list，另外一个呢，我们叫link list，那么都是集合对象，但是底层啊，它们的实现方式略有不同，咱们的a list呀，它的底层呢，采用的是数组的这种结构呢，来管理和组织数据，而我们的这个叫link的历史呢，它采用的是一种链表的结构来管理和组织数据，所以啊，我们一般情况下就会对这两个集合的对象呢进行对比，比如我们增加数据，哪一个集合的对象抄的会快一些，那么查询数据的时候呢，又是哪一个集合的对象的会快一些，那么既持对比啊，咱们把这个图形呢，给大家画一画，我们通过图形的方式让大家体会一下它们之间的区别啊，首先呢，我们回过头来先把咱们这个历史呢给大画一画，来，我们复制一下。复制完成以后，我们来，咱们在我们右边的空白的地方，咱们画上一下来，这个呢，就是我们所谓的一个叫A历，然后呢，我们再来啊，咱们回头我们再来，我把咱们的这个link的历史呢，我们复制一下来，复制复制完成以后呢，我们回到咱们的这个地方来啊来回来，我们回来以后呢，我们就放到我们当前的这个位置，咱们准备做一个对比了。

首先呢，我们先给大家添加数据啊，咱们往里面添加数据，我们放我们的第一条数据，诶这个我先去掉啊。我先把这个呢，去掉，是我们的里面的东西，现在呢，我们来添加一个我们的第一条数据，我们就叫张三就可以了，我们写上它叫张三，好，那么把这个张三呢，我们准备好，我们现在准备往这两个集合里面放，感受一下我放一条数据的时候，他们的效率怎么样，谁快还是谁慢，是吧？那比方说我把张三我们往这里放，我往这里放的话，我该怎么做呢？意思啊，我放到这以后就不管了，意味着我对象构建出来以后，我只要通过一个箭头往下去指向它就可以了，同学们记住，我现在只需要指向它就可以了。啊，那么我们接下来把张三拿过来，那我们这边呢，我们的张三我放进去，你会发现这个时候呢，我需要把first关联到我的张三，所以我的箭头给它关联一下，好，我们这里呢，把它放过来啊来。

然后呢，我再把箭头呢，我们往这里放就可以了，同学们，这个是我们的操作，诶老师，那么我们在当前的情况下，我就发现了，我们的张三只要一个箭头，我们的张三需要两个箭头，那么是不是在这个场合下，这个a release它要比我们的link list快呀，其实不是这样的，为什么呢？因为咱们之前讲过了，我们的a list最开始时候里面没有这个黄色的小格子，对不对？只有当你放第一个元素的时候，它会开辟三个黄色的空间，它会创建三个的小格子，然后再关联到我们的对象，所以啊，咱们从我们的画图的角度来讲的话，我要画一个两个，三个，还有第四个，对不对，而我这里只需要画两个是不是就可以了？那从这个角度来讲的话，我们的另的历史它应该是胜出的，所以啊，我们的文字咱们写上一下来。咱们在下面呢，咱们说一下。

我们增加我们的第一条我们的数据，咱们link的啊list它会比我们的A啊list快一些啊，会比它快就可以了，好，这是我们增加我们的一条数据，那同学们，那么我们接下来我们准备增加二条数据了，二条数据呢，就是我们的理四了，所以来我们复制一下。复这以后我把这两个颜色呢，我们给它变成我们的这个颜色，表述的是已经存在的数据，这绿色呢，表示我要新增的数据，我叫李四，好了，同学们，现在我准备把理四的数据往这边增一下，好弄完了以后大家看啊，记住我们这个创建的过程，你不用管它，我们现在说的是效率的问题，所以我们的箭头只需要加一个我们的，哎，它就可以了，加一个箭头诶就加一个啊就加一个，好，那我加完之后，那么我们这边也得放个对象，对不对，那么你放个对象的话，我们的张三和李四就得关联在一块了吧，咱们不说其他的，就说追加的问题，所以我们就把李四放到这边，然后呢，把我的张三我放到这边对不对，放完了以后，我这个拉大一些，把这个last放这边，大家看一下，放完了以后这个箭头保持不变吧，那么我们的last是不是应该干嘛，应该给它关联到李四吧，然后呢，张三要能找到李四，所以他们俩之间还要关联在一块儿，所以这又得加个箭头，诶，翻过来，翻过来以后我们往这边。

那我们再来复制一下，好换过来，那同学们现在怎么样？同学们发现从我刚才的演示步骤的角度来讲的话，我的理式只要加一个箭头就行了，但是呢，我们的理式放在我们的link list里面，我得有一个箭头，我们的两个箭头，我们的三个箭头吧，诶，所以从这个角度来讲的话，咱们的a release更快一些，对吗？哎，所以我们哎写上。那叫第二条数据啊，第二条数据，然后呢，我们的a list啊，它会比我们的link list会更快一些，所以呢，哎，好了。那这是我的第二条数据，那如果我现在放第三条数据，所以我们这里呢，给它来颜色呢，我标记成它表示已经存在的数据，我们准备放第三个，咱们叫张三李四黄五好了，往五呢，颜色呢，我们给它一个绿色，那么这时候我们往这放，往这放以后你会发现其实同样它只需要什么我们的这个就行了，好了，我往这边放怎么办？你会发现我要往我们这边放的情况下，同学们想一想这个问题来，那么这个时候大家可以想象一下我的last怎么了，诶放过来，我这里呢，再增加一个网五就可以了，对不对，增加增加以后还是这个箭头指向我们的网五，然后呢，我们这里呢也复制一下，把它添加过来，把这个增加过来给同学们。

反向一下谁更快一些，其实从这个角度来讲的话，是不是还是我们的release更快一些啊，所以我们增加我们的第三条数据没问题了啊。好，我们的增加我们的第三条数据，大家会发现我们当前的这个数组的容量是不是已经满了，满了的情况下，如果你现在准备加第四条数据，来咱们看一看我们增加我们的第四条数据，那么我们说张三李四王五，我们照六了，那么写上它我们就叫照六，对吧？好了，那么照六的情况下，把它的颜色变成绿色，往里面添加，你会发现这个照六怎么了，你放不进去，放不进去的原因是因为它里面已经满了吧，如果你想往里面放，那么我的a release怎么办？它需要扩容吧？

这个大家还记得吗？它是需要扩容的，对不对？然后呢，我们再回过头来看这边，我们这边需要扩容吗？不需要，我们只需要跟刚才一样，把这个last往后挪一挪是不是就可以了，挪完了以后把这个照六我们复制过来，然后把这个箭头我们放过来，就会发现我们后续的所有追加数据的操作不是全都是这样子的，能不能明白同学们，哎，就是这样，所以也就意味着我们从这个角度来讲的话，当我们的容量不够的时候，我们的这个link list明显它的效率会更快，为什么？因为我们的这个release还需要扩容，还是需要拷贝的，所以性能就会比较差一些，所以我们说一下，增加第四条。

第四条，然后呢，我们括号啊超过容量。咱们超过容量啊，超过容量，那么我们的这个叫link list，它应该比我们的release更快一些，对吧。好了啊，这是我们的这种情况，好，我们再给大家说一种情况什么呢？就是往中间插入，比方说啊，我们再来个田七啊，这个呢，我们就写上它了啊翻过来。翻过来，然后呢，我们这里呢，也给它变过来啊好变过来以后干嘛呢？我增加一个田七，如果增加一个田七的话，大家看一下，哎，我们增加一个填七可以了，那么把它变成我们的绿色，这个时候如果是我们数组当中我们去增加的话，但是我是插入，什么叫插入啊，我往张三和李四里面去插入数据。这个时候会出现什么情况，这时候就你就会发现，由于我们数轴的连续性，你往里面增加的情况下，我们的理四和Y5，包括我们的兆六是不是就得往后挪呀，对不对，它的每一个值都得往后挪，咱们之前说过了，我就不演示了，那么我们这里来看一看这个地方，我如果增加田七的话，往这个张三和李四的地方去添加的话，大家想想我们会怎么办，其实你会发现就简单了很多，我只需要把这个箭头我指向它，把这个箭头我指向它对不对，然后呢，我再复制一下，再一个反向箭头其实就可以了，然道理我这个地方再加一个反向箭头其实也就可以了，诶，所以啊，往里面插入数据的话，那么其实我们的这个另的例子，其实比我们的更快一些，对不对，所以我们说一下复制啊，我们想它咱们叫插入数据。

啊，咱们叫插入数据对吧，就是这样的，所以啊，咱们就不说别的了，同学们，咱们就看这几个项目，你就会发现我们谁快谁慢，其实都不一定，那都不一定，这个取决于咱们的应用场景和使用方式，对吧？你像我们增加第二条，第三条，当我们容量够的话，那么不是添加第一个的情况下，是不是非常快呀，但是呢，如果我们是什么呢？哎，容量不够，或者说我们插入数据的话，那么我们这个list就会比这个另的list会慢很多，所以啊，这就是我们之间的一个比较操作。

好了，同学们，那么我们的release link list他们在插入数据，谁快谁慢，我们是不是就知道了？哎，接下来我们再说查询数据的问题，那比方说咱就不说别的了，咱们就假设从我们当前的数据当中，我读取那个叫理事的数据。大家想想，我想从这个历史里面把这个理式的数据我读取出来，我该怎么办？那你说老师这个简单呀，我只要取那个索引为一的不就完事了吗？这不就马上出来了吗？对不对？哎，同学们，你们要记住啊，我要查的名字是李四。我可不知道李四这个数据的索引是什么，我不知道，那你该怎么查呀？对吧，你看到图了，你知道哦，这个李四是一，我不知道啊，我就想查询名称是李四的这条数据怎么办。

那是不是就只能一个一个去查了，为什么呢？你没有索引呢？你没有索引的话，你得先查第一个，看他是不是李四吧，你再查第二个，看他是不是李四，对不对，你就得一个一个去查了，这种查询方式我们称之为叫线性查找，来一个一个去找，你要巧了，他在第一个你很快就出来了，万一他要在最后一个呢，那不就慢了嘛，对不对？所以啊，Release如果你不知道，所以的情况下，你挨个遍历去找，它的性能不够快，应该是比较慢的。好，我们回过头来看咱们的这个link list，咱们的link list怎样，我们要查询李四，你会发现。他也只能一个一个找，他会从我们当前集合的头或者尾开始入手呢，干嘛呢去查找我的数据，那么我们从first找到张三，再从张三呢找到田七，再从田七再到找到李四也能找到，但是你会发现他同样也是线性查找，也就意味着我们也得一个一个去找，那其实还是那句话，效率是不够快的。

老师，那我根据索引访问呢？记住我们的link的意思是没有索引的概念的，它里面的索引其实就是顺序号，也就意味着它还是挨个去查找，所以这就跟我们之前的release就不一样，如果你知道索引去找的话，那么它的效率是非常快的，所以从查询的角度来讲，你有索引，那么肯定是他快，但是如果你没有索引的情况下，他们两个没有本质上的区别，同学们能不能明白老师说的意思啊？所以咱们总结一下，如果集合的数据容量没有达到数组的阈值的话，那么追加数据的时候应该是a release更快一些，如果像集合的指定位置插入数据，或者集合的数据容量不够的场合，那么link list的效率会更高一些。如果查询数据时啊，我们根据索引查询数据，那么我们的a list还更快一些，但是如果没有索引的话，我们的两个集合没有本质区别。好了，两个集合的对比呢，咱们就说到这里。