网站升级维护中页面,竞价外包代运营公司,自有电脑做网站服务器,wordpress幻灯片插件怎么用目录
一、前言
二、基本概念
三、相同之处
四、不同之处
五、ArrayList 底层
六、LinkedList 底层
七、ArrayList 应用场景
八、LinkedList 应用场景
九、ArrayList和LinkedList高级话题
十、总结 一、前言 在Java集合的广阔舞台上#xff0c;ArrayList与LinkedLis…目录
一、前言
二、基本概念
三、相同之处
四、不同之处
五、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倍是依旧不够放下数据的。 所以它此时会创建一个长度为实际长度为准的数组也就是101121位长度的数组然后再将数据添加进去。 总结查询快增删慢。 六、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支持泛型可以确保类型安全。你可以创建一个ArrayListPerson来存储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的工作原理和应用场景我们可以更好地利用这种数据结构来解决实际问题。
如果文章对您有帮助还请您点赞支持 感谢您的阅读欢迎您在评论区留言指正分享
