基本介绍
还记得我们的java集合框架吗, 我们来复习一下, 如图:
可以看出来 ArrayList和LinkedList 都是具体类, 他们都是接口List的实现类.
但是他们底层的逻辑是不同的, 相信学过这个的应该大概有个映像吧, 如下图:
可以看出来, ArrayList是向内存申请一块连续的数组空间进行存储, 在数组的存储形式的基础上进行链表的增删改查, 而LinkedList则是每次添加元素的时候就向系统申请一块内存, 不用就直接释放, 他们虽然在内存上不是连续的, 但是在逻辑上他们是连在一起的.
有什么不同??
- 底层实现不同, ArrayList是基于动态数组的数据结构, 而LInkedLIst是基于双向链表的数据结构
- 随机访问的性能不同, Arraylist的随机访问性能是由于LinkedList的, 因为ArrayList可以根据下标来直接访问, 类似于数组, 时间复杂度为O(1), 但是LinkedList的随机访问时间复杂度为O(n), 因为他需要遍历整个链表才能找到指定的元素
- 插入和删除不同, 对于插入和删除, LInkedList要明显由于ArrayList, 因为LInkedList的掺入和删除操作时间复杂度为O(1), 例如插入, 我们可以直接在链表的头部进行插入或者是通过一个元素来记录最后一个结点的位置, 然后直接在最后一个结点进行尾插, 删除是相同的操作, 因此时间复杂度为O(1), 但是对于ArrayList就不同了, ArrayList的插入和删除需要移动插入位置的元素的后面的所有元素, 最坏的情况需要移动ArrayList的所有元素, 因此时间复杂度为O(n)
但是需要注意的是, 其实他们插入的平均时间复杂度是一样的, 接下来我们来探讨一下, 他们两个的平均时间复杂度:
- 对于ArrayList的插入的平均时间复杂度, 它想要插入一个数字, 虽然是直接指定插入的地方, 也就是他的一个随机插入的性质, 但是它还需要对后面的元素进行一个挪动, 运气不好的话, 就需要挪动整个数组, 时间复杂度最坏的情况下是O(n), 最坏的情况下是O(1), 平均下来就是O(n/2), 我们去掉系数, 也就是O(n)
- 对于LinkedList来说, 他进行插入, 需要遍历链表,从头到尾遍历, 好的情况就是在头的时候就便利到了, 时间复杂度为O(1), 坏的情况下需要遍历完整个链表, 时间复杂度最坏的情况就是O(n),平均下来就是O(n/2) ,去掉系数就是O(n)
所以对于我们真是运用链表的场景, 没有说他们两个哪个时间复杂度, 或者是性能更好, 只能是在不同的情况下适应不同的场景.
小结:
ArrayList 和 LinkedList 都是 List 接口的实现类，但它们的底层实现（结构）不同、随机访问的性能和添加/删除的效率不同。如果是随机访问比较多的业务场景可以选择使用 ArrayList，如果添加和删除比较多的业务场景可以选择使用 LinkedList。
ArrayList适用于需要快速随机访问元素的场景，因为它的底层是基于数组实现的，可以通过下标直接访问元素。但是，当需要频繁插入或删除元素时，由于需要移动元素，效率较低。
LinkedList适用于需要频繁插入或删除元素的场景，因为它的底层是基于链表实现的，插入或删除元素只需要改变指针指向，效率较高。但是，当需要随机访问元素时，由于需要遍历链表，效率较低。
因此，根据具体的场景需求，选择合适的集合类可以提高程序的效率。
ArrayList的扩容机制
我们首先创建一个ArrayList如图:
import java.util.ArrayList; import java.util.LinkedList; import java.util.List; public class Test { public static void main(String[] args) { List<Integer> arrayList = new ArrayList<>(); // 第0步:创建基于链表的List arrayList.add(1); // 1 添加元素 arrayList.add(2); // 2 添加元素 arrayList.add(3); // 3 添加元素 arrayList.add(4); // 4 添加元素 arrayList.add(5); // 5 添加元素 arrayList.add(6); // 6 添加元素 arrayList.add(7); // 7 添加元素 arrayList.add(8); // 8 添加元素 arrayList.add(9); // 9 添加元素 System.out.println("hello"); // 打印 } }
第0步, 初始化:
ArrayList的构造方法如下:
/** * Constructs an empty list with the specified initial capacity. * * @param initialCapacity the initial capacity of the list * @throws IllegalArgumentException if the specified initial capacity * is negative */ 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); } } /** * Constructs an empty list with an initial capacity of ten. */ public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } /** * Constructs a list containing the elements of the specified * collection, in the order they are returned by the collection's * iterator. * * @param c the collection whose elements are to be placed into this list * @throws NullPointerException if the specified collection is null */ public ArrayList(Collection<? extends E> c) { elementData = c.toArray(); if ((size = elementData.length) != 0) { // c.toArray might (incorrectly) not return Object[] (see 6260652) if (elementData.getClass() != Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); } else { // replace with empty array. this.elementData = EMPTY_ELEMENTDATA; } }
里面有三个重载的构造方法, 简单来说就是:
- 无参构造: Obeject数组elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
- 给定初始容量: ①当 传入的初始容量initialCapacity > 0为真时，创建一个大小为initialCapacity的空数组，并将引用赋给elementData；
②当 传入的初始容量initialCapacity = 0为真时，将空数组EMPTY_ELEMENTDATA赋给elementData；
③当 传入的初始容量initialCapacity < 0为真时，直接抛出IllegalArgumentException异常。
此处我们传入的initialCapacity为空, 也就是无参构造方法, 如下:
transient Object[] elementData; private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; }
在构造方法中，它将DEFAULTCAPACITY_EMPTY_ELEMENTDATA赋值给elementData，这个DEFAULTCAPACITY_EMPTY_ELEMENTDATA是一个空的Object数组，而elementData就是ArrayList实际存储数据的容器。
第1步, 添加元素1:
触发:
public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; }
ensureCapacityInternal为确认初始化容量:
进入ensureCapacityInternal:
private void ensureCapacityInternal(int minCapacity) { ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); }
随后进入calculateCapacity计算最低所需容量:
private static int calculateCapacity(Object[] elementData, int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { return Math.max(DEFAULT_CAPACITY, minCapacity); } return minCapacity; }
此处的minCapacity为 size + 1, 翻译过来也就是最低所需的容量, 研究发现, 如果是空数组(刚开始使用无参构造方法的时候)就返回DEFAULT_CAPACITY, 值为10.
当elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的时候, 直接返回minCapacity.
随后进入ensureExplicitCapacity(int minCapacity)方法:
private void ensureExplicitCapacity(int minCapacity) { modCount++; // overflow-conscious code if (minCapacity - elementData.length > 0) grow(minCapacity); }
modCount++，这是用来记录数组被修改次数的变量，我们先不管它. minCapacity为计算出来的最小所需容量, elementData.length为当前容量,如果最小所需容量大于当前容量, 就需要扩容, 然后进入grow方法:
private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1); if (newCapacity - minCapacity < 0) newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity); }
老的容量为当前容量,新的容量为老的容量的1.5倍,如果新的容量–最小所需容量<О那么新的容量就等于最小所需容量,如果新的容量-当前数组最大的容量限制>0,那么就进入hugeCapacity方法,然后使用copyOf方法进行数据迁移.将老的数据迁移到新的容量的数组中
总结一下:
我们使用无参构造方法的时候, 就会创建一个底层为空的数组的链表, 此时size 为0, 然后向里面添加元素的时候, 此时的minCapacity为 size + 1 = 1, 在calculateCapacity方法中返回了DEFAULT_CAPACITY(10), 然后进入ensureExplicitCapacity(10), 此时的minCapacity = 10 > 当前容量 = 0, 所以进行初始扩容(elementData = Arrays.copyOf(elementData, newCapacity)), 将容量扩充到10, 也就是elementData/length == 10, 随后的插入, 只要没有超过10, 那就可以直接插入, 如果容量满了, 那么就进行1.5倍扩容.
ArrayLIst的基本使用
import java.util.ArrayList; import java.util.LinkedList; import java.util.List; public class Test { public static void main(String[] args) { ArrayList<Integer> arrayList = new ArrayList<>(); // 第0步:创建基于链表的List // add(int x) 直接向元素末尾位置添加x arrayList.add(1); // get(int index) 方法, 返回下标为index的元素 int a = arrayList.get(0); System.out.println(a); // add(int index, int element); 向指定位置插入元素 arrayList.add(1,3); // size(); 获取当前元素的个数 int size = arrayList.size(); // remove(int index); 删除下标为index 的元素 arrayList.remove(0); // 判断arrList是否为空, 如果为空就返回true, 否则返回false; arrayList.isEmpty(); // set(int index, int element); 将index 下标的元素设置为 element arrayList.set(0,5); } }
LInkedList与之类似
ArrayList和Vector
ArrayList和Vector都实现了List接口. 代码演示如图:
import java.util.ArrayList; import java.util.Vector; public class Main { public static void main(String[] args) { ArrayList<String> arrayList = new ArrayList<>(); Vector<String> vector = new Vector<>(); // 添加元素 arrayList.add("Java"); arrayList.add("Python"); arrayList.add("C++"); vector.add("Java"); vector.add("Python"); vector.add("C++"); // 获取元素 System.out.println(arrayList.get(0)); System.out.println(vector.get(0)); // 删除元素 arrayList.remove(0); vector.remove(0); // 获取元素个数 System.out.println(arrayList.size()); System.out.println(vector.size()); } }
但它们有以下区别：
- 线程安全性：Vector 是线程安全的，而 ArrayList 不是。所以在多线程环境下，应该使用 Vector。
- 性能：由于 Vector 是线程安全的，所以它的性能通常比 ArrayList 差。在单线程环境下，ArrayList 比 Vector 快。
- 初始容量增长方式：当容量不足时，ArrayList 默认会增加 50% 的容量，而 Vector 会将容量翻倍。这意味着在添加元素时，ArrayList 需要更频繁地进行扩容操作，而 Vector 则更适合于存储大量数据。
Vector的grow方法
综上所述，如果不需要考虑线程安全问题，并且需要高效的存取操作，则 ArrayList 是更好的选择；如果需要考虑线程安全以及更好的数据存储能力，则应该选择 Vector。
