第十四章 集合(List)

2023-12-24 14:33:57

一、集合框架体系

集合:
(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 本身并不存放对象。

public class Test {
 
    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(3);
 
        // list.iterator() 重置迭代器,可重复
        Iterator<Integer> iterator = list.iterator();
        while (iterator.hasNext()) {
            Integer next = iterator.next();
            System.out.println(next);
        }
    }
}

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

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

public class Test {
 
    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(3);
 
        for (Integer e : list) {
            System.out.println(e);
        }
    }
}

三、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)位置的子集合。

public class Test {
 
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("乔峰");
        list.add("段誉");
        list.add(1, "虚竹");
        list.add("Tom");
        System.out.println(list); // [乔峰, 虚竹, 段誉, Tom]
 
        List<String> list2 = new ArrayList<>();
        list2.add("Jack");
        list2.add("Tom");
        list.addAll(1, list2);
        System.out.println(list); // [乔峰, Jack, Tom, 虚竹, 段誉, Tom]
 
        System.out.println(list.get(1)); // Jack
        System.out.println(list.indexOf("Tom")); // 2
        System.out.println(list.lastIndexOf("Tom")); // 5
 
        list.remove(5);
        System.out.println(list); // [乔峰, Jack, Tom, 虚竹, 段誉]
        list.set(2, "Mike");
        System.out.println(list); // [乔峰, Jack, Mike, 虚竹, 段誉]
        System.out.println(list.subList(0, 2)); // [乔峰, Jack]
    }
}

四、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倍。

public class ArrayList_<E> {
 
    transient Object[] elementData;
 
    private int size;
 
    protected transient int modCount = 0;
 
    private static final int DEFAULT_CAPACITY = 10;
 
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
 
    // 无参构造
    public ArrayList_() {
        // 创建一个空的数组
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
 
    public ArrayList_(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } 
    }
 
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        // 在 elementData[size] 赋值,并且size++
        elementData[size++] = e;
        return true;
    }
 
    private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }
 
    private void ensureExplicitCapacity(int minCapacity) {
        // 操作次数
        modCount++;
 
        // overflow-conscious code
        // 判断是否扩容,如果elementData数组大小不够就扩容
        if (minCapacity - elementData.length > 0){
            grow(minCapacity);
        }
 
    }
 
    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }
 
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
 
    // 扩容方法
    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        // 扩容为1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0){
            newCapacity = minCapacity;
        }
        // 防止超过最大值2147483639
        if (newCapacity - MAX_ARRAY_SIZE > 0){
            newCapacity = hugeCapacity(minCapacity);
        }
        // minCapacity is usually close to size, so this is a win:
        // Arrays.copyOf 可以保留原先的数据,并扩容
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
 
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0){
            // overflow
            throw new OutOfMemoryError();
        }
        return (minCapacity > MAX_ARRAY_SIZE) ?
                Integer.MAX_VALUE :
                MAX_ARRAY_SIZE;
    }
}

五、Vector(P513)

1. Vector 的基本介绍

(1)Vector 类的定义说明

public class Vector<E>
    extends AbstractList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable

(2)Vector 底层也是一个对象数组 protected Object[] elementData;
(3)Vector 是线程同步的,即线程安全,Vector 类的操作方法带有 synchronized。
(4)在开发中,需要线程同步安全时,考虑使用 Vector。
在这里插入图片描述

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

Vector 扩容源码类似于 ArrayList

public class Vector_<E> {
 
    protected Object[] elementData;
 
    protected int capacityIncrement;
 
    protected transient int modCount = 0;
 
    protected int elementCount;
 
    public Vector_() {
        this(10);
    }
 
    public Vector_(int initialCapacity) {
        this(initialCapacity, 0);
    }
 
    public Vector_(int initialCapacity, int capacityIncrement) {
        super();
        if (initialCapacity < 0){
            throw new IllegalArgumentException("Illegal Capacity: "+
                    initialCapacity);
        }
        // 初始化数组
        this.elementData = new Object[initialCapacity];
        this.capacityIncrement = capacityIncrement;
    }
 
    public synchronized boolean add(E e) {
        modCount++;
        ensureCapacityHelper(elementCount + 1);
        elementData[elementCount++] = e;
        return true;
    }
 
    private void ensureCapacityHelper(int minCapacity) {
        // overflow-conscious code
        // 判断是否扩容
        if (minCapacity - elementData.length > 0){
            grow(minCapacity);
        }
    }
 
    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        // newCapacity = oldCapacity + oldCapacity
        int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                capacityIncrement : oldCapacity);
        if (newCapacity - minCapacity < 0){
            newCapacity = minCapacity;
        }
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
}

六、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)

public class LinkedList_<E> {
 
    transient int size = 0;
    protected transient int modCount = 0;
 
    transient Node<E> first;
 
    transient Node<E> last;
 
    private static class Node<E> {
        E item; // 存放数据
        Node<E> next;
        Node<E> prev;
 
        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }
 
    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 E remove() {
        return removeFirst();
    }
 
    public E removeFirst() {
        final Node<E> f = first;
        if (f == null) {
            throw new NoSuchElementException();
        }
        return unlinkFirst(f);
    }
 
    private E unlinkFirst(Node<E> f) {
        // assert f == first && f != null;
        final E element = f.item;
        final Node<E> next = f.next;
        f.item = null;
        f.next = null; // help GC
        first = next;
        if (next == null) {
            last = null;
        } else {
            next.prev = null;
        }
        size--;
        modCount++;
        return element;
    }
}

七、ArrayList和LinkedList比较(P517)

在这里插入图片描述
(1)如果我们改查的操作多,选择 ArrayList。
(2)如果我们增删的操作多,选择 LinkedList。
(3)一般来说,在程序中,80%-90%都是查询,因此大部分情况下会选择 ArrayList。

文章来源:https://blog.csdn.net/yirenyuan/article/details/135180508
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。