深入List集合：ArrayList与LinkedList的底层逻辑与区别

目录

一、前言

二、基本概念

三、相同之处

四、不同之处

五、ArrayList 底层

六、LinkedList 底层

七、ArrayList 应用场景

八、LinkedList 应用场景

九、ArrayList和LinkedList高级话题 

十、总结

---

一、前言

        在Java集合的广阔舞台上，ArrayList与LinkedList以其独特的魅力，演绎着数据结构与算法的微妙平衡。一个静如处子，以数组之基，实现高效随机访问；一个动如脱兔，借链表之灵，擅长灵活插入删除。让我们一同潜入技术深海，探寻这两大集合类的独特魅力与适用之道。

二、基本概念

ArrayList定义：
        ArrayList是Java中的一个动态数组实现，它属于List接口的子类。ArrayList能够根据需要自动调整其大小，存储的元素是有序的，并且可以通过索引快速访问。它支持泛型，可以存储任何类型的对象，同时提供了添加、删除、查找和遍历等一系列常用的操作方法。
LinkedList定义：
        LinkedList是Java中的一个双向链表实现，同样实现了List接口。与ArrayList不同，LinkedList中的元素不是存储在连续的内存空间中，而是通过节点之间的引用连接起来的。每个节点都包含数据部分以及指向前一个和后一个节点的引用。LinkedList也支持泛型，并提供了与ArrayList类似的常用操作方法。

三、相同之处

        ArrayList和LinkedList作为Java中List接口的实现类，具有一些共同点。它们都能够动态地存储元素，并且可以根据需要自动调整容量大小。同时，它们都支持泛型，可以存储任何类型的对象，并且保证了类型安全。
        这两种集合类都维护了元素的插入顺序，使得元素可以按照添加的顺序进行访问。此外，它们都提供了一系列常用的操作方法，如添加、删除、查找和遍历等，这些操作都可以通过List接口中的方法进行调用。
        因此，在Java编程中，ArrayList和LinkedList都可以作为有序集合类来使用，根据具体需求选择适合的实现类即可。
 

四、不同之处

        ArrayList和LinkedList是Java中两种常用的List接口实现，它们在内部实现和性能特性上存在显著差异。
        ArrayList基于动态数组，支持通过索引快速访问元素，但在插入和删除元素时可能需要移动其他元素，时间复杂度较高。而LinkedList则基于双向链表，插入和删除操作只需修改相关节点的前后引用，时间复杂度较低，但随机访问元素需要从头节点开始遍历，性能较差。
        此外，ArrayList在内存上需要预留空间并可能在扩容时产生额外开销，而LinkedList的每个节点则需要额外的内存来存储前后节点的引用。因此，在选择时应根据具体使用场景来决定。

五、ArrayList 底层

        arraylist集合的底层其实是基于数组实现的，数组我们并不陌生。
        数组的特点：数组其实实在内存当中的一块连续区域，并且它会把这一块连续的区域分割成若干个相等的小区域，每块区域都有自己的索引，每个区域都是用来装一个数据的。
 
        数组最重要的特点就是他的查询速度是非常快的，但是很多人直接说数组的查询速度很快，这个其实是不准确的，它严格来说是根据索引查询数据比较的快。从头到尾的查很慢。
        但是如果是根据索引来查就是非常快的了，就比如说需要查2号索引处的数据，它可以一下子定位数组位置，因为数组有一个自己的起始地址，起始地址可以找到最左侧的位置，如果要查2号索引处的数据，直接让起始地址加2，就可以定位到索引为2的位置，最后将数值C取出来。
        同样，如果要查5号索引处的数值，那么直接让起始索引加5就可以了。所以这才是它根据索引查询速度快的原因。也就是它是通过地址值加索引来进行定位的。查询任意数据耗时是相同的。也就是不管你是查询2号位置的数据还是5号位置的数据它所要耗费的时间是一样的，所以说它根据索引查询速度快。
        但是它的删除效率是很低很低的，如果要删除B值，删除以后需要将后面的所有值一个一个的向前挪一位，这样才能保证数据的连续性，所以如果数据量大的时候，这样大量的去迁移数据的时候，就会带来一些性能问题，所以说它的删除效率是比较低的。

        同样，添加的时候也是效率极低的，需要将添加位置后面的所有数据向后移动。或者是当我的数组已经满了的时候，我再添加数据的时候我这里面不够放怎么办？他又要扩容，就是把数组的范围变大，然后再把数据又迁移过来再把新添加的数据放在空出来的位置上去。所以又要扩容又要迁移，他的效率一定是不会高的。

        那么扩容到底是如何使用数组来实现的呢？细节是怎么回事呢？
        当我们使用无参构造器去创建这个集合对象的时候，他就会在底层创建一个默认长度为0的数组，也就是一个没有任何数据的空数组然后会用一个size来记录数组的大小，当我们第一次添加数据到里面去的时候，他会创建一个新的长度为10 的数组，交给elementData来记录。
 
        在添加第一个数据之后，会将size指向它的第二个索引。同理，每加一次数据之后，size都回向后移动相应的距离。
 
 
        当数组存满之后要怎么办呢？

        当我们在存第11个数据的时候，他就会自动将数组的长度扩容到原来的1.5倍，也就是将数组长度变为15。但是注意，它是创建了一个长度为15 的数组，所以它会再将原来长度为10 的数组内的原数据迁移到长度为15 的新数组中，然后再把新数组放到后面去。
 
 
        如果一次性添加多个数据，比如说如果一次性添加11个数据，那么它其实1.5倍是依旧不够放下数据的。
        所以它此时会创建一个长度为实际长度为准的数组，也就是10+11=21位长度的数组，然后再将数据添加进去。

总结：查询快，增删慢。

六、LinkedList 底层

        Linkedlist的底层是基于双链表实现的
        那么什么是链表呢？链表起始是由一个一个结点组成的，这些结点在内存中并不是连续存储的，而是在内存中分散存储的，但是链表的每个结点他除了会包含数据值之外，还会包含下一个结点的地址信息，通过这个地址信息，我们是可以找到下一个地址结点的，这样就实现了一个结点链接另一个结点的形式，这就是所谓的链表。
 
（如图所示），我们可以从头开始顺藤摸瓜的找到每一个结点。也就是找到每一个数据进行相应的处理。
        那么链表是如何形成的呢？
        在添加第一个数据A的时候，它会被记为链表的头结点，我们可以通过地址找到头结点再找到整个列表。再添加第二个数据B，数据会有一个自己的地址，假如说地址是11，然后它会将地址交给头结点A来记住。
 
        同理，再向后添加数据D、E 的时候，只需要使前一个数据记住他们的地址值即可完成首尾相连的链表形结构。
 
        那么链表数据结构有什么特点呢？
 
        查询比较慢：无论查询哪个数据都要从头开始找，包括根据索引查也同样是慢的，为什么呢？比如说要找到第二个位置处的数据，是不能马上找到第二个索引位置处的，因为它的元素在内存中不是连续的，不可能通过头部地址一下子定位到这个位置，即使要找2号索引位置处的数据也只能从头开始找。

        增删比较快：如果需要在链表中添加一个数据C，那么只需要把数据C放到任何一个位置，然后让C对应的下一个数据地址指向D，然后让B指向C（将B存储的下一个数据地址改成C的地址）。
 
        这样就添加进去了，也不需要挪动原来元素的位置。而且也不存在扩容的问题，因为它的元素在内存中都是分散存储的，无论加多少数据都是不存在扩容或者移动原来元素位置的。所以说添加的速度是比较快的。
 
        如果要删除CE之间的数据D，那么只需要将C对应的下一个数据地址指向数据E，然后再将数据D删除就可以了。也不需要迁移元素。
 
        单向链表与双向链表：
        linkedlist是双向链表，除了从前往后查找之外，同时它的每一个结点也会记前一个结点的地址，也就是说可以从为结点开始从后往前找。所以双向链表就是可以从两头开始查。所以说双向链表的查询速度要胜于单向链表，但是因为链表只能从前往后找或者从后往前找，所以他的查询速度还是要慢于可以直接利定位索引位置的数组的。只是增删的时候速度要优于数组。
 
        在java中大多数情况都会使用双向链表。

七、ArrayList 应用场景

        ArrayList 是一种基于数组实现的动态数据结构，在Java集合框架中扮演着重要角色。它通过自动调整数组大小来适应元素数量的变化，提供了高效且灵活的存储方式。以下是ArrayList在多个生动应用场景中的具体应用：
        1.    动态数组存储
场景描述：
        想象你正在编写一个程序，需要存储用户输入的一系列数据，但事先并不知道用户会输入多少数据。这时，一个能够动态调整大小的数组就显得尤为重要。
ArrayList应用：
        ArrayList正是为此而生。它可以根据需要自动调整大小，无需担心数组越界的问题。你可以随时向ArrayList中添加或删除元素，而无需手动管理数组的大小。
        2.    批量数据处理
场景描述：
        在数据分析或科学计算中，经常需要处理大量的数据。这些数据可能来自文件、数据库或网络请求等。
ArrayList应用：
        ArrayList提供了高效的批量数据处理能力。你可以将大量数据一次性添加到ArrayList中，然后利用Java提供的各种集合操作方法来处理这些数据，如排序、搜索、过滤等。
        3.    对象集合管理
场景描述：
        在面向对象编程中，经常需要管理一组对象。例如，你可能有一个Person类，需要存储多个Person对象的集合。
ArrayList应用：
        ArrayList支持泛型，可以确保类型安全。你可以创建一个ArrayList<Person>来存储Person对象的集合，并利用ArrayList提供的各种方法来管理这些对象，如添加、删除、查找等。
        4.    作为方法参数和返回值
场景描述：
        在编写方法时，有时需要传递或返回一组数据。这些数据可能来自方法的内部处理，也可能需要传递给其他方法进行处理。
ArrayList应用：
        ArrayList可以作为方法参数和返回值来传递或返回一组数据。这样，你可以利用ArrayList的灵活性和高效性来简化方法的编写和调用。
        5.    实现简单的数据结构
场景描述：
        在算法和数据结构的学习中，经常需要实现一些简单的数据结构，如栈（Stack）和队列（Queue）的简化版。
ArrayList应用：
        虽然ArrayList不是专门为栈和队列设计的，但你可以利用它的动态调整大小和随机访问特性来实现这些数据结构的简化版。例如，你可以使用ArrayList的add方法在末尾添加元素来实现栈的压栈操作，使用remove(int index)方法或get(int index)方法结合remove方法来实现栈的弹栈操作；同样地，你也可以使用ArrayList来实现队列的简化版。

八、LinkedList 应用场景

        LinkedList 是一种非常灵活的数据结构，它基于链表的原理，通过节点（Node）之间的引用（或指针）来存储数据。每个节点包含数据部分和指向下一个节点的引用。这种结构使得 LinkedList 在很多应用场景中都表现出色。
        1. 队列（Queue） - 先进先出（FIFO）
场景描述：
        想象你在一家银行排队办理业务。第一个人先来，第一个被服务；后来的人只能排在队伍后面，等待前面的人办完业务后再轮到自己。这就是典型的先进先出（FIFO）原则。
LinkedList应用：
        在 LinkedList 中，我们可以将队列设计成使用头节点（head）和尾节点（tail）来管理。新元素总是添加到队列的尾部，而移除操作总是从队列的头部进行。这样，最早加入的元素总是最先被移除。
        2. 栈（Stack） - 后进先出（LIFO）
场景描述：
        想象你有一堆书，每次你只能看到最上面的一本书。如果你想取一本书，你必须先移除上面的所有书。这就是后进先出（LIFO）原则。
LinkedList应用：
        在 LinkedList 中，栈的实现非常简单。我们只需要一个指向栈顶（即最后一个加入的元素）的引用。新元素总是添加到栈顶，移除操作也总是从栈顶进行。这样，最后加入的元素总是最先被移除。
        3. 双向链表（Doubly Linked List） - 双向遍历
场景描述：
        想象你在一个环形跑道上跑步，你可以向前跑，也可以随时停下来向后跑。双向链表允许你从任意节点向前或向后遍历。
LinkedList应用：
        双向链表（Doubly Linked List）的每个节点除了包含数据和指向下一个节点的引用外，还包含一个指向前一个节点的引用。这使得双向链表在需要频繁进行前后遍历的场景中非常有用，比如实现撤销（Undo）操作、滑动窗口算法等。
        4. 散列表的冲突解决（Linked List as a Collision Resolution Method）
场景描述：
        想象你有一个很大的书架，但上面的书没有按照任何顺序排列。当你想要找一本书时，你可能需要从头开始一本一本地找，直到找到为止。在散列表（Hash Table）中，如果两个键的哈希值相同（即发生冲突），我们可以使用链表来解决这个冲突。
LinkedList应用：
        在散列表的实现中，当发生冲突时，我们可以将具有相同哈希值的元素存储在一个链表中。这样，虽然查找某个特定元素可能需要遍历链表，但总体上仍然保持了散列表的高效性。
        5. 实现图（Graph）的邻接表（Adjacency List）
场景描述：
        想象你有一张复杂的交通网络图，每个城市都是一个节点，城市之间的道路是连接这些节点的边。邻接表是一种用链表来表示图中节点之间连接关系的方法。
LinkedList应用：
        在图的邻接表表示法中，每个节点都有一个链表，链表中包含与该节点直接相连的所有节点。这种方法在处理稀疏图（即边数远少于节点数平方的图）时非常高效，因为它避免了使用二维数组来存储边信息时的空间浪费。

九、ArrayList和LinkedList高级话题 

        在Java中，ArrayList和LinkedList作为两种常见的集合实现，与多种设计模式有着密切的联系。以下是与ArrayList和LinkedList相关的一些设计模式介绍：
        迭代器模式（Iterator Pattern）
        迭代器模式是一种设计模式，它提供了一种方法顺序访问一个聚合对象中的各个元素，而不暴露其内部的表示。在Java中，ArrayList和LinkedList都实现了Iterable接口，因此它们都支持迭代器模式。
o    特点：
o    提供一个统一的接口来遍历集合中的元素，而无需了解集合的内部结构。
o    迭代器模式将集合的遍历操作从集合类中分离出来，使得集合类的职责更加单一。
o    在ArrayList和LinkedList中的应用：
o    ArrayList和LinkedList都通过实现Iterable接口来提供迭代器。
o    迭代器内部维护了一个指向当前元素的游标（cursor），通过调用hasNext()和next()方法来遍历集合中的元素。
        观察者模式（Observer Pattern）
        虽然ArrayList和LinkedList本身并不直接实现观察者模式，但它们可以作为观察者模式中的被观察对象（Subject）或观察者（Observer）来使用。
o    特点：
o    定义对象间的一种一对多的依赖关系，当一个对象改变状态时，其相关依赖对象皆得到通知并被自动更新。
o    观察者模式主要用于实现事件处理系统、消息广播系统等。
o    在ArrayList和LinkedList中的潜在应用：
o    如果有一个集合对象（如ArrayList或LinkedList）需要通知其他对象关于其内容的变化（如添加、删除元素），那么可以将该集合对象作为被观察对象，其他对象作为观察者。
o    当集合对象发生变化时，它可以通过调用观察者的更新方法来通知它们。
        然而，需要注意的是，在Java的标准库中，ArrayList和LinkedList并没有直接提供对观察者模式的支持。如果需要实现观察者模式，通常需要自定义一个被观察对象类，并在该类中维护一个观察者列表，以及相应的添加、删除和通知观察者的方法。
        其他相关设计模式
除了迭代器模式和观察者模式外，还有一些其他设计模式与ArrayList和LinkedList有关，如：
o    工厂模式：可以用于创建ArrayList或LinkedList的实例，而无需直接调用它们的构造函数。
o    单例模式：虽然与ArrayList和LinkedList的直接关系不大，但在某些情况下，可以使用单例模式来确保一个集合类只有一个实例（尽管这通常不是集合类的常见用法）。
o    装饰器模式：可以用于在不修改现有集合类的情况下，为其添加新的功能或行为。例如，可以        创建一个装饰器类来包装一个ArrayList或LinkedList，并在其基础上添加日志记录、性能监控等功能。
        总的来说，ArrayList和LinkedList作为Java集合框架中的核心组件，与多种设计模式有着紧密的联系。通过理解和应用这些设计模式，可以更加灵活地使用这些集合类，并构建出更加健壮、可扩展和可维护的软件系统。

十、总结

        ArrayList是一种高效且灵活的动态数据结构，在多个应用场景中都表现出色。从简单的动态数组存储到复杂的对象集合管理，再到作为方法参数和返回值传递或返回一组数据，ArrayList都能提供高效且直观的解决方案。通过理解ArrayList的工作原理和应用场景，我们可以更好地利用这种数据结构来解决实际问题。

如果文章对您有帮助，还请您点赞支持
感谢您的阅读，欢迎您在评论区留言指正分享