Java集合面试题汇总篇 (2)

ArrayList 采用数组存储,所以插入和删除元素的时间复杂度受元素位置的影响。 比如:执行 add(E e)方法的时候, ArrayList 会默认在将指定的元素追加到此列表的末尾,这种情况时间复杂度就是O(1)。但是如果要在指定位置 i 插入和删除元素的话( add(intindex,E element))时间复杂度就为 O(n-i)。因为在进行上述操作的时候集合中第 i 和第 i 个元素之后的(n-i)个元素都要执行向后位/向前移一位的操作。

LinkedList 采用链表存储,所以插入,删除元素时间复杂度不受元素位置的影响,都是近似 $O(1)$,而数组为近似 $O(n)$。

ArrayList 一般应用于查询较多但插入以及删除较少情况,如果插入以及删除较多则建议使用 LinkedList

是否支持快速随机访问: LinkedList 不支持高效的随机元素访问,而 ArrayList 实现了 RandomAccess 接口,所以有随机访问功能。快速随机访问就是通过元素的序号快速获取元素对象(对应于 get(intindex)方法)。

内存空间占用: ArrayList 的空间浪费主要体现在在 list 列表的结尾会预留一定的容量空间,而 LinkedList 的空间花费则体现在它的每一个元素都需要消耗比 ArrayList 更多的空间(因为要存放直接后继和直接前驱以及数据)。

高级工程师的我,可不得看看源码,具体分析下:

ArrayList工作原理其实很简单,底层是动态数组,每次创建一个 ArrayList 实例时会分配一个初始容量(没有指定初始容量的话,默认是 10),以add方法为例,如果没有指定初始容量,当执行add方法,先判断当前数组是否为空,如果为空则给保存对象的数组分配一个最小容量,默认为10。当添加大容量元素时,会先增加数组的大小,以提高添加的效率;

LinkedList 是有序并且支持元素重复的集合,底层是基于双向链表的,即每个节点既包含指向其后继的引用也包括指向其前驱的引用。链表无容量限制,但双向链表本身使用了更多空间,也需要额外的链表指针操作。按下标访问元素 get(i)/set(i,e) 要悲剧的遍历链表将指针移动到位(如果i>数组大小的一半,会从末尾移起)。插入、删除元素时修改前后节点的指针即可,但还是要遍历部分链表的指针才能移动到下标所指的位置,只有在链表两头的操作add(), addFirst(),removeLast()或用 iterator() 上的 remove() 能省掉指针的移动。此外 LinkedList 还实现了 Deque(继承自Queue接口)接口,可以当做队列使用。

不会囊括所有方法,只是为了学习,记录思想。

ArrayList 和 LinkedList 两者都实现了 List 接口

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable{ public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable 构造器

ArrayList 提供了 3 个构造器,①无参构造器 ②带初始容量构造器 ③参数为集合构造器

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable{ public ArrayList(int initialCapacity) { if (initialCapacity > 0) { // 创建初始容量的数组 this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) { this.elementData = EMPTY_ELEMENTDATA; } else { throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity); } } public ArrayList() { // 默认为空数组 this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } public ArrayList(Collection<? extends E> c) { //...} }

LinkedList 提供了 2 个构造器,因为基于链表,所以也就没有初始化大小,也没有扩容的机制,就是一直在前面或者后面插插插~~

public LinkedList() { } public LinkedList(Collection<? extends E> c) { this(); addAll(c); } // LinkedList 既然作为链表,那么肯定会有节点 private static class Node<E> { E item; Node<E> next; Node<E> prev; Node(Node<E> prev, E element, Node<E> next) { this.item = element; this.next = next; this.prev = prev; } } 插入

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/zyssfz.html