My Blog

记录 JavaSE 中集合框架之 List 家族

学习笔记，仅供参考

参考：B站Mirco_Frank - java 进阶 | 官网教程 | JDK-9 API | javatpoint 教程-可供练习

目录

• Colletion

• List, Queue, Set

• ArrayList

• LinkedList

• Vector

• Stack

• 小结

由于传统的数组在增删改查和扩容等功能上很难操作，所以为了弥补这些功能，Java 中就有了集合框架。它使用起来更加方便，也不用去深究那些细节上的问题。在 API 中属于 java.util.Collections 包

🚄 Colletion

贵人暂且不提，先说家族的创始人 Colletion 接口，Collection 代表着一群的对象，类似于数组，每个对象也被称作 元素。有的集合允许有重复的元素，有的则不允许；有的集合是有顺序的，有的则是无序的。既然 Collection 接口是家族老大，那自然就不会亲自出马办事，都是交给手下来办。所以就有了子接口 List, Queue, Set 这些当家的，当家的也不会随便出手，于是就交给它的 实现类 们来办理家族上下事。

老大当然也不是吃闲饭的，为了能让家族更好的运转，它要制定一些规矩(Colletion 的方法)，底下的小弟(实现类)都要遵守。下面简单列举一些，具体的到实现类的时候在详细说明

方法

• add(E e)   // 确保集合包含此元素（有则可加可不加，无则加）

• clear()   // 清除集合中所有的元素

• contains(Object o)   // 判断集合中是否含有此元素，true 有；false 无

• equals(Object o)   // 比较指定对象与此集合是否相等

• hashCode()   // 返回此集合的 hashcode 值

• isEmpty()   // 判断此集合是否为空

• iterator()   // 重写 Iterable 的，遍历集合的所有元素，并返回

• remove(Object o)   // 从集合中删除指定的元素，若其存在

• size()   // 返回当前集合中元素的数量

• toArray()   // 返回一个包含集合所有元素的数组

🔌 List, Queue, Set

介绍完老大，接着简述一下三个当家的，它们分别是 List, Queue, Set 。它们分别代表着集合的三种不同的类型，列表、队列、集合，下面依次说明

List 是有顺序的集合，可以通过下标来访问或查询集合中的元素。它也运行有重复的元素，允许有空元素(null)，所以它不擅长实现非重复元素的特性。它也制定了一些方法来让操作数据更加的方便高效，具体的实现类有：ArrayList、LikedList、Stack、Vector

Queue 是用来处理之前所保存元素的集合，一般情况下是先进先出(FIFO)的规则来处理数据，但有时候也可以根据特定的需求来处理。具体的实现类有：PriorityQueue、Deque、ArrayDeque

Set 是无序、不重复的集合，正如其名，它就像是对数学上的集合的抽象表示。每个 Set 至多只能存放一个空值。具体实现类：HashSet、LikedHashSet、TreeSet

💡 ArrayList

ArrayList 是家族中的其中一个管事的(实现类)，是属于大当家(List)下的。

优缺点

优点：作为传统数组的加强版，它更加的灵活，没有大小的限制能够自动的扩容；随时地增删元素；直接通过下标就能查找到元素；允许有重复、空元素

缺点：增删改元素需要遍历才能完成操作；在多线程中，它的实例是不同步的

底层原理

ArrayList 的底层也是用原始的数组构成的，所以它与传统的数组类似。但它能够自动扩容，一种简单的实现是内部新建个容量更大数组，然后将原来的元素搬过去，再让数组名引用新的数组即实现扩容。由于是数组实现，所以查找指定下标的元素就十分快。但插入和删除元素时，则要将指定下标后面的元素挨个搬迁十分麻烦

构造器

• ArrayList()   // 构造一个空列表，并初始化容量为 10

• ArrayList(int initialCapacity)   // 构造一个空列表，并指定其容量

方法

• add(E e)   // 在列表尾部追加所给的元素

• add(int index, E e)   // 在表的指定下标位置插入所给数据，但所给下标不可超过表的大小，否则抛出下标越界异常

  // 新建 ArrayList 对象，泛型指定为 String 类型
  ArrayList<String> list = new ArrayList<>();
  
  // 添加元素
  list.add("Frank");  // 集合尾部追加所给元素
  list.add("Tom");
  
  list.add(1, "Jerry");  // 指定下标插入数据
  list.add(2, "Mike");
  
  list.add(5, "Puck");  // 指定的下标超过 size - 1，抛出 IndexOutOfBoundsException
  list.add(100);  // 插入元素非 String 类型，编译报错
  
  // 因为有泛型，所以它也能添加对象作为元素
  
  /**
  *  编写 Student类
  */
  public class Student {
  private String name;
  private int age;
  
  public Student(String name, int age) {
      this.name = name;
      this.age = age;
  }
  
  public String toString() {
      return "\n$ name: " + this.name
              + "| age: " + this.age + " $";
  }
  }
  
  // 在 ArrayList 集合中插入 Student 对象
  ArrayList<Student> studentList = new ArrayList<>();
  
  studentList.add(new Student("Tom", 12));
  studentList.add(new Student("Jerry", 13));
  studentList.add(0, new Student("Frank", 18));
  // 打印集合直接输出即可，会自动调用它的 toString 方法
  System.out.println(studentList);
  
  /* 
  print result: 
  [
  $ name: Frank| age: 18 $, 
  $ name: Tom| age: 13 $, 
  $ name: Jerry| age: 14 $]
  */

• addAll(Collection<? extends E> c)   // 将所给集合的所有元素追加到该集合的尾部

• addAll(int index, Collection<? extends E> c)   // 将所给集合的所有元素插入到该集合指定的下标

  // 对于不同的类型则不允许合并集合
  ArrayList<Integer> list1 = new ArrayList<>();
  ArrayList<Integer> list2 = new ArrayList<>();
  
  list1.add(1);
  list1.add(2);
  
  list2.add(8);
  list2.add(9);
  
  list1.addAll(list2);
  list2.addAll(1, list2);
  
  System.out.println(list1);
  System.out.println(list2);
  
  /*
  print result: 
  list1: [1, 2, 8, 9]
  list2: [8, 8, 9, 9]
  */

• toArray()   // 从头到尾复制该集合中的元素，将元素放到 Object[] 中，并返回

  // insert elements
  list.add(1); list.add(2); list.add(3); list.add(4);
  // convert to array
  Object[] arr = list.toArray();
  // for-each 遍历数组
  for (Object value : arr) {
  System.out.println(value + ", ");
  }
  // for-i 遍历操作
  for (int i = 0; i < arr.length; i++) {
  System.out.println(((int) arr[i] + 1) + ", ");
  }
  
  /*
  print result:
  1, 2, 3, 4, 
  2, 3, 4, 5, 
  */

• clear()   // 清空集合中所有元素

  // insert elements
  list.add(1); list.add(2); list.add(3); list.add(4);
  System.out.println(list);
  // clear list
  list.clear();
  System.out.println(list);
  
  /*
  print result: 
  [1, 2, 3, 4]
  []
  */

• clone()   // 克隆该集合并返回

• contains(Object o)   // 判断集合中是否有指定的元素，有 true；无 false

  // insert elements
  list.add(1); list.add(2); list.add(3); list.add(4);
  System.out.println(list.contains(1));
  System.out.println(list.contains(5));
  
  /*
  print result: 
  true
  false
  */

• size()   // 返回该集合的容量（即含有元素的个数）

• get(int index)   // 获取集合中指定下标的元素, 若下标超过 size - 1，则抛出下标越界异常

  // insert elements
  list.add(1); list.add(2); list.add(3); list.add(4);
  System.out.println("size: " + list.size());
  System.out.println("the element of specified index : " + list.get(1));
  System.out.println("the element of specified index : " + list.get(5));
  
  /*
  print result: 
  size: 4
  the element of specified index : 2
  throws IndexOutOfBoundsException
  */

• indexOf(Object o)   // 返回指定元素的下标，多个重复的，只返回从头到尾的第一个的 index

• lastIndexOf(Object o)   // 与 indexOf 类似，它是从尾到头的第一个的 index

• isEmpty()   // 判断集合是否为空，空 true；非空 false

  ArrayList<Integer> list = new ArrayList<>();
  ArrayList<Integer> listEmpty = new ArrayList<>();
  // insert elements
  list.add(1); list.add(2); list.add(1); list.add(4);
  
  System.out.println(list.indexOf(1));
  System.out.println(list.lastIndexOf(1));
  System.out.println(list.isEmpty());
  System.out.println(listEmpty.isEmpty());
  
  /*
  print result: 
  0
  2
  false
  true
  */

• remove(int index)   // 删除集合中指定下标的元素

• remove(Object o)   // 从头到尾顺序，删除集合中与所给值相同的的第一个元素

• removeAll(Collection<?> c)   // 删除该集合与所给集合的交集元素

• retainALl(Collection<?> c)   // 保留该集合与所给集合的交集元素，即删除那些交集之外的元素

  // 假设 list1 为 [1, 2, 1, 4]
  //     list2 为 [1] 
  list1.remove(1);  // 根据元素删除，list1: [2, 1, 4]
  list1.remove(1);  // 根据下标删除，list1: [1, 1, 4]
  list1.removeAll(list2);  // list1: [2, 4]
  list1.retainAll(list2);  // list1: [1, 1]
  
  // ★ 注意：当ArrayList 的元素类型为 Integer 时，再调用 remove() 方法，它默认会以下标删除为准，但可以通过 Integer 自动装箱将参数转为对象，如：list1.remove((Integer) 1), 这样就是根据对象删除
  

• replaceAll(UnaryOperator<E> operator)   // 根据所给的操作来替换集合中每个元素

  // 该方法涉及到泛型和接口等知识，暂时无法理解，仅知道简单的用法
  
  // 假设 list 集合中元素为 ["Red", "Green", "Blue"]
  list.replaceAll( e -> "White" );  // list: ["White", "White", "White"]
  
  // 假设 list 集合中元素为 [1, 2, 3]
  list.replaceAll( e -> e + 10 );  // list: [11, 12, 13]
  
  // 利用 lambda 表达式，将集合的每个元素都做了变换的操作
  

• set(int index, E e)   // 将集合中指定的下标元素替换为所给的元素

• Collections.sort()   // 对所给的集合进行排序，数字按大小排序，字母按 A-Z 顺序排序

• Collections.reverseOrder()   // 对集合进行降序排列

  // ★ 由于 ArrayList 自带的 sort 方法涉及到泛型、接口，所以使用 Collections.sort() 更加方便 
  
  // 假设 list 为 ["Tom", "Frank", "Mike", "Rose"]
  Collections.sort(list);  // list: ["Frank", "Mike", "Rose", "Tom"]
  
  // 假设 list 为 [2, 4, 1, 3]
  Collections.sort(list);  // list: [1, 2, 3, 4]
  Collections.sort(list, Collections.reverseOrder());  // list: [4, 3, 2, 1]
  

• subList​(int fromIndex, int toIndex)   // 返回从 fromIndex 下标开始，取 (toIndex - fromIndex) 个元素的子集合，相当于数学上的[fromIndex, toIndex)

  // 假设 list 为 ["A", "B", "C", "D", "E", "F", "G"]
  list.subList(2, 5);  // list: ["C", "D", "E"]
  

• trimToSize​()   // 将该集合的容量裁剪至当前的大小, ★ 注意 ArrayList 没有获取集合容量的方法

🔗 LinkedList

LinkedList 是 List 接口的又一个实现类，它与 ArrayList 不同的是，它是基于 双向链表 的形式来构成的集合

优缺点

优点 ：增删数据方便，不像 ArrayList 得一个个的搬迁；允许有重复的元素；也可用来作堆栈、队列

缺点 ：查询数据较麻烦，要经过遍历才能找到指定位置的数据；多线程中不同步

底层实现

LinkedList 是基于双向链表的形式实现的，所以它要有前驱引用、后驱引用（类似指针）和数据位。增删数据时只需改动引用即可实现插入和删除操作。但查询数据时可能要从某个节点开始遍历，直到找到符合的元素将其返回

构造器

• LinkedList()   // 构建一个空集合

• LinkedList(Collection<? extends E> c)   // 构建一个集合，且包含所给集合的元素

方法

• add(E e)   // 在集合尾部追加元素

• add(int index, E e)   // 在集合的指定下标插入元素

• addAll(Collection<? extends E> c)   // 在该集合的尾部追加所给集合的所有元素，重载方法多了 index 指定下标处添加

• addFirst(E e)   // 在集合开头插入指定元素

• addLast(E e)   // 在集合结尾插入指定元素

  // 创建 LinkedList 集合
  LinkedList<String> list = new LinkedList<>();
  LinkedList<String> listAll = new LinkedList<>();
  
  list.add("Tom");  // list: ["Tom"]
  list.add("Jerry");  // list: ["Tom", "Jerry"]
  list.add(0, "Frank");  // list: ["Frank", "Tom", "Jerry"]
  
  listAll.add("Alan");  // listAll: ["Alan"]
  list.addAll(listAll);  // 结尾追加，list: ["Frank", "Tom", "Jerry", "Alan"]
  list.addAll(0, listAll);  // 指定下标添加，list: ["Alan", "Frank", "Tom", "Jerry"]
  
  list.addFirst("First");  // list: ["First", "Frank", "Tom", "Jerry"]
  list.addLast("Last");  // list: [ "Frank", "Tom", "Jerry", "Last"]
  

• clear()   // 清空集合

• clone()   // 返回一个复制的 LinkedList 集合

• contains(Object o)   // 判断该集合是否含有所给的元素，有 true；无 false

• element()   // 返回但不删除集合的首元素，空集合则抛出 NoSuchElementException

• get(int index)   // 获取集合中指定下标元素

• getFirst()   // 获取集合首元素

• getLast()   // 获取集合尾元素

  // 假设 list 为: [1, 2, 3, 4, 5]
  list.element();  // return: 1
  list.get(3);  // return: 4
  list.getFirst();  // return: 1
  lsit.getLast();  // return: 5
  

• indexOf(Object o)   // 从头到尾的顺序，返回集合中第一个与所给元素相同的元素下标，没有则返回 -1

• lastIndexOf(Object o)   // 从尾到头的顺序，返回集合中第一个与所给元素相同的元素下标，没有则返回 -1

  // 假设 list 为 [1, 3, 2, 1, 4]
  lsit.indexOf(1);  // return: 0
  list.lastIndexOf(1);  // return: 3
  list.indexOf(9);  // return: -1
  

• offer(E e)   // 将所给元素添加到该集合的尾部

• offerFirst(E e)   // 将所给元素插入到该集合的开头

• offerLast(E e)   // 将所给元素插入到该集合的末尾

• peek(E e)   // 获取但不删除该集合的首元素，若集合为空则返回 null

• peekFirst(E e)   // 获取但不删除该集合的首元素，若集合为空则返回 null

• peekLast(E e)   // 获取但不删除该集合的尾元素，若集合为空则返回 null

• poll(E e)   // 获取且删除该集合的首元素，若集合为空则返回 null

• pollFirst(E e)   // 获取且删除该集合的首元素，若集合为空则返回 null

• pollLast(E e)   // 获取且删除该集合的尾元素，若集合为空则返回 null

  // 假设 list 为 ["Tom", "Jerry"]
  //   listEmpty 为 []
  list.offer("Frank");  // list: ["Tom", "Jerry", "Frnak"]
  list.offerFirst("First");  // list: ["First", "Tom", "Jerry"]
  list.offerLast("Last");  // list: ["Tom", "Jerry", "Last"]
  
  list.peek();  // return: Tom
  listEmpty.peek();  // return: null
  list.peekFirst();  // return: Tom
  list.peekLast();  // return: Jerry
  listEmpty.peekFirst();  // return: null
  
  list.poll();  // return: Tom, list: ["Jerry"]
  list.pollFirst();  // return: Tom, list: ["Jerry"]
  list.pollLast();  // return: Jerry, list: ["Tom"]
  listEmpty.poll();  // return: null
  
  // ★ 由前面 LinkedList 的继承图就能看出，
  //    LinkedList 还是 Queue 的实现类，
  //    所以它也具备 Queue 的进队出队 (offer, peek, poll) 方法
  //    即遵循 FIFO(First Input First Output) 原则
  

• pop()   // 从给集合表示的堆栈中弹出一个元素，即返回并删除该集合的首元素

• push(E e)   // 从给集合表示的堆栈中压入一个元素，即插入所给元素到该集合的首位

  // suppose list is [1, 2, 3]
  list.pop();  // return: 1, list: [2, 3]
  list.push(10);  // list: [10, 1, 2, 3]
  
  // 所以 LinkedList 当堆栈用时，
  // 是集合的开头当栈顶，末尾当栈底
  

• remove()   // 返回并删除该集合的首元素

• remove(int index)   // 删除该集合中所给下标的元素

• remove(Object o)   // 从头到尾顺序，删除该集合第一个与所给对象相同的元素，若存在的话，返回 true 表示删除成功

• removeFirst()   // 返回并删除该集合的首元素

• removeFirstOccurrence​(Object o)   // 从头到尾顺序，删除该集合第一个与所给对象相同的元素

• removeLast()   // 返回并删除该集合的尾元素

• removeLastOccurrence​(Object o)   // 从头到尾顺序，删除该集合最后一个与所给对象相同的元素

  // 假设 list 为 ["Tom", "Jerry", "Frank", "Tom", "Tom"]
  list.remove();  // return: Tom, list: ["Jerry", "Frank", "Tom", "Tom"]
  list.remove(2);  // return: Frank, list: ["Tom", "Jerry", "Tom", "Tom"]
  list.remove("Tom");  // return: true, list: ["Jerry", "Frank", "Tom", "Tom"]
  list.removeFirst();  // return: Tom, list: ["Jerry", "Frank", "Tom", "Tom"]
  list.removeFirstOccurrence("Tom");  // return: true, list: ["Jerry", "Frank", "Tom", "Tom"]
  list.removeLast();  // return: Tom, list: ["Tom", "Jerry", "Frank", "Tom"]
  list.removeLastOccurrence("Tom");  // return: true, list: ["Tom", "Jerry", "Frank", "Tom"]
  
  // 与 ArrayList 一样，若存的为整数，要用类型转换，否则默认调用的为下标的方法
  

• set(int index, E e)   // 用所给的元素替换该集合所给下标的元素

• size()   // 返回该集合含有元素的数量

• toArray()   // 将集合中的元素从头到尾到复制到 Object[] 中，并将其返回

🔪 Vector

前两个是比较常用的，Vector 和 Stack 会用的相对较少，所以简要记录。首先，Vector 类也是 List 的实现类，也是类似一种动态数组，能根据需求增减元素且没有大小限制。其次，它也是通过下标来访问其元素。最后，与前两个不同的是，它是线程同步的。所以能适合在多线程中保证线程安全，而不需要线程安全时，可用 ArrayList 来代替。

根据网上一些表述，此类由于保证同步而性能上不高，它的同步是因为给每个方法都加了 synchronized 。还有就是可能出的比较早，后续有更好的类取代了它

具体的方法参考 Vector-API ，下面列举一些相对独特的方法

构造器与方法

• Vector​()   // 构建一个空向量，初始容量为 10，容量递增为 0

• Vector(int initialCapacity)   // 构建一个空向量，并指定初始容量，容量递增为 0

• capacity()   // 返回该向量的当前容量

• setSize​(int newSize)   // 设置该向量的大小

📚 Stack

栈作为一种数据结构，所具有的特点就是 LIFO(Last Input Frist Output) ，常用的就是它的进栈和出栈

构造器与方法

• Stack()   // 创建一个空栈

• empty()   // 判断该栈是否为空

• peek()   // 查看但不删除栈顶元素

• pop()   // 弹出并返回栈顶元素

• push(E e)   // 将所给元素压入栈顶

• search(Object o)   // 搜索所给元素在栈中的位置，并将该位置返回; 没有则返回 -1

  // create stack collection
  Stack<String> stack = new Stack<>();
  stack.empty();  // return: true;
  stack.push("Tom");
  stack.push("Jerry");
  stack.push("Frank");  // stack: ["Tom", "Jerry", "Frank"]
  
  stack.peek();  // return: Frank, stack: ["Tom", "Jerry", "Frank"]
  stack.pop();  // return: Frank, stack: ["Tom", "Jerry"]
  stack.search("Tom");  // return: 2, start from stack top, 1 2 3 ...
  stack.search("Fuck");  // return: -1, not found given element
  
  // print stack, fianl result: ["Tom", "Jerry"]
  System.out.println(stack);

Stack 对象除了上述的方法外，也能使用 List 的方法来处理数据，即 add, remove 等

小结

Java 中通常用 ArrayList 来代替传统的数组，而 LinkedList 的又能当队列和栈使用，所以它俩是重点。下面用表格的形式对比两者的特点