day23_集合/13-尚硅谷-Java语言高级-List接口常用实现类的对比

那接下来呢，咱们讲一下这个collection它的一个子接口啊，叫做list接口，这个list接口首先呢，我们关注的就是它的这个存储数据的特点啊，是有序的哎可重复的，那通常呢，咱们把这个list它的这个哎接口以及它具体的实现类看作是呢，是对咱们原来这个数组的一个替换，所以咱们在昨天讲到这个集合框架的时候呢，说我们通常把这个类测接口呢，看做叫动态数组，叫做这个动态数组，这个数组呢，咱们说有个特点，就是一旦呢，说实话长度就不能改了，你想扩容的话呢，得重新去拗啊，你还得自己去造一个，造完一个以后呢，你还得把原来数据呢给它copy过来，那对于我们这个list子来讲，似乎呢，就意味着大家不用去关注它的长度够不够的问题。它动态的就帮我们去把这个长度就做了一个变化啊，大家呢，形象这样去理解就可以了啊，以后呢，大家如果去重装数据，像以前用数组，你得先告诉我我造多长的，那现在我们要用数组用集合的话呢，大家就不用了，你就直接造完这个集合，直接就往里填就完了，不用考虑会不会冒的情况啊，其实就相当于呢，就避开了原来的这个角标越界的异常。

啊，非常的方便啊，那这呢，我们就开始要使用这个list，讲一下它里边的具体的这个操作，那list呢，作为一个接口，它的具体的实现类呢，有这样的三个啊，那首先我们关注一下，就这三个结构，它们之间又有哪些不同啊这样的一个问题，好，咱们呢去新建一个啊这呢我就叫做关于诶历史的一个测试了。首先咱们把这个list的这个整个，呃，从从从这吧，把这个框架结构呢，先给大家引进来啊，在这块CTRLC一下。

拿过来，嗯，这个就不要了。行collection collection是这样子的，然后这个例子呢，存储有序的可重复的数据，我们称作叫做动态数组啊，使用它呢来替换。哎，原有的这个数组，哎，本质上器官数组的是我们的list，具体呢，有三个实现类，我们这块呢，把它们打开来说明一下。嗯，来说明一下啊，所以呢，这块我们先说的第一个事儿啊，第一个事儿呢，就是我这块呢，讲一下这三个啊，具体实线类的区别，或者叫异同，而这道呃，这个这个题呢，也是一道非常经典的面试题啊，那就是让你去比较一下叫aist link的list啊，以及呢，我们叫vector啊，他们三者的异同，哎三者的异同，那异同异同那先考虑的就是叫同有什么相同点啊。

对，你仨类是不是都是实现这个接口了啊，都是作为我们这个接口的实现类出现的，而这个接口呢，存的数据是这样的特点的，那就是你们仨是不是也得这样特点了，对啊，这个我们写一下啊，就是三个类啊都实现了啊实现了哎，咱们这个叫list接口啊，存储数据的特点相同。哎，这个所谓的相同呢，就是我们提到的啊，就都是有序的可重复的数据，好这呢，就是他们的这个相同点没了，那么主要呢，我们关注的就是它们三者的这个不同点，那么这个不同点呢，哎，我就写到这儿吧，写到这儿了啊，那首先呢，我们说一下这个叫ear list earest呢上来大家就可以指明说ear呢，它是作为。

哎，作为什么呢？作为我们这个list接口的主要实现类。啊，一提到主要实现类，那EIG呢，就是大家如果没有特殊的需求的话呢，大家呢，需要用一个有序的可充的数组来替代咱们的这个，呃呃结构来替代咱们应用数组，大家默认呢，你就去new一个list就完了啊基本上我们用的都是它这两个呢，就基本上都不用，所以说它叫主要的实现类，这个呢叫主要实现类，哎，其实最明显的就是先要说这个vector呢，它呢是作为我们list接口的一个古老实现类。诶，古老实验类怎么叫古老呢？我们看看它什么时候出现的啊，先看这个vector吧，Ctrl c ctrl shift t。

1.0，相当于咱们有这个Java语言的时候，出推出的第一个版本里边呢，就有vector了，哎，用它呢，来存储这个有序的可重复的数据，OK a release ctrl c ctrl shift t。而list1.2的时候出现的啊，它是1.2中出现的，然后呢，我们看下这个link list ctrl，呃，直接点一下就行。它也是1.2出现的，就是link list和a list呢，出现的都相对晚一些，他们都实现了这个list接口，看看list接口什么时候出现的，1.2出现的都老了，它比接口出现的还老。啊是吧，它是1.2啊，那就相当于回过来说这个咱们在1.0的时候啊，就有一个vector用它呢去来存储这个叫有趣的可重复的数据了啊大家就用着，然后呢，到这个JDK1.2的版本的时候呢，出来这个接口叫list，后来才出来的啊出来这个接口以后呢，紧接着就提供了它的两个实现类。

然后呢，我们也把这个VE呢，又归到它的这个接口下面了，呃，就是这样的一段历史，呃，咱们把这个VE呢，看作它的一个古老实线类，其实有点像什么呢？就是像，嗯，比如说像那个朝代当中这个，呃原来就算是有一个，比如说上一个皇帝的一些这个老臣是吧，现在呢，就突然又出来一个新的皇帝了，然后这个新的皇帝呢，是不是有自己的一帮这个亲信是吧？哎，都是人家的一个体系的，然后你这个老臣呢，他也就归到这个体系下了，哎归到体系下呢，显然这个是不是不受待见啊，那这块呢，肯定就基本上有事就不找你了啊，人家就用这个主要实现类了啊，这里边呢，是不是就提到一个叫release了啊，而这link的list也用啊，它俩呢，我们等一下展开说有什么区别啊，至少呢，提出来这个VE呢就不怎么用了，所以我们你是个老的是吧，哎，古老时间类啊，那么它作为一个主要时间类，它作为一个古老时间类。

啊，基本上开发中不会去用，其实主要原因是什么呢？哎，我们先说他俩啊，主要原因是我们这个俄啊，它的执行效率比较高。办事比较利落是吧，啊，执行效率高，执行效率高的原因是什么呢？对，是因为它是一个线程安全感啊，那进进而呢，它这个就效率高，全不安全啊，说错了，对不安全的啊，对不安全，它效率高的，这是分号一下，而我们这个vector呢，它正好相反，它呢是一个线程安全的，那安全的话呢，就对应的就是效率就低了，有这样的一个对比，那么我们看下这个vector vector里边对应了很多方法，往下拽，拽着拽着你就发现，哎哟，好多西红男子的。这个位置没有啊，是不是私有的了，私有的呢，你对外是不是也不暴露直接调用啊，我在这里边调，嗯，我在其他的方法里在这里调了，你调的话呢，这加同步了，这是不是就不用加了，哎，对啊，所以你会看到它这个，呃，一些公共的方法呢，它就会加这个S了，那就同步了，所以呢，你这个效率就差一些，哎，我们这个list，呃，A list，嗯，A list啊这里边你去看它就没有这个同步了，我就不打开看了啊哎，有这样的一个点，哎，这样的点，这呢就属于他们俩的一个对比，这呢也算是这个不同了，那你要说有什么相同呢？除了这个事儿之外呢，它俩呢还有一个相同点，那就涉及到这个底层结构。

这个底层呢，我们a release它呢是使用使用object类型的数组存储，说白了a release呢，说用你来替换数组，其实呢，它只是对数组的一个封装，底层呢，数据仍然存在我们的数组当中。

啊，这个就是涉及到我们数据结构了，数据结构里边呢，这个像数组是一种典型的存储方式啊，他们都是用的数组结构啊，我们这个vector呢，底层也是使用的object数组。这个我们可以看源码，很容易的就能看得到啊，Ctrl c ctrl shift t a release，点开哎，A list，然后在这里边我们能够看到一个哎结构就是它啊就是这个啊，底层这个数组就是object类型的，它啊叫element data，这个呢，你也可以顺便呢给它哎拿过来也行啊，咱们讲这个呃，String的时候呢，它底层那个叫value是吧。String string buffer叫value吧，它那个数组类型是什么呀？差呗，其实从这个角度来讲，咱们讲的这个string也好，String buffer也好。啊，40BUFF啊，他们是不是也是容器啊，只不过这个容器呢，它这个使用的范围非常小啊，它只能是承装这个差型的，这个数据对于咱们这个集合来讲呢，是object类型的啊，都可以装啊，其实呢，它一定程度上也是容器啊，就是字符串，那么这是它，然后这个呢也是啊，你可以在我们这个vector啊，Ctrl c ctrl shift t进来，这得往上找一点。

啊在这啊一样，那都是呢，用这个数组去存的啊，因为我们添加的时候呢，你可以加任何类型的对象，所以呢，就是object类型的啊很好理解，成这呢，就我们提到他们两的的一个对比啊，咱们暂且呢先说到这儿啊先到这这呢就是这个情况说完了，然后接下来呢，我们说一下这个叫link list，这个link list呢，他也是我们这个list接口中定义的，属于我们这个新的一套这个皇帝下的一套班子了啊那这个人呢，是一个重臣是吧，主要的一个事贤类啊，找事儿，有事呢没事就基本上都找他啊，那么这个呢，就是属于一个其次的了。

啊，这个其次的话呢，跟它有什么区别呢？他们俩呢，就平时呢有些分工了，那这个link的list呢，哎，你看它这个使用上啊，它叫linked，而这个呢叫array，这个类名呢，不是乱起的啊，Array的一个list，我们底层呢，是不是就用arra数组啊，你这是一个link的link就是一个链表的意思啊，有个链铁链子啊，就是这种连接起来的这种结构啊，所以说呢，它们俩的主要区别就是底层结构的区别啊，对于我们这个link的例子来讲，它呢，我们说底层它呢是使用的叫双向链表啊存储，这就涉及到数据结构中的另外一种特点啊，这呢是一个顺序存储的数组，这呢是一个链表结构啊，咱们等一下看下这源码啊，那么使用这个链表存储和数组存储呢，表现出来的一些点就不同了啊，什么不同呢？对，就涉及到我们对这个数组元素的。

直接操作了，那另一个的意思呢，我们什么时候用呢？我们说啊对于啊这个频繁的呢，叫啊增加增加，其实主要呢，涉及到这个插入哈，这块对于频繁的插入和删除操作，哎，我们这使用此类呢，效率比咱们的耳丽高，看分号一下，原因是什么呢？就是因为它底层呢是使用双向列表来存储的。啊，双业列表来存储的，简单的我们说一下这个事儿其实大家很好理解啊，你想我们在这个release当中，既然一体层是用数组存的，一个两个三个，四个，五个，六个七个，好，嗯，有点小了啊，七个简单的来说一下，比如说呢，我们现在想把这个元素呢给它删掉，咱们前面呢也做过相关的练习了，虽然说这时候我们用的是list，但是它底层只是相当于我们把咱们之前写的那个数组的操作它给封装好了。

做法其实一样啊，也得是后一个去替换前一个啊，一直这样去替换才可以，那你想象一下，如果我们现在这个呃，使用a list呢，装数据，我装了1万条，我现在呢把第三条数据删掉，这个事呢挺崩溃的是吧，那就后边第四个往前移，第五个往前往前移一一直到这个第1万个数据，效率其实挺差的，这个呢是做了一个删除啊，然后对于这个插入呢，我现在呢，想在123第四个位置插入一个元素。那你这些元素都得往后移，所以呢，这时候你你们得这个这个哎往后移，你得先移最后一个啊，这个往后移往后移，往后移往后移，哎把这个空出来，把这个新元素呢，哎放到这儿。这呢叫插入，那还是那个道理，我现在有1万条数据，我想在第三个位置插入一条数据啊，那你从这个第1万个啊，往后移往后移，往后移往到这个第三条呢，诶插到这。

效率呢比较差啊，效率比较差，那同样的这个事儿呢，我们看一下link list啊，Link list呢，人家是一个双向列表，咱们以前没有讲过，其实也不难理解，就是这个，这是具体的一个元素了，这个元素的话呢，它会有这样的呃三块啊，这个呢是存在它的核心数据，这个对，就是它的前一个元素是谁，这个是它的下个元素是谁。如果它是第一个元素，它的前一个的没有，那就是no呗，哎，我们有第二个元素还是这样，然后呢，这个就是相当于你指向它的下一个，这个呢指向你的上一个啊，再接着这样，这呢就叫做双向链表啊，再接着，哎，再这么着啊等等等等等往下啊好，这呢是用一个链表去存储的了，我现在想把这个元素删掉，我想把它删掉，假设后边还非常长。

这时候你想跟后边这些呢，就没有关系了，对就没有关系了，怎么做呢？嗯怎么做，我就把它过掉就行，嗯，我呢这样做，把你这个要删掉的这个元素，你的这个next地址你给我，我呢，诶指向它。对吧，哎，然后的话呢，这个呃，你呢，指向了上个源头的地址啊，你给我我去指向它。中间呢，到你这块呢，是不是就把你给自然而然的就过掉了，因为我这块呢，原来是它现在到它这个指针不就没有了吗？啊然后这个这个呢指向它，然后你现在改成指向它了，这个就没有了，嗯，其实这块呢，你就没你事了。就当于这个人给这个人传话，这个人给这个传话，现在呢，就我直接给人家传了啊，我这呢也直接给人家去对接了，你呢就被解聘了是吧？啊这呢就相当于是给他删掉了，嗯，那同样的道理，比如我们在这个位置啊，这个元素和这个元素之间，我想插入一个元素。

哎，插个元素叉，元素呢，那就是原来呢你这个地址呢，你是给他的，现在呢，你把你这个地址你给我，我去指向，哎，然后呢，你呢你指向我，哎这个呢元素你呢原来是指向它，你别指他了，你把这个地址你给我，我去指他，然后呢你呢你指我，这样这不就相当于插入一个元素了，后边的也没有关系。哎，所以呢，这个时候我们会发现，不管你现在有1万条还是10万条数据，我想删第三个位置，只跟第二个和第四个有点关系啊，跟前跟这个其他的这些都没关系啊，像插入也同样的道理，所以说我们如果在这个代码当中频繁的会做一些啊，进来了又出去了，出去了又进来了啊，你要用一个结构去存储的时候呢，建议使用link list，它呢也能做，但是效率会很差啊，这呢就是它们三者的一个对比。

啊，那这里边提到这个不同呢，我们就是啊减上是吧，哎，你看下这个结构就行，那另一个类似呢，咱们刚才这不也提到了，那毕竟提到了稍微看一下所谓的这个双向列表这个结构啊，哎，它ctrl c ctrl shift t一下进来，进来以后你会发现这里边儿没有所谓的所谓的这个数组了。我们只会看到了一个叫first，一个叫last，这个呢是记录一下它列表结构中的第一个元素和最后一个元素的啊，你要再往下看，说你这个node所谓的就是你这里边的具体的一个元素，能不能看到呢？也能，那再看呢，就得看更深层次的代码了，就涉及到你这里边要去做一个添加，哎添加这里边呢，又叫这个，哎这里边呢，这不就真实的我们每一个元素呢，它都叫一个node了，哎，点开这个node类型，这不就是你这个数据本身，你的下一个元素，你的上一个元素。

啊，我在这个PPT里面呢，给大家也稍微简单的呃，显示了一下这样的一个逻辑啊，诶在这这就是底层的这个核心的代码。行，我们先把这个停一下，然后接下来呢，我们去说一下这个源码的分析啊。