面试官：谈谈你对ArrayList和LinkedList的理解 |
您所在的位置：网站首页 › 声明arraylist › 面试官：谈谈你对ArrayList和LinkedList的理解 |
面试官：谈谈你对ArrayList和LinkedList的理解
|
前言 ArrayList和LinkedList作为java开发中常用的两个集合类型，本篇文章主要来谈谈二者的原理与区别。 本篇文章主要涉及以下几个内容： ArrayList底层实现ArrayList扩容逻辑LinkedList底层实现ArrayList与LinkedList对比ArrayList底层实现我们都知道，ArrayList底层是基于数组实现，那么数组有什么特点呢？ 数组的特点：使用一组连续的内存空间来存储具有相同数据类型的数据。需要注意的是，数组的空间大小是固定的，一旦申请数组就需要占用整块内存。 数组随机访问特性 由于数组的空间大小固定，存储的数据类型也相同，我们就可以通过寻址公式类随机访问数组中的任意一个下标的元素。 寻址公式如下： address[i] = baseAddress + i * dataTypeSize其中address[i]表示要访问的第i个元素的地址，baseAddress表示数组的基地址，dataTypeSize表示数组中存储的数据类型的大小。 举个例子，假如数组的基地址为100，数组存储的数据类型是整型数据，那么整型数据对应的dataTypeSize为4，如果要访问第1个数据，那么可以通过如下公式：address[1] = 100 + 1 * 4 计算得到第1个数据的地址为104，然后就内存位置对应的位置取出元素的值，这便是数组支持按照下标随机访问的特性。 回到ArrayList，看下ArrayList如何使用数组实现的。 在ArrayList中可以看到如下声明： //ArrayList底层的数组声明，用于存放具体的元素 Object[] elementData; public ArrayList() { this.elementData = {}; }调用ArrayList的默认构造函数，elementData被赋值为一个空数组。 ArrayList扩容逻辑因为ArrayList基于数组实现，而数组的空间大小是固定的，所以当数组的空间用完了 ，就需要对ArrayList底层的数组进行扩容。 比如：数组一开始申请的存储空间只能存10个元素，当我们要往数组中添加第11个元素时，就需要对数组进行扩容，才能够将新的元素放入到数组中。 当使用ArrayList默认的构造函数创建对象时，底层的数组实际是被赋值为一个空数组，但我们第一次调用往其中添加元素时，才会触发具体扩容逻辑，第一次扩容默认的初始化容量为10，使用了延迟加载的实现方式避免空间浪费。 扩容逻辑的核心实现是，计算当前ArrayList需要存储的最小数据量minCapacity的值是多少，然后判断当前底层数组elementData的大小与minCapacity的值的关系，如果elementData数组的大小大于minCapacity的值，则表示当前数组满足存储容量要求，不需要执行扩容逻辑；如果elementData数组的大小小于minCapacity的值，则表示数组需要扩容以存储更多的数据，具体是将数组的大小扩容为原来数据大小的1.5倍，新数组大小通过如下方式计算： int newCapacity = oldCapacity + (oldCapacity >> 1);当计算出的扩容后数组的大小newCapacity后，就需要执行具体的扩容逻辑，实现方式是通过申请一个容量为newCapacity的数组，将旧数组中的值都拷贝到新数组中，具体实现是通过System.arraycopy实现的数据拷贝，如下所示： //该方法底层native的实现 //original是旧数组，copy是新数组 //也就是将original中从下标为0开始的元素，拷贝到copy数组中，copy也是从下标 //0开始接收元素，具体拷贝的数据个数为original.length //也就是将original的，全部数据拷贝过去 System.arraycopy(original, 0, copy, 0, original.length);可以看到，当我们往ArrayList中添加元素的过程中，随着数据量的增多会触发多次扩容逻辑，但如果我们事先可以指定存储到ArrayList中的数据量，可以调用ArrayList的有参构造函数，事先指定一个固定大小的值作为ArrayList底层数组的初始容量，那么在后续往ArrayList中添加元素就可以避免多次的扩容逻辑。 LinkedList底层实现与ArrayList不同，LinkedList底层是基于双向链表实现，其中使用了head和tail指针分别指向链表头部和尾部的节点，当添加元素时，只需要通过tail指针往尾节点后面添加元素即可。 在数组中要求申请的内存块是连续的，而链表的实现不需要连续的内存块，链表中通过指针将链表中多个节点连接起来，链表中的每个节点除了存储自身的数据外，还需要申请额外的存储空间存储指向当前节点的前驱节点的指针prev和指向后继节点的指针next。 当我们向链表中添加元素时，只需要将新的数据节点添加到链表尾部即可。因为链表不需要保证内存空间的连续性，所以添加过程中不涉及具体的数据搬移操作。 ArrayList与LinkedList对比基于前面的介绍，我们了解到ArrayList和LinkedList底层实现的数据结构是完全不同的，因此二者的特性与使用场景也完全不同，下面我们来做个简单对比： ArrayList和LinkedList都实现了List接口，但LinkedList还实现了Deque接口，因此LinkedList还可以当成双向队列使用。ArrayList基于数组实现，因此它的优点是支持按照下标随机访问的元素，访问的时间复杂度为O(1)；但缺点也很明显，往ArrayList进行插入或删除元素的过程中，为了保持数组的连续性，会涉及到底层数组的数据搬移操作，平均时间复杂度为O(n)；另外ArrayList对内存的要求比较高，需要连续的内存块存储数据。LinkedList基于链表实现，因此它的优点是插入或者删除元素的过程中只需要执行特定指针操作即可，不涉及具体的元素搬移操作，时间复杂度为O(1)；它的缺点是不支持按照下标随机访问，当要访问链表中的某个元素时，只能从链表头部往后遍历，直到找到目标节点或者遍历到链表尾部为止，平均时间复杂度为O(n)；另外链表需要额外的内存空间来存储的每个节点前驱和后继节点的指针，因此会比数组多消耗一定的内存空间。小结今天主要是针对java中常用的集合ArrayList和LinkedList的原理进行了介绍，其中不涉及到具体的源码分析，感兴趣的小伙伴可以自行参考对应的源码实现。 由于小编技术水平有限，如果有什么错误的地方，欢迎留言指出，小编会在第一时间回复。 想要获取更多的内容可以关注我的微信公众号： 
|
【本文地址】