文章目录

前言一、List是什么？二、常用方法三、ArrayList1.简介2.ArrayList构造器3.添加元素（扩容机制） LinkedList1、简介2、添加元素

---

前言

刷LeetCode的时候用了List，用得少已经有些恍惚了。所以今天整理一下List接口还有它的一些实现类，加深理解。 （以下内容基于JDK1.8）

一、List是什么？

List接口是Collection的子接口，实现一种线性表的数据结构。存放在List中的所有元素都有一个下标（从0开始），可以通过下标访问List中的元素。同时，List中可以包含重复元素。

二、常用方法

List接口除继承Collection的方法之外，还定义了一些自己的方法。使用这些方法可以实现定位访问、查找、迭代和返回子线性表。

Collection常用的方法如下： boolean add(E e):向集合中添加元素e； boolean remove(E e)：向集合中删除指定元素o； boolean contains（E e）：返回集合中是否包含指定的元素e； boolean isEmpty（）：返回集合是否为空； int size（）：返回集合的大小（元素个数）； 还有一些批量操作和数组操作的常见方法，可参见API。

---

List的常用方法如下： E get（int index）： 返回指定下标的处的元素； E set（int index）： 设置指定下标出的元素； void add（int index, E element）:将指定元素插入到指定下标处； E remove（int index）：删除指定下标处的元素； abstract boolean addAll（int index，Collection <? extends E> c）:在指定下标处插入集合c中的全部元素；

三、ArrayList

1.简介

ArrayList是最常用的线性表实现类，通过数组实现的集合对象。ArrayList类实际上实现了一个变长的对象数组，其元素可以动态增加和删除。它的定位访问时间是常量时间。

2.ArrayList构造器

无参构造下的默认容量是10，也可以使用带容量的参数构造。

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() { //DEFAULTCAPACITY_EMPTY_ELEMENTDATA = 10 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; } }

3.添加元素（扩容机制）

ArrayList类中的add()方法代码：

/** * Appends the specified element to the end of this list. * * @param e element to be appended to this list * @return <tt>true</tt> (as specified by {@link Collection#add}) */ public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; }

其中的elementData是存储元素的数组：

/** * The array buffer into which the elements of the ArrayList are stored. * The capacity of the ArrayList is the length of this array buffer. Any * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA * will be expanded to DEFAULT_CAPACITY when the first element is added. */ transient Object[] elementData; // non-private to simplify nested class access

分析add()引用的方法：ensureCapacityInternal(int minCapacity)

//此时minCapacity=size+1 private void ensureCapacityInternal(int minCapacity) { ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); }

ArrayList类中的calculateCapacity()方法代码：

//如果list为空，则返回默认值（10）和minCapacity的最大值；否则返回minCapacity private static int calculateCapacity(Object[] elementData, int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { return Math.max(DEFAULT_CAPACITY, minCapacity); } return minCapacity; }

ArrayList类中的ensureExplicitCapacity()方法代码：

private void ensureExplicitCapacity(int minCapacity) { modCount++; //初始值为0 // overflow-conscious code if (minCapacity - elementData.length > 0) //当容量不足的时候，使用grow函数进行扩容 grow(minCapacity); }

新容量 = 旧容量 + 0.5倍旧容量，也就是扩容1.5倍 ArrayList类中的grow()方法代码：

private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; //新容量 = 旧容量 + 0.5倍旧容量，也就是扩容1.5倍 int newCapacity = oldCapacity + (oldCapacity >> 1); if (newCapacity - minCapacity < 0) newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) //如果新容量超过了最大容量值，则调用hugeCapacity进行扩容 newCapacity = hugeCapacity(minCapacity); // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity); }

如果超过最大容量值，就是用Integer的最大值，否则使用设置的最大容量值 ArrayList类中的hugeCapacity()方法代码：

private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // overflow throw new OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; }

---

LinkedList

1、简介

LinkedList也实现了List接口（也实现了Deque，Cloneable，Serializable，即支持队列，克隆和可序列化），相对于ArrayList来说，它们的最大区别在于底层数据结构不同，LinkedList的底层是一个双向链表，这也决定了它的最大优点，那就是对于数据的修改比ArrayList更加方便快捷。相对于ArrayList，LinkedList插入是更快的。因为LinkedList不需要改变数组的大小，也不需要在数组装满的时候要将所有的数据重新装入一个新的数组，类似于插入数据，删除数据时，LinkedList也优于ArrayList，其时间复杂度仅为O(1)，而ArrayList删除数据是开销很大的，因为这需要重排数组中的数据。

2、添加元素

add（）无参方法这里默认尾插

public boolean add(E e) { linkLast(e); return true; } void linkLast(E e) { final Node<E> l = last; final Node<E> newNode = new Node<>(l, e, null); last = newNode; if (l == null) first = newNode; else l.next = newNode; size++; modCount++; }

也可以指定头插和尾插：

public void addFirst(E e) { linkFirst(e); } private void linkFirst(E e) { final Node<E> f = first; final Node<E> newNode = new Node<>(null, e, f); first = newNode; if (f == null) last = newNode; else f.prev = newNode; size++; modCount++; } public void addLast(E e) { linkLast(e); } /** * Links e as last element. */ void linkLast(E e) { final Node<E> l = last; final Node<E> newNode = new Node<>(l, e, null); last = newNode; if (l == null) first = newNode; else l.next = newNode; size++; modCount++; }