Collection集合体系全景图（二）-六虎

Collection宗族:

LinkedList详解

LinkedList 继承自 AbstrackSequentialList 并完成了 List 接口以及 Deque 双向行列接口，因而 LinkedList 不但具有 List 相关的操作办法，也有行列的相关操作办法。

LinkedList 和 ArrayList相同完成了序列化接口 Serializable 和 Cloneable 接口使其具有了序列化和克隆的特性。

LinkedList 一些首要特性：

LinkedList 调集底层完成的数据结构为双向链表
LinkedList 调集中元素允许为 null
LinkedList 允许存入重复的数据
LinkedList 中元素存放次序为存入次序。
LinkedList 对错线程安全的，假如想确保线程安全的前提下操作 LinkedList，能够运用 List list = Collections.synchronizedList(new LinkedList(…)); 来生成一个线程安全的

LinkedList 一些常用办法

add(E e)：在链表结尾增加元素e。

add(int index, E e)：在指定方位刺进元素e。

remove()：删去链表结尾的元素。

remove(int index)：删去指定方位的元素。

get(int index)：获取指定方位的元素。

set(int index, E e)：将指定方位的元素替换为e。

size()：回来链表中元素的个数。

clear()：清空链表中的一切元素。

isEmpty()：判断链表是否为空。

indexOf(Object o)：回来元素o在链表中第一次呈现的方位，假如不存在则回来-1。

lastIndexOf(Object o)：回来元素o在链表中最终一次呈现的方位，假如不存在则回来-1。 toArray()：将链表转换为数组。

认识链表结构

链表是一种常用的数据结构，它的首要作用是用来存储和办理数据。链表的特点是能够动态地增加和删去元素，而且不需求预先分配内存空间。这使得链表在处理很多数据时十分高效。

链表的另一个长处是能够支持快速的刺进和删去操作，因为只需求修正指针的指向即可，而不需求像数组相同移动很多的元素。这使得链表在完成一些高级算法时十分有用，比方图论中的最短路径算法和拓扑排序算法等，此外链表还能够用来完成栈和行列等数据结构。

链表的分类

单向链表

单向链表是一种线性数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针。单向链表只能从头节点开端遍历，每个节点只能拜访其后继节点，不能拜访前驱节点。

长处：刺进和删去操作的时刻复杂度为O(1)，只需求修正指针即可。不需求预先分配内存空间，能够动态地增加或删去节点。

缺陷：不能随机拜访节点，只能从头节点开端遍历，时刻复杂度为O(n)。需求额定的空间存储指针信息。

双向链表

双向链表是一种线性数据结构，每个节点包含数据和指向前驱节点和后继节点的指针。双向链表能够从头节点或尾节点开端遍历，每个节点能够拜访其前驱节点和后继节点。

长处：能够双向遍历，拜访节点的前驱和后继节点，时刻复杂度为O(1)。刺进和删去操作的时刻复杂度为O(1)，只需求修正指针即可。

缺陷：需求额定的空间存储指针信息。

循环链表

循环链表是一种特别的双链表，其尾节点指向头节点，构成一个环。循环链表能够从任意节点开端遍历，每个节点能够拜访其前驱节点和后继节点。

长处：能够从任意节点开端遍历，时刻复杂度为O(n)。刺进和删去操作的时刻复杂度为O(1)，只需求修正指针即可。

缺陷：需求额定的空间存储指针信息。需求特别处理尾节点的指针，简单呈现死循环的状况。

为什么会有单、双链表之分？

假如单向链表要删去元素的话，不但要找到删去的节点，还要找到删去节点的上一个节点（通常称之为前驱），因为需求改变上一个节点中 next 的指针，但又因为它是单向链表，所以在删去的节点中并没有存储上一个节点的相关信息，那么我们就需求再查询一遍链表以找到上一个节点，这样就带来了必定的功能问题，所以就有了双向链表。

源码解析

//LinkedLis 节点个数
transient int size = 0;  
//LinkedLis首个节点
transient Node<E> first;  
//LinkedLis尾节点
transient Node<E> last;
//空参结构因为生成一个空链表 first = last = null
public LinkedList() {  
}  
带参结构传入一个调集类，来结构一个具有必定元素的 LinkedList 调集
public LinkedList(Collection<? extends E> c) {  
this();  
addAll(c);  
}
//这个办法
public boolean addAll(Collection<? extends E> c) {  
return addAll(size, c);  
}

该办法将指定调集中的一切元素增加到列表的结尾。它回来一个布尔值，表明是否成功增加了一切元素。该办法运用另一个重载办法addAll(int index, Collection<? extends E> c)，将指定调集中的一切元素刺进到列表中的指定方位。

    public boolean addAll(int index, Collection<? extends E> c) {
    //1.  查看索引是否满足要求，即 index >= 0 && index <= size。
    checkPositionIndex(index);  
    //将调集变成数组
    Object[] a = c.toArray();  
    int numNew = a.length;  
    //当数组长度为0时回来false
    if (numNew == 0)  
    return false;  
    //找到该索引值对应的节点的前驱节点和后继节点
    Node<E> pred, succ;  
    //index等于当时链表的巨细size则阐明要增加的元素应该放在链表的结尾，此时后继节点为空，前驱节点为当时链表的最终一个节点
    if (index == size) {  
    succ = null;  
    pred = last;  
    } else {  
    //node(index)办法找到索引值为index的节点，将该节点作为后继节点
    succ = node(index);  
    //该节点的前驱节点作为前驱节点
    pred = succ.prev;  
    }  
    // 遍历数组中的元素，将每个元素封装成一个新的节点，并刺进到链表中。
    for (Object o : a) {  
    //将一个Object类型的变量o强制转换为泛型类型E的变量e
    @SuppressWarnings("unchecked") E e = (E) o;  
    Node<E> newNode = new Node<>(pred, e, null);  
    //假如前驱节点为空，则阐明链表为空，将新节点设置为链表的第一个节点。
    if (pred == null)  
    first = newNode;  
    else  
    //则将前驱节点的后继节点设置为新节点
    pred.next = newNode;  
    //将前驱节点更新为新节点，以便下一次刺进节点时运用。
    pred = newNode;  
    }  
    //阐明刺进的方位是链表的结尾，需求更新`last`的值为`pred
    if (succ == null) {  
    last = pred;  
    } else {  
      //阐明刺进的方位在链表中间，需求将pred的`next`指针指向succ，一起将succ的prev指针指向pred
    pred.next = succ;  
    succ.prev = pred;  
    }  
    //更新链表的巨细和修正计数器
    size += numNew;  
    modCount++;  
    return true;  
    }

其他增加办法能够自行总结

查看索引是否满足要求，即 index >= 0 && index <= size。

将调集转换为数组。

假如数组长度为0，则回来false。

找到要刺进的方位的前驱节点和后继节点。

遍历数组中的元素，将每个元素封装成一个新的节点，并刺进到链表中。

更新链表的头尾节点。

更新列表的巨细和修正计数器。

回来true表明增加成功。

删去节点

    /** * 删去头节点
    * @return 删去的节点的值 即 节点的 element
     * @throws NoSuchElementException 假如链表为空则抛出异常
     */ 
    public E removeFirst() { 
    final Node<E> f = first; if (f == null) 
    throw new NoSuchElementException(); 
    return unlinkFirst(f); 
    } 
    /** * 删去尾节点 
    * @return 删去的节点的值 即 节点的 element 
    * @throws NoSuchElementException 假如链表为空则抛出异常 */ 
    public E removeLast() {
     final Node<E> l = last; if (l == null) t
     hrow new NoSuchElementException();
     return unlinkLast(l); 
    }
    //删去头节点 
    private E unlinkFirst(Node<E> f) {  
    final E element = f.item;  
    final Node<E> next = f.next;  
    f.item = null;  
    f.next = null; 
    first = next;  
    if (next == null)  
    last = null;  
    else  
    next.prev = null;  
    size--;  
    modCount++;  
    return element;  
    }
    //删去尾部节点 
    private E unlinkLast(Node<E> l) {  
    final E element = l.item;  
    final Node<E> prev = l.prev;  
    l.item = null;  
    l.prev = null; 
    last = prev;  
    if (prev == null)  
    first = null;  
    else  
    prev.next = null;  
    size--;  
    modCount++;  
    return element;  
    }
    //删去任意节点
    unlink(Node<E> x) {  
    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--;  
    modCount++;  
    return element;  
    }

总结：具体完成进程是将要删去的节点的前驱节点和后继节点连接起来，然后将要删去的节点的前驱节点和后继节点的指针指向，最终将要删去的节点的元素值置为，一起更新链表的巨细和修正计数器

CopyOnWriteArrayList线程安全的 List 调集

它的作用是在读多写少的场景下提高功能。它的完成办法是在写操作时，先将原有的数据仿制一份，然后在新的数据上进行写操作，最终再将原有数据的引证指向新的数据。这样做的好处是读操作不需求加锁，因为读取的是原有数据，不会受到写操作的影响，而写操作也不会影响到读操作，因为写操作是在新的数据上进行的。这样就能够防止读写操作之间的竞争，提高了并发功能

缺陷

因为每次写操作都需求创立一个新的数组，因而写操作的功能较差，尤其是在数据量较大时。此外，因为 CopyOnWriteArrayList 在写操作时需求仿制整个数组，因而它的内存占用较大，不适合存储很多数据。因而，CopyOnWriteArrayList 在实践开发中运用较少。

排除心中疑问

线程安全和不安全的区别首要在于多线程并发拜访时是否会呈现数据不一致或许异常状况。线程安全的调集类在多线程并发拜访时，能够确保数据的一致性和正确性，不会呈现数据不一致或许异常状况。

ArrayList线程不安全为什么还常常运用

ArrayList的功能比较好，因为它是基于数组完成的，能够快速地拜访和修正元素。

在单线程环境下，ArrayList的运用对错常安全的，因为只要一个线程在对其进行操作。

在多线程环境下，假如只要一个线程对其进行写操作，而其他线程只进行读操作，那么也是安全的。

在某些状况下，我们能够经过运用同步机制来确保ArrayList的线程安全性，比方运用Collections.synchronizedList()办法或许运用ConcurrentModificationException异常来防止多线程一起修正ArrayList的状况。

因而，尽管ArrayList对错线程安全的，可是因为其功能和易用性等方面的长处，依然常常被运用。可是，在多线程环境下，我们应该尽量防止运用非线程安全的调集，而是运用线程安全的调集，比方Vector、CopyOnWriteArrayList等。

CopyOnWriteArrayList源码解读

    public boolean add(E e) {
    final ReentrantLock lock = this.lock;  
    lock.lock();  
    try {  
    Object[] elements = getArray();  
    int len = elements.length;  
    //创立一个新的数组newElements，它的长度比原数组elements多1，
    //然后将原数组elements中的一切元素仿制到新数组newElements中。
    //这个操作能够用来在数组结尾增加一个新元素。
    Object[] newElements = Arrays.copyOf(elements, len + 1);  
    newElements[len] = e;  
    setArray(newElements);  
    return true;  
    } finally {  
    lock.unlock();  
    }  
    }
    //transient表明该成员变量不会被序列化，即在目标被序列化时，该成员变量的值不会被保存；
    //volatile表明该成员变量是多线程共享的，任何线程在修正该变量时，都会立即将修正后的值刷新到主内存中，其他线程在读取该变量时，都会从主内存中读取最新的值
    //Object[]表明该成员变量是一个数组类型，其中每个元素都是一个Object类型的目标
    private transient volatile Object[] array;
    final Object[] getArray() {  
        return array;  
}

首先获取了当时目标的锁，然后获取当时数组的元素将其仿制到一个新的数组中，并在新数组的最终增加新元素。最终将新数组设置为当时数组，并回来true表明增加成功。最终释放锁。

以上就是关于List下3种常用完成进行详细解说，内赠送一张总结图

Collection集合体系全景图（二）

Collection宗族:

LinkedList详解

LinkedList 一些首要特性：

LinkedList 一些常用办法

认识链表结构

链表的分类

单向链表

双向链表

循环链表

为什么会有单、双链表之分？

源码解析

其他增加办法能够自行总结

删去节点

CopyOnWriteArrayList线程安全的 List 调集

缺陷

排除心中疑问

ArrayList线程不安全为什么还常常运用

CopyOnWriteArrayList源码解读

相关文章

日拱一卒，伯克利CS61A，作业4，伯克利教你学递归

Shell编程从入门到实践 ——实践篇

写给go开发者的gRPC教程-metadata

程序员的出路：技术变迁与时代背景的双重挑战

作者信息