List集合-蒲公英云

List是Java集合框架中最常用的集合类型之一，它允许我们存储有序的元素集合，通过索引可以轻松访问和操作这些元素。 List是一个接口，Java提供了多个实现List接口的类，如ArrayList、LinkedList和Vector等。在本文中，我们将详细讨论List集合和它的子类，从浅入深介绍这些子类的特点、应用场景和底层实现原理。

一、List集合的基本概念

List集合介绍

List是一个接口，它继承自Collection接口。 List表示的是一个元素有序的集合，可以根据插入顺序或其他某个规则来存储元素。 List还提供了访问下标、添加、删除、查询等常规操作。这些操作受到集合的大小、容量、对内存的影响等多个因素的影响，因此我们需要在使用时选择具体的子类。

List的底层实现可以是数组或链表。对于数组实现的List，元素的插入和删除是相对耗时的操作，因为需要进行数组的移位操作。而对于链表实现的List，插入和删除则可以达到O(1)的时间复杂度。

List集合

List集合内置方法

1. add(E e)

public boolean add(E e)

添加元素到List集合末尾。

示例代码：

List<String> list = new ArrayList<>();
list.add("A");
list.add("B");
list.add("C");
System.out.println(list); // 输出 [A, B, C]

2. add(int index, E element)

public void add(int index, E element)

在指定位置插入元素。

示例代码：

List<String> list = new ArrayList<>();
list.add(1, "A");
list.add("B");
list.add(0, "C");
System.out.println(list); // 输出 [C, A, B]

3. get(int index)

public E get(int index)

获取指定位置的元素。

示例代码：

List<String> list = new ArrayList<>();
list.add("A");
list.add("B");
String element = list.get(0);
System.out.println(element); // 输出 A

4. set(int index, E element)

public E set(int index, E element)

修改指定位置的元素。

示例代码：

List<String> list = new ArrayList<>();
list.add("A");
list.add("B");
list.set(0, "C");
System.out.println(list); // 输出 [C, B]

5. remove(int index)

public E remove(int index)

删除指定位置的元素。

示例代码：

List<String> list = new ArrayList<>();
list.add("A");
list.add("B");
list.remove(0);
System.out.println(list); // 输出 [B]

6. size()

public int size()

获取List集合中元素的个数。

示例代码：

List<String> list = new ArrayList<>();
list.add("A");
list.add("B");
int size = list.size();
System.out.println(size); // 输出 2

7. indexOf(Object o)

public int indexOf(Object o)

查找元素在List集合中第一次出现的位置。如果没有找到，则返回-1。

示例代码：

List<String> list = new ArrayList<>();
list.add("A");
list.add("B");
int index = list.indexOf("B");
System.out.println(index); // 输出 1

8. lastIndexOf(Object o)

public int lastIndexOf(Object o)

查找元素在List集合中最后一次出现的位置。如果没有找到，则返回-1。

示例代码：

List<String> list = new ArrayList<>();
list.add("A");
list.add("B");
list.add("A");
int index = list.lastIndexOf("A");
System.out.println(index); // 输出 2

9. subList(int fromIndex, int toIndex)

public List<E> subList(int fromIndex, int toIndex)

获取List集合中指定范围内的子集合。

示例代码：

List<String> list = new ArrayList<>();
list.add("A");
list.add("B");
list.add("C");
List<String> subList = list.subList(1, 3);
System.out.println(subList); // 输出 [B, C]

10. clear()

public void clear()

清空List集合中的所有元素。

示例代码：

List<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.clear();
System.out.println(list); // 输出 []

11. isEmpty()

public boolean isEmpty()

判断List集合是否为空。

示例代码：

List<Integer> list1 = new ArrayList<>();
List<Integer> list2 = new ArrayList<>();
System.out.println(list1.isEmpty()); // 输出 true
System.out.println(list2.isEmpty()); // 输出 true

12. contains(Object o)

public boolean contains(Object o)

判断List集合中是否包含指定元素。

示例代码：

List<String> list = new ArrayList<>();
list.add("A");
list.add("B");
System.out.println(list.contains("B")); // 输出 true
System.out.println(list.contains("C")); // 输出 false

13. toArray()

public Object[] toArray()

将List集合转换成数组。

示例代码：

List<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
Object[] arr = list.toArray();
System.out.println(Arrays.toString(arr)); // 输出 [1, 2]

14. toArray(T[] a)

public <T> T[] toArray(T[] a)

将List集合转换成指定类型的数组。

示例代码：

List<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
Integer[] arr = new Integer[2];
Integer[] result = list.toArray(arr);
System.out.println(Arrays.toString(result)); // 输出 [1, 2]

15. addAll(Collection<? extends E> c)

public boolean addAll(Collection<? extends E> c)

将另一个Collection集合中的所有元素添加到List集合末尾。

示例代码：

ArrayList<String> list1 = new ArrayList<>();
list1.add("A");
list1.add("B");
ArrayList<String> list2 = new ArrayList<>();
list2.add("C");
list2.add("D");
list1.addAll(list2);
System.out.println(list1); // 输出 [A, B, C, D]

16. addAll(int index, Collection<? extends E> c)

public boolean addAll(int index, Collection<? extends E> c)

将另一个Collection集合中的所有元素插入到List集合中的指定位置。

示例代码：

ArrayList<String> list1 = new ArrayList<>();
list1.add("A");
list1.add("B");
ArrayList<String> list2 = new ArrayList<>();
list2.add("C");
list2.add("D");
list1.addAll(1, list2);
System.out.println(list1); // 输出 [A, C, D, B]

除了以上方法，List集合还可以使用iterator()方法返回一个迭代器，支持遍历访问所有元素，并且可以使用ListIterator来实现遍历和修改List集合的操作。

List集合下方法

二、ArrayList

ArrayList是List接口的一个实现类。它使用数组来实现元素的存储，支持快速随机访问。 ArrayList是线程不安全的，如果需要在多线程环境下操作，则应该使用线程安全的Vector或者提供了同步机制的ArrayList，称为Synchronized ArrayList。

1、ArrayList的特点

数据以数组形式存储，数据的添加和删除速度较慢；
能够随机访问某个位置的元素，可以通过数组下标来访问元素；
支持快速插入，插入一个元素只需要将需要插入的元素插入到指定的下标即可。若需要在中间位置插入，则会移动后面所有元素一个单位；
可以根据元素内容快速查询其在List中的位置；
遍历ArrayList的速度较快；
存储元素时不需要考虑空间问题，因为ArrayList的容量是动态扩展的。

2、ArrayList的适用场景

强调随机访问与遍历，适用于需要快速访问和遍历所有元素的场景；
可以根据元素位置快速访问，适用于需要随机访问某个位置元素的场景；
元素的内容较为复杂或对象较大，避免使用LinkedList的引用传递操作。

3、ArrayList的底层实现

ArrayList使用数组实现元素的存储和访问。当ArrayList中的元素数量超出容量时，它会新建一个容量更大的数组，并将原来的数组中的元素复制到新的数组中，然后释放老数组。在ArrayList中插入元素时，如果插入的位置不在ArrayList底层数组中，则需要调整数组大小，而在数组末尾插入元素或删除元素性能较好。因此，在ArrayList中频繁的插入和删除元素时，那么效率较低。

ArrayList底层实现

ArrayList底层使用数组实现，其扩容和添加、修改、删除数据的底层代码如下：

1. 扩容：

当ArrayList的数组长度不够时，需要对数组进行扩容。代码如下：

private void ensureCapacity(int minCapacity) {
        // 获取当前数组长度
    int oldCapacity = elementData.length;
        // 如果需要扩容
    if (minCapacity > oldCapacity) {
        // 新的容量为原来的1.5倍+1
        int newCapacity = (oldCapacity * 3) / 2 + 1;
        // 如果新容量仍然小于所需容量，则直接使用所需容量
        if (newCapacity < minCapacity)
            newCapacity = minCapacity;
        // 复制原数组到新数组中
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
}

2. 添加数据：

在ArrayList中添加数据时，需要先判断是否需要扩容，然后将元素添加到数组末尾。代码如下：

public boolean add(E e) {
    // 判断是否需要扩容
    ensureCapacity(size + 1);
    // 将元素添加到数组末尾
    elementData[size++] = e;
    return true;
}

3. 修改数据：

在ArrayList中修改数据时，直接在指定位置上修改即可。代码如下：

public E set(int index, E element) {
    // 检查索引是否越界
    rangeCheck(index);
    // 获取旧值
    E oldValue = elementData(index);
    // 在指定位置上修改元素
    elementData[index] = element;
    // 返回旧值
    return oldValue;
}

4. 删除数据：

在ArrayList中删除数据时，需要先将要删除的元素覆盖掉，然后将后面的元素向前移动。代码如下：

public E remove(int index) {
    // 检查索引是否越界
    rangeCheck(index);
    // 获取旧值
    E oldValue = elementData(index);
    // 覆盖要删除的元素
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index + 1, elementData, index,
                numMoved);
    // 将最后一个元素设为null，便于垃圾回收
    elementData[--size] = null;
    return oldValue;
}

总结：ArrayList底层使用数组实现，扩容和添加、修改、删除数据的底层代码主要涉及数组长度的修改、元素的添加、修改和删除等操作。使用数组实现可以快速地访问数组中的元素，但是也存在数组长度固定、扩容时需要重新分配数组等缺点。

4、ArrayList的方法

add(E e): 将元素e添加到ArrayList的末尾。
add(int index, E element): 将元素element添加到指定的index位置。
addAll(Collection<? extends E> c): 将集合c中的所有元素添加到ArrayList的末尾。
addAll(int index, Collection<? extends E> c): 将集合c中的所有元素添加到指定的index位置。
clear(): 清空ArrayList中的所有元素。
clone(): 复制ArrayList并返回一个新的ArrayList对象。
contains(Object o): 判断ArrayList中是否包含元素o。
ensureCapacity(int minCapacity): 增加ArrayList的容量，使其能够容纳minCapacity个元素。
get(int index): 返回指定index的元素。
indexOf(Object o): 返回元素o在ArrayList中第一次出现的位置。
isEmpty(): 判断ArrayList是否为空。
iterator(): 返回ArrayList中元素的迭代器。
lastIndexOf(Object o): 返回元素o在ArrayList中最后出现的位置。
remove(int index): 删除指定index位置的元素。
remove(Object o): 删除ArrayList中第一个出现的元素o。
removeAll(Collection<?> c): 删除ArrayList中包含在集合c中的所有元素。
retainAll(Collection<?> c): 保留ArrayList中与集合c中相同的所有元素。
set(int index, E element): 将指定index位置的元素替换为element。
size(): 返回ArrayList中元素的数量。
subList(int fromIndex, int toIndex): 返回ArrayList中从fromIndex到toIndex位置的子列表。
toArray(): 将ArrayList转换为一个数组，并返回该数组。
toArray(T[] a): 将ArrayList转换为一个数组，并返回该数组。如果指定的数组a足够大，则将元素存入a中，否则创建一个新的数组来存储元素。

三、LinkedList

LinkedList是List接口的另一个实现类，它使用链表来实现元素存储。相对于ArrayList，LinkedList对于元素的添加和删除操作比较快。

1、LinkedList的特点

数据以链表形式存储，因此支持快速添加和删除元素；
不支持随机访问元素，只能通过指针遍历链表；
可以在链表的任意一端添加和删除元素；
根据元素内容查询其在链表中的位置速度较慢；
存储元素时需要考虑空间问题，因为LinkedList会为每一个元素生成一个Node对象。

2、LinkedList的适用场景

需要频繁地添加、删除元素，并且不需要快速随机访问元素的场景；
存储元素数量不大，不会占用过多的空间；
原始数据类型较小或元素内容较简单，可以直接使用Object存储。

3、LinkedList的底层实现

LinkedList底层使用双向链表实现，每个节点都包含前驱节点和后继节点。插入元素时，需要调整前驱节点和后继节点指针，删除元素时也需要修改前驱节点和后继节点指针。LinkedList也允许我们通过指针遍历链表，即从头节点或尾节点往后或往前遍历。

LinkedList底层添加数据，修改数据和删除数据的代码如下：

添加数据：

//在添加数据时，首先会创建一个新节点，然后将该节点链接到链表的末尾。如果链表为空，则将该节点作为链表的头节点(first)，否则将该节点作为链表的尾节点(last)的后继节点(next)。

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++;
}

修改数据：

//在修改数据时，首先会检查给定的索引是否合法，然后获取该索引对应节点(Node)的item值(即原来的数据)，将其替换为新的数据(element)，最后返回原来的数据。
```
public E set(int index, E element) {
    checkElementIndex(index);
    Node<E> x = node(index);
    E oldVal = x.item;
    x.item = element;
    return oldVal;
}
```

删除数据：

//在删除数据时，首先会检查给定的索引是否合法，然后获取该索引对应节点(Node)的item值(即要删除的数据)，然后将该节点从链表中断开，使它的前驱节点(prev)指向它的后继节点(next)，同时它的后继节点(next)指向它的前驱节点(prev)。如果该节点是头节点，则将它的后继节点作为新的头节点(first)，如果该节点是尾节点，则将它的前驱节点作为新的尾节点(last)。最后将该节点的item值设置为null，缩小链表的size，返回被删除的数据。

public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}
E unlink(Node<E> x) {
    // assert x != null;
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;
    if (prev == null) {
        first = next;
    } else {
        prev.next = next;
        x.prev = null;
    }
    if (next == null) {
        last = prev;
    } else {
        next.prev = prev;
        x.next = null;
    }
    x.item = null;
    size--;
    return element;
}

4、LinkedList的方法

add(E e)：向链表尾部添加元素e。时间复杂度为O(1)。
add(int index, E element)：在指定位置插入元素element。时间复杂度为O(n)。
addFirst(E e)：在链表头部插入元素e。时间复杂度为O(1)。
addLast(E e)：在链表尾部插入元素e。时间复杂度为O(1)。
clear()：清空链表中的所有元素。
get(int index)：获取指定位置的元素。时间复杂度为O(n)。
getFirst()：获取链表头部的元素。时间复杂度为O(1)。
getLast()：获取链表尾部的元素。时间复杂度为O(1)。
indexOf(Object o)：返回指定元素o在链表中第一次出现的位置。时间复杂度为O(n)。
remove()：删除链表头部的元素。时间复杂度为O(1)。
remove(int index)：删除指定位置的元素。时间复杂度为O(n)。
removeFirst()：删除链表头部的元素。时间复杂度为O(1)。
removeLast()：删除链表尾部的元素。时间复杂度为O(1)。
set(int index, E element)：将指定位置的元素替换为element。时间复杂度为O(n)。
size()：获取链表中元素的个数。
Object[] toArray(): 将LinkedList转换成一个Object类型的数组返回。
<T> T[] toArray(T[] a): 将LinkedList转换成一个指定类型的数组返回。
boolean add(E e): 将元素e添加到LinkedList的末尾。
void add(int index, E element): 将元素element添加到LinkedList的index位置。
boolean addAll(Collection<? extends E> c): 将集合c中的所有元素添加到LinkedList的末尾。
boolean addAll(int index, Collection<? extends E> c): 将集合c中的所有元素添加到LinkedList的index位置。
void clear(): 删除LinkedList中的所有元素。
boolean contains(Object o): 判断LinkedList中是否包含元素o。
Iterator<E> descendingIterator(): 返回一个逆序遍历的Iterator。
E element(): 返回LinkedList的第一个元素。
E get(int index): 返回LinkedList中指定位置的元素。
int indexOf(Object o): 返回LinkedList中第一次出现元素o的位置。
boolean isEmpty(): 判断LinkedList是否为空。
Iterator<E> iterator(): 返回一个正序遍历的Iterator。
int lastIndexOf(Object o): 返回LinkedList中最后一次出现元素o的位置。
ListIterator<E> listIterator(): 返回一个正序遍历的ListIterator。
ListIterator<E> listIterator(int index): 返回一个从指定位置开始正序遍历的ListIterator。
E peek(): 返回LinkedList的第一个元素，如果LinkedList为空则返回null。
E peekFirst(): 返回LinkedList的第一个元素，如果LinkedList为空则抛出NoSuchElementException异常。
E peekLast(): 返回LinkedList的最后一个元素，如果LinkedList为空则返回null。
E poll(): 删除并返回LinkedList的第一个元素，如果LinkedList为空则返回null。
E pollFirst(): 删除并返回LinkedList的第一个元素，如果LinkedList为空则抛出NoSuchElementException异常。
E pollLast(): 删除并返回LinkedList的最后一个元素，如果LinkedList为空则返回null。
void push(E e): 将元素e压入LinkedList的头部。
E pop(): 删除并返回LinkedList的头部元素。
E remove(): 删除并返回LinkedList的第一个元素，如果LinkedList为空则抛出NoSuchElementException异常。
E remove(int index): 删除并返回LinkedList中指定位置的元素。
boolean remove(Object o): 删除LinkedList中第一次出现的元素o。
boolean removeAll(Collection<?> c): 删除LinkedList中所有属于集合c的元素。
boolean retainAll(Collection<?> c): 保留LinkedList中属于集合c的元素，删除其他元素。
E set(int index, E element): 将LinkedList中指定位置的元素替换为element。
int size(): 返回LinkedList中包含的元素个数。
List<E> subList(int fromIndex, int toIndex): 返回一个从fromIndex到toIndex之间的子List。
boolean linkBefore(Object[] src, int srcPos, int srcEnd, int dstIndex): 将src数组中从srcPos到srcEnd之间的元素插入到LinkedList中dstIndex位置之前。

50.Node<E> node(int index)：获取指定位置的节点。

代码实现如下：

private Node<E> node(int index) {
// 判断index是否越界
    if (index < 0 || index >= size) {
        throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
    }
// 如果index小于size的一半，从头部开始遍历
    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
// 如果index大于等于size的一半，从尾部开始遍历
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

void linkBefore(E e, Node<E> succ)：在指定节点前插入元素e。代码实现如下：

private void linkBefore(E e, Node succ) {

// 获取succ的前驱节点
```
final Node<E> pred = succ.prev;
```
// 创建一个新节点
```
final Node<E> newNode = new Node<>(pred, e, succ);
```
// 将新节点插入到succ和pred之间
```
succ.prev = newNode;
if (pred == null)
    first = newNode;
else
    pred.next = newNode;
size++;
modCount++;
```
}

E unlink(Node<E> x)：删除指定节点x。代码实现如下：

private E unlink(Node x) {

// 获取x的前驱节点和后继节点

final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;

// 将prev和next连接

if (prev == null) {
    first = next;
} else {
    prev.next = next;
    x.prev = null;
}
if (next == null) {
    last = prev;
} else {
    next.prev = prev;
    x.next = null;
}
x.item = null;
size--;
modCount++;
return element;

}

四、Vector

Vector是List接口的另一个实现类，通过Vector可以实现线程安全的集合操作。但是，由于Vector在同步时使用了synchronized关键字，因此它的性能比ArrayList要低。

1、Vector的特点

数据以数组形式存储；
可以随机访问某个位置的元素，可以通过数组下标来访问元素；
支持快速插入，插入一个元素只需要将需要插入的元素插入到指定的下标即可。若需要在中间位置插入，则会移动后面所有元素一个单位；
可以根据元素内容快速查询其在List中的位置；
遍历Vector的速度较快；
在多线程的情况下，支持线程安全。

2、Vector的适用场景

适用于需要多线程操作的场景，实现线程安全的操作；
需要快速访问指定位置的元素，适用于需要随机访问元素的场景；
避免在Vector中插入、删除元素，因为这样会导致ArrayList数据重新分配空间的问题。

3、Vector的底层实现

Vector和ArrayList比较相似，不同于ArrayList，Vector在每个本地方法调用时使用了synchronized关键字来保证多线程访问的线程安全性。在其他方面，Vector与ArrayList大致相同。

4、Vector下方法

add(Object o):将一个对象添加到Vector的尾部，并返回true。
add(int index, Object o):将一个对象插入到指定位置，并返回true。
addAll(Collection c):将一个集合中的所有元素添加到Vector的尾部，并返回true。
addAll(int index, Collection c):将一个集合中的所有元素插入到指定位置，并返回true。
clear():清空Vector中的所有元素，并返回void。
clone():创建Vector的副本，并返回Object。
contains(Object o):判断Vector中是否包含指定的元素，并返回boolean。
containsAll(Collection c):判断Vector中是否包含指定集合中的所有元素，并返回boolean。
copyInto(Object[] anArray):将Vector中的元素复制到指定的数组中，并返回void。
elementAt(int index):返回指定位置的元素。
elements():返回一个枚举器，用于遍历Vector中的元素。
ensureCapacity(int minCapacity):确保Vector的容量至少是指定值，并返回void。
equals(Object o):比较Vector与指定对象是否相等。
firstElement():返回Vector中的第一个元素。
get(int index):返回指定位置的元素。
hashCode():返回Vector的哈希码值。
indexOf(Object o):返回指定元素在Vector中第一次出现的位置。
indexOf(Object o, int index):返回指定元素在Vector中从指定位置开始第一次出现的位置。
insertElementAt(Object o, int index):将一个元素插入到指定位置，并返回void。
isEmpty():判断Vector是否为空。
lastElement():返回Vector中的最后一个元素。
lastIndexOf(Object o):返回指定元素在Vector中最后一次出现的位置。
lastIndexOf(Object o, int index):返回指定元素在Vector中从指定位置开始最后一次出现的位置。
remove(int index):删除指定位置的元素，并返回被删除的元素。
remove(Object o):删除指定的元素，并返回boolean。
removeAll(Collection c):删除所有在指定集合中出现的元素，并返回boolean。
removeElement(Object o):删除指定的元素，并返回void。
removeElementAt(int index):删除指定位置的元素，并返回void。
retainAll(Collection c):将Vector中不在指定集合中出现的元素全部删除，并返回boolean。
set(int index, Object o):将指定位置的元素设置为指定值，并返回被替换的元素。
setElementAt(Object o, int index):将指定位置的元素设置为指定值，并返回void。
setSize(int newSize):设置Vector的大小，若新大小比原大小小，则删除后面的元素；若新大小比原大小大，则用null补齐，并返回void。
size():返回Vector中元素的个数。
subList(int fromIndex, int toIndex):返回包含指定范围内的元素的列表。
toArray():将Vector中的元素复制到一个数组中，并返回Object[]。
toArray(T[] a):将Vector中的元素复制到指定类型的数组中，并返回T[]。