• 第十四章 集合（集合框架体系、List）

    一、集合框架体系

    （1）可以动态保存任意多个对象
    （2）提供了一系列方便的操作对象的方法：add、remove、set、get 等

    集合框架体系：

    二、Collection

    1. Collection 接口常用方法

    （1）add：添加单个元素

    （2）remove：删除指定元素

    （3）contains：查找元素是否存在

    （4）size：获取元素个数

    （5）isEmpty：判断是否为空

    （6）clear：清空

    （7）addAll：添加多个元素

    （8）containsAIl：查找多个元素是否都存在

    （9）removeAll：删除多个元素

    2. Collection 接口遍历元素方式1，使用 Iterator（迭代器）

    （1）Iterator 对象称为迭代器，主要用于遍历 Collection 集合中的元素。
    （2）所有实现了 Collection 接口 的集合类都有一个 iterator() 方法，用以返口一个实现了Iterator 接口的对象，即可以返回一个迭代器。
    （3）Iterator 仅用于遍历集合，lterator 本身并不存放对象。

    1. public class Test {
    2.  
    3.     public static void main(String[] args) {
    4.         ArrayList list = new ArrayList<>();
    5.         list.add(1);
    6.         list.add(2);
    7.         list.add(3);
    8.  
    9.         // list.iterator() 重置迭代器，可重复
    10.         Iterator iterator = list.iterator();
    11.         while (iterator.hasNext()) {
    12.             Integer next = iterator.next();
    13.             System.out.println(next);
    14.         }
    15.     }
    16. }

    3. Collection 接口遍历元素方式2，增强 for 循环

    增强 for 循环，可以代替 iterator 迭代器，特点：增强 for 本质就是迭代器。只能用于遍历集合或数组。

    1. public class Test {
    2.  
    3.     public static void main(String[] args) {
    4.         ArrayList list = new ArrayList<>();
    5.         list.add(1);
    6.         list.add(2);
    7.         list.add(3);
    8.  
    9.         for (Integer e : list) {
    10.             System.out.println(e);
    11.         }
    12.     }
    13. }

    三、List

    1. List 接口基本介绍

    （1）List 接口是 Collection 接口的子接口

    （2）List 集合类中元素有序（即添加顺序和取出顺序一致）、且可重复

    （3）List 集合中的每个元素都有其对应的顺序索引，即支持索引。

    （4）List 容器中的元素都对应一个整数型的序号记载其在容器中的位置，可以根据序号存取容器中的元素

    2. List 集合里添加了一些根据索引来操作集合元素的方法

    （1）void add (int index, Object ele）：在 index 位置插入 ele 元素

    （2）boolean addAll (int index, Collection eles)：从 index 位置开始将 eles 中的所有元素添加进来

    （3）Object get (int index)：获取指定 index 位置的元素

    （4）int indexOf (Object obj)：返回 obj 在集合中首次出现的位置

    （5）int lastlndexOf (Object obj)：返回 obj 在当前集合中末次出现的位置

    （6）Object remove (int index)：移除指定 index 位置的元素，并返回此元素

    （7）Object set (int index, Object ele)：设置指定 index 位置的元素为 ele，相当于是替换

    （8）List subList (int fromlndex，int tolndex)：返回从 fromlndex 到（tolndex -1）位置的子集合

    1. public class Test {
    2.  
    3.     public static void main(String[] args) {
    4.         List list = new ArrayList<>();
    5.         list.add("乔峰");
    6.         list.add("段誉");
    7.         list.add(1, "虚竹");
    8.         list.add("Tom");
    9.         System.out.println(list); // [乔峰, 虚竹, 段誉, Tom]
    10.  
    11.         List list2 = new ArrayList<>();
    12.         list2.add("Jack");
    13.         list2.add("Tom");
    14.         list.addAll(1, list2);
    15.         System.out.println(list); // [乔峰, Jack, Tom, 虚竹, 段誉, Tom]
    16.  
    17.         System.out.println(list.get(1)); // Jack
    18.         System.out.println(list.indexOf("Tom")); // 2
    19.         System.out.println(list.lastIndexOf("Tom")); // 5
    20.  
    21.         list.remove(5);
    22.         System.out.println(list); // [乔峰, Jack, Tom, 虚竹, 段誉]
    23.         list.set(2, "Mike");
    24.         System.out.println(list); // [乔峰, Jack, Mike, 虚竹, 段誉]
    25.         System.out.println(list.subList(0, 2)); // [乔峰, Jack]
    26.     }
    27. }

    四、ArrayList（P509） 

    1. ArrayList 的注意事项

    （1）ArrayList 可以加入 null，并且多个。

    （2）ArrayList 是由数组来实现数据存储的。

    （3）ArrayList 基本等同于 Vector。ArrayList 是线程不安全（执行效率高），在多线程情况下，不建议使用ArrayList。

    2. ArrayList 的底层操作机制源码分析（P510）

    （1）ArrayList 中维护了一个 Object 类型的数组，transient Object[] elementData【transient  表示该属性不会被序列化】

    （2）当创建 ArrayList  对象时，如果使用的是无参构造器，则初始 elementData 容量为 0。

    第一次添加，则扩容 elementData 为 10。如果需要再次扩容的话，则扩容 elementData 为1.5 倍。

    （3）如果使用的是指定大小的构造器，则初始 elementData 容量为指定大小，如果需要扩容，则直接扩容 elementData 为1.5倍。

    1. public class ArrayList_ {
    2.  
    3.     transient Object[] elementData;
    4.  
    5.     private int size;
    6.  
    7.     protected transient int modCount = 0;
    8.  
    9.     private static final int DEFAULT_CAPACITY = 10;
    10.  
    11.     private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    12.  
    13.     // 无参构造
    14.     public ArrayList_() {
    15.         // 创建一个空的数组
    16.         this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    17.     }
    18.  
    19.     public ArrayList_(int initialCapacity) {
    20.         if (initialCapacity > 0) {
    21.             this.elementData = new Object[initialCapacity];
    22.         } 
    23.     }
    24.  
    25.     public boolean add(E e) {
    26.         ensureCapacityInternal(size + 1);  // Increments modCount!!
    27.         // 在 elementData[size] 赋值，并且size++
    28.         elementData[size++] = e;
    29.         return true;
    30.     }
    31.  
    32.     private void ensureCapacityInternal(int minCapacity) {
    33.         ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    34.     }
    35.  
    36.     private void ensureExplicitCapacity(int minCapacity) {
    37.         // 操作次数
    38.         modCount++;
    39.  
    40.         // overflow-conscious code
    41.         // 判断是否扩容，如果elementData数组大小不够就扩容
    42.         if (minCapacity - elementData.length > 0){
    43.             grow(minCapacity);
    44.         }
    45.  
    46.     }
    47.  
    48.     private static int calculateCapacity(Object[] elementData, int minCapacity) {
    49.         if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
    50.             return Math.max(DEFAULT_CAPACITY, minCapacity);
    51.         }
    52.         return minCapacity;
    53.     }
    54.  
    55.     private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    56.  
    57.     // 扩容方法
    58.     private void grow(int minCapacity) {
    59.         // overflow-conscious code
    60.         int oldCapacity = elementData.length;
    61.         // 扩容为1.5倍
    62.         int newCapacity = oldCapacity + (oldCapacity >> 1);
    63.         if (newCapacity - minCapacity < 0){
    64.             newCapacity = minCapacity;
    65.         }
    66.         // 防止超过最大值2147483639
    67.         if (newCapacity - MAX_ARRAY_SIZE > 0){
    68.             newCapacity = hugeCapacity(minCapacity);
    69.         }
    70.         // minCapacity is usually close to size, so this is a win:
    71.         // Arrays.copyOf 可以保留原先的数据，并扩容
    72.         elementData = Arrays.copyOf(elementData, newCapacity);
    73.     }
    74.  
    75.     private static int hugeCapacity(int minCapacity) {
    76.         if (minCapacity < 0){
    77.             // overflow
    78.             throw new OutOfMemoryError();
    79.         }
    80.         return (minCapacity > MAX_ARRAY_SIZE) ?
    81.                 Integer.MAX_VALUE :
    82.                 MAX_ARRAY_SIZE;
    83.     }
    84. }

    五、Vector（P513）

    1. Vector 的基本介绍

    （1）Vector 类的定义说明

    1. public class Vector
    2.     extends AbstractList
    3.     implements List, RandomAccess, Cloneable, java.io.Serializable

    （2）Vector 底层也是一个对象数组 protected Object[] elementData;

    （3）Vector 是线程同步的，即线程安全，Vector 类的操作方法带有 synchronized。

    （4）在开发中，需要线程同步安全时，考虑使用 Vector。

    2. Vector 的底层操作机制源码分析

    Vector 扩容源码类似于 ArrayList

    1. public class Vector_ {
    2.  
    3.     protected Object[] elementData;
    4.  
    5.     protected int capacityIncrement;
    6.  
    7.     protected transient int modCount = 0;
    8.  
    9.     protected int elementCount;
    10.  
    11.     public Vector_() {
    12.         this(10);
    13.     }
    14.  
    15.     public Vector_(int initialCapacity) {
    16.         this(initialCapacity, 0);
    17.     }
    18.  
    19.     public Vector_(int initialCapacity, int capacityIncrement) {
    20.         super();
    21.         if (initialCapacity < 0){
    22.             throw new IllegalArgumentException("Illegal Capacity: "+
    23.                     initialCapacity);
    24.         }
    25.         // 初始化数组
    26.         this.elementData = new Object[initialCapacity];
    27.         this.capacityIncrement = capacityIncrement;
    28.     }
    29.  
    30.     public synchronized boolean add(E e) {
    31.         modCount++;
    32.         ensureCapacityHelper(elementCount + 1);
    33.         elementData[elementCount++] = e;
    34.         return true;
    35.     }
    36.  
    37.     private void ensureCapacityHelper(int minCapacity) {
    38.         // overflow-conscious code
    39.         // 判断是否扩容
    40.         if (minCapacity - elementData.length > 0){
    41.             grow(minCapacity);
    42.         }
    43.     }
    44.  
    45.     private void grow(int minCapacity) {
    46.         // overflow-conscious code
    47.         int oldCapacity = elementData.length;
    48.         // newCapacity = oldCapacity + oldCapacity
    49.         int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
    50.                 capacityIncrement : oldCapacity);
    51.         if (newCapacity - minCapacity < 0){
    52.             newCapacity = minCapacity;
    53.         }
    54.         elementData = Arrays.copyOf(elementData, newCapacity);
    55.     }
    56. }

    六、LinkedList（P515）

    1. LinkedList 说明

    （1）LinkedList 底层实现了双向链表和双端队列特点。
    （2）可以添加任意元素（元素可以重复），包括 null。
    （3）线程不安全，没有实现同步。

    2. LinkedList 的底层操作机制

    （1）LinkedList 底层维护了一个双向链表。
    （2）LinkedList 中维护了两个属性 first 和 last 分别指向首节点和尾节点。
    （3）每个节点（Node对象），里面又维护了 prev 、next 、item 三个属性，其中通过 prev 指向前一个，通过 next 指向后一个节点。最终实现双向链表。

    （4）所以 LinkedList 的元素的添加和删除，不是通过数组完成的，相对来说效率较高。

    3. LinkedList 源码解读（P516）

    1. public class LinkedList_ {
    2.  
    3.     transient int size = 0;
    4.     protected transient int modCount = 0;
    5.  
    6.     transient Node first;
    7.  
    8.     transient Node last;
    9.  
    10.     private static class Node {
    11.         E item; // 存放数据
    12.         Node next;
    13.         Node prev;
    14.  
    15.         Node(Node prev, E element, Node next) {
    16.             this.item = element;
    17.             this.next = next;
    18.             this.prev = prev;
    19.         }
    20.     }
    21.  
    22.     public boolean add(E e) {
    23.         linkLast(e);
    24.         return true;
    25.     }
    26.  
    27.     void linkLast(E e) {
    28.         final Node l = last;
    29.         final Node newNode = new Node<>(l, e, null);
    30.         last = newNode;
    31.         if (l == null) {
    32.             first = newNode;
    33.         } else {
    34.             l.next = newNode;
    35.         }
    36.         size++;
    37.         modCount++;
    38.     }
    39.  
    40.     public E remove() {
    41.         return removeFirst();
    42.     }
    43.  
    44.     public E removeFirst() {
    45.         final Node f = first;
    46.         if (f == null) {
    47.             throw new NoSuchElementException();
    48.         }
    49.         return unlinkFirst(f);
    50.     }
    51.  
    52.     private E unlinkFirst(Node f) {
    53.         // assert f == first && f != null;
    54.         final E element = f.item;
    55.         final Node next = f.next;
    56.         f.item = null;
    57.         f.next = null; // help GC
    58.         first = next;
    59.         if (next == null) {
    60.             last = null;
    61.         } else {
    62.             next.prev = null;
    63.         }
    64.         size--;
    65.         modCount++;
    66.         return element;
    67.     }
    68. }

    七、ArrayList 和 LinkedList 比较（P517）

    （1）如果我们改查的操作多，选择 ArrayList。
    （2）如果我们增删的操作多，选择 LinkedList。
    （3）一般来说，在程序中，80%-90%都是查询，因此大部分情况下会选择 ArrayList。

  • 相关阅读:
    conan入门(二十九):对阿里mnn进行Conan封装塈conans.CMake和conan.tools.cmake.CMake的区别
    AI算法助力室内家具布局
    机器学习2--matplotlib绘图包
    [Spring Framework]AOP经典案例、AOP总结
    Java通过Lettuce访问Redis主从，哨兵，集群
    如何计算多分组交互pp值
    菲律宾外汇储备降至两年来的最低水平
    《Effective Objective-C 2.0》读书笔记——对象、消息、运行期
    vue清除动态路由
    基于Redis实现分布式锁（执行流程）
  • 原文地址：https://blog.csdn.net/yirenyuan/article/details/130882284