List

List接口

java.util.List extends Collection接口继承自Collection接口，是单列集合的一个重要分支，习惯性地会将实现了List接口的对象称为List集合。在List集合中允许出现重复的元素，所有的元素是以一种线性方式进行存储的，在程序中可以通过索引来访问集合中的指定元素。另外，List集合还有一个特点就是元素有序，即元素的存入顺序和取出顺序一致。

List接口的特点

有序的集合,存储元素和取出元素的顺序是一致的(存储123 取出123)
有索引,包含了一些带索引的方法
允许存储重复的元素

List接口中带索引的方法(特有)

public void add(int index, E element): 将指定的元素，添加到该集合中的指定位置上。

public void add(E element)：将指定的项目添加到滚动列表的末尾。

public E get(int index):返回集合中指定位置的元素。

public E remove(int index): 移除列表中指定位置的元素, 返回的是被移除的元素。

public E set(int index, E element):用指定元素替换集合中指定位置的元素,返回值的更新前的元素。

注意：操作索引的时候,一定要防止索引越界异常

IndexOutOfBoundsException:索引越界异常,集合会报

ArrayIndexOutOfBoundsException:数组索引越界异常

StringIndexOutOfBoundsException:字符串索引越界异常

//创建一个List集合对象,多态
List<String> list = new ArrayList<>();

//使用add方法往集合中添加元素
list.add("a");
list.add("b");
list.add("c");
list.add("d");
list.add("a");

//打印集合
System.out.println(list);//[a, b, c, d, a] 不是地址重写了toString

 
//public void add(int index, E element): 将指定的元素，添加到该集合中的指定位置上。
//在c和d之间添加一个itheima
list.add(3,"itheima");//[a, b, c, itheima, d, a]
System.out.println(list);


//public E remove(int index): 移除列表中指定位置的元素, 返回的是被移除的元素。
//移除元素
String removeE = list.remove(2);
System.out.println("被移除的元素:"+removeE);//被移除的元素:c
System.out.println(list);//[a, b, itheima, d, a]


//public E set(int index, E element):用指定元素替换集合中指定位置的元素,返回值的更新前的元素。
//把最后一个a,替换为A
String setE = list.set(4, "A");
System.out.println("被替换的元素:"+setE);//被替换的元素:a
System.out.println(list);//[a, b, itheima, d, A]

ArrayList

ArrayList implements List，ArrayList集合数据存储的结构是数组结构。元素增删慢，查找快，由于日常开发中使用最多的功能为查询数据、遍历数据，所以ArrayList是最常用的集合。数组的长度不可以发生改变，但是ArrayList集合的长度是可以随意变化的。

ArrayList 底层就是⼀个 Object[] 数组
ArrayList 底层数组默认初始化容量为 10
- jdk1.8 中 ArrayList 底层先创建⼀个长度为 0 的数组
- 当第⼀次添加元素（调用 add() 方法）时，会初始化为⼀个长度为 10 的数组
当 ArrayList 中的容量使用完之后，则需要对容量进行扩容：
- ArrayList 容量使用完后，会“自动”创建容量更⼤的数组，并将原数组中所有元素拷贝过去，这会导致效率降低
- 优化：可以使⽤构造⽅法 ArrayList (int capacity) 或ensureCapacity(int capacity) 提供⼀个初始化容量，避免刚开始就⼀直扩容，造成效率较低

优点：

向 ArrayList 末尾添加元素（add() 方法）时，效率较⾼
查询效率高

缺点：

扩容会造成效率较低（可以通过指定初始化容量，在⼀定程度上对其进⾏改善）
另外数组⽆法存储⼤数据量（因为很难找到⼀块很⼤的连续的内存空间）
向 ArrayList 中间添加元素（add(int index)），需要移动元素，效率较低

常用方法

public boolean add(E e)：向集合当中添加元素，参数的类型和泛型一致。返回值代表添加是否成功。

备注：对于ArrayList集合来说，add添加动作一定是成功的，所以返回值可用可不用。

public E get(int index)：从集合当中获取元素，参数是索引编号，返回值就是对应位置的元素。

public E remove(int index)：从集合当中删除元素，参数是索引编号，返回值就是被删除掉的元素。

public int size()：获取集合的尺寸长度，返回值是集合中包含的元素个数。

public Object[] toArray() 按适当顺序（从第一个到最后一个元素）返回包含此列表中所有元素的数组。

public < T> T[] toArray(T[] a) 返回数组的运行时类型是指定数组的运行时类型。如果指定的数组能容纳列表，则将该列表返回此处。否则，将分配一个具有指定数组的运行时类型和此列表大小的新数组。

注意事项：

对于ArrayList集合来说，直接打印得到的不是地址值，而是内容，因为重写了toString方法。

如果内容是空，得到的是空的中括号：[]

public static void main(String[] args) {
    // 创建了一个ArrayList集合，集合的名称是list，里面装的全都是String字符串类型的数据
    // 备注：从JDK 1.7+开始，右侧的尖括号内部可以不写内容，但是<>本身还是要写的。
    ArrayList< String> list = new ArrayList<>();
    System.out.println(list); // []
    // 向集合当中添加一些数据，需要用到add方法。
    list.add("赵丽颖");
    System.out.println(list); // [赵丽颖]
    list.add("迪丽热巴");
    list.add("古力娜扎");
    list.add("玛尔扎哈");
    System.out.println(list); // [赵丽颖, 迪丽热巴, 古力娜扎, 玛尔扎哈]
    //list.add(100); // 错误写法！因为创建的时候尖括号泛型已经说了是字符串，添加进去的元素就必须都是字符串才行

  }

ArrayList 和 Array（数组）的区别？

ArrayList 内部基于动态数组实现，比 Array（静态数组）使用起来更加灵活：

ArrayList会根据实际存储的元素动态地扩容或缩容，而 Array 被创建之后就不能改变它的长度了。
ArrayList 允许你使用泛型来确保类型安全，Array 则不可以。
ArrayList 中只能存储对象。对于基本类型数据，需要使用其对应的包装类（如 Integer、Double 等）。Array 可以直接存储基本类型数据，也可以存储对象。
ArrayList 支持插入、删除、遍历等常见操作，并且提供了丰富的 API 操作方法，比如 add()、remove()等。Array 只是一个固定长度的数组，只能按照下标访问其中的元素，不具备动态添加、删除元素的能力。
ArrayList创建时不需要指定大小，而Array创建时必须指定大小。

ArrayList的扩容机制

ArrayList在jdk7.0的时候，创建容器的时候会在底层创建一个长度为10的object数组，在jdk8.0的时候，在创建容器的时候底层并不会立刻创建，只有在第一次调用add方法的时候才会创建一个长度为10的数组，当然也可以通过构造函数的方式给自定义初始化的容量

扩容策略：ArrayList 的扩容策略是每次扩容为当前容量的 1.5 倍。这意味着，当内部数组满了之后，ArrayList 会创建一个新的更大容量的数组，并将原数组中的元素复制到新数组中

复制元素：在进行扩容时，ArrayList 会调用 Arrays.copyOf() 方法来创建新的数组，并将原数组中的元素复制到新数组中

Arrays.copyOf()方法

  public static int[] copyOf(int[] original, int newLength) {
    // 申请一个新的数组
      int[] copy = new int[newLength];
// 调用System.arraycopy,将源数组中的数据进行拷贝,并返回新的数组
      System.arraycopy(original, 0, copy, 0,
                       Math.min(original.length, newLength));
      return copy;
  }

copyOf()内部实际调用了 System.arraycopy() 方法

LinkedList

java.util.LinkedList集合数据存储的结构是链表结构。方便元素添加、删除的集合

LinkedList是一个双向链表LinkedList是List的子类，List中的方法LinkedList都是可以使用，这里就不做详细介绍，我们只需要了解LinkedList的特有方法即可。在开发时，LinkedList集合也可以作为堆栈，队列的结构使用。

实际开发中对一个集合元素的添加与删除经常涉及到首尾操作，而LinkedList提供了大量首尾操作的方法。

常用方法

public void addFirst(E e)：将指定元素插入此列表的开头。

public void addLast(E e)：将指定元素添加到此列表的结尾。

public E getFirst()：返回此列表的第一个元素。

public E getLast()：返回此列表的最后一个元素。

public E removeFirst()：移除并返回此列表的第一个元素。

public E removeLast()：移除并返回此列表的最后一个元素。

public E pop()：从此列表所表示的堆栈处弹出一个元素。

public void push(E e)：将元素推入此列表所表示的堆栈。

public boolean isEmpty()：如果列表不包含元素，则返回true。

public class LinkedListDemo {
  public static void main(String[] args) {
    LinkedList<String> link = new LinkedList<String>();
    //添加元素
    link.addFirst("abc1");
    link.addFirst("abc2");
    link.addFirst("abc3");
    System.out.println(link);

    // 获取元素
    System.out.println(link.getFirst());
    System.out.println(link.getLast());
    
    // 删除元素
    System.out.println(link.removeFirst());
    System.out.println(link.removeLast());

    while (!link.isEmpty()) { //判断集合是否为空
      System.out.println(link.pop()); //弹出集合中的栈顶元素
    }
    System.out.println(link);
  }
}

LinkedList 为什么不能实现 RandomAccess 接口？

RandomAccess 是一个标记接口，用来表明实现该接口的类支持随机访问（即可以通过索引快速访问元素）。由于 LinkedList 底层数据结构是链表，内存地址不连续，只能通过指针来定位，不支持随机快速访问，所以不能实现 RandomAccess 接口。

在 binarySearch（) 方法中，它要判断传入的 list 是否 RandomAccess 的实例，如果是，调用indexedBinarySearch()方法，如果不是，那么调用iteratorBinarySearch()方法

ArrayList 与 LinkedList 区别?

是否保证线程安全： ArrayList 和 LinkedList 都是不同步的，也就是不保证线程安全；
底层数据结构： ArrayList 底层使用的是 Object 数组；LinkedList 底层使用的是 双向链表 数据结构（JDK1.6 之前为循环链表，JDK1.7 取消了循环。注意双向链表和双向循环链表的区别，下面有介绍到！）
插入和删除是否受元素位置的影响：
- ArrayList 采用数组存储，所以插入和删除元素的时间复杂度受元素位置的影响。比如：执行add(E e)方法的时候， ArrayList 会默认在将指定的元素追加到此列表的末尾，这种情况时间复杂度就是 O(1)。但是如果要在指定位置 i 插入和删除元素的话（add(int index, E element)），时间复杂度就为 O(n)。因为在进行上述操作的时候集合中第 i 和第 i 个元素之后的(n-i)个元素都要执行向后位/向前移一位的操作。
- LinkedList 采用链表存储，所以在头尾插入或者删除元素不受元素位置的影响（add(E e)、addFirst(E e)、addLast(E e)、removeFirst()、 removeLast()），时间复杂度为 O(1)，如果是要在指定位置 i 插入和删除元素的话（add(int index, E element)，remove(Object o),remove(int index)），时间复杂度为 O(n) ，因为需要先移动到指定位置再插入和删除。

是否支持快速随机访问： LinkedList 不支持高效的随机元素访问，而 ArrayList（实现了 RandomAccess 接口）支持。快速随机访问就是通过元素的序号快速获取元素对象(对应于get(int index)方法)。

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

注意：我们在项目中一般是不会使用到 LinkedList 的，需要用到 LinkedList 的场景几乎都可以使用 ArrayList 来代替，并且，性能通常会更好！就连 LinkedList 的作者约书亚 · 布洛克（Josh Bloch）自己都说从来不会使用 LinkedList 。

另外，不要下意识地认为 LinkedList 作为链表就最适合元素增删的场景。我在上面也说了，**LinkedList 仅仅在头尾插入或者删除元素的时候时间复杂度近似 O(1)，其他情况增删元素的平均时间复杂度都是 O(n) 。**

Vector

Vector implements List

Vector 底层是数组，初始化容量为 10
扩容：原容量使用完后，会进行扩容。新容量扩大为原始容量的 2 倍
Vector 是线程安全的（里面方法都带有 synchronized 关键字），效率较低，现在使用较少

ArrayList 和 Vector 的区别?（了解即可）
ArrayList 是 List 的主要实现类，底层使用 Object[]存储，适用于频繁的查找工作，线程不安全。
Vector 是 List 的古老实现类，底层使用Object[] 存储，线程安全。

如何将 ArrayList 变成线程安全的？

调用 Collections 工具类中的 static List synchronizedList(List list) 方法

Stack

Stack extend Vector implements List

Vector是List接口的一个实现类，而Stack是Vector的一个子类，它实现了一个标准的后进先出的栈。堆栈只定义了默认构造函数，用来创建一个空栈。堆栈除了包括由Vector定义的所有方法，也定义了自己的一些方法。

常用方法

boolean empty()：测试堆栈是否为空。

E peek()：查看堆栈顶部的对象，但不从堆栈中移除它。

E pop()：移除堆栈顶部的对象，并作为此函数的值返回该对象。

E push(E item)：把项压入堆栈顶部。

int search(Object o)：返回对象在堆栈中的位置，以 1 为基数。

Vector 和 Stack 的区别?（了解即可）

Vector 和 Stack 两者都是线程安全的，都是使用 synchronized 关键字进行同步处理。
Stack 继承自 Vector，是一个后进先出的栈，而 Vector 是一个列表。

随着 Java 并发编程的发展，Vector 和 Stack 已经被淘汰，推荐使用并发集合类（例如 ConcurrentHashMap、CopyOnWriteArrayList 等）或者手动实现线程安全的方法来提供安全的多线程操作支持。

Java > Java集合

#Java

List

http://example.com/2023/05/13/Java/Java集合/3. List/

作者

PALE13

发布于

2023年5月13日

许可协议

Set 上一篇

Queue 下一篇