List数据结构总结：

一、List

1、List 简介：

• 一个 List 是一个元素有序的、可以重复、可以为 null 的集合。

• Java 集合框架中最常使用的几种 List 实现类是 ArrayList，LinkedList 和 Vector。

  
  List 结构图.png

2、List的常用方法

List的常用方法.png

3、List删除时注意

• Collection是继续自lterator类，所以所有的Collection都能使用foreach方法。使用Foreach历list过程中，删除某个元素，会报错，原因是list.remove0方法除元素时并没有修改总元素的个数，导致下一次遍历的时候数量不对报错;
• 可以使用lterator的itr.remove方法，这个方法在删除元素的时候修改了总元索的个数，所以不报错。

二、ArrayList分析：

线性数组。异步的。效率高。多用于查询。
扩容方式:
超出现有长度后，自动扩容，扩容的容量最小是1.5倍。如果一下子增加了100个元素，肯定扩容的容量就不止是1.5倍了。

1、ArrayList 特点：

（1）ArrayList 实现了 RandomAccess 接口，表明 ArrayList 支持随机访问;
（2）ArrayList 实现了 Cloneable 接口，表明 ArrayList 是可以 clone 的;
（3）ArrayList 实现了 Serializable 接口，表明 ArrayList 是支持序列化的;
（4）和 Vector 不同， ArrayList 不是线程安全的，在单线程下可以使用，在多线程中可以选择 Vector 或者CopyOnWriteArrayList;
（5）ArrayList 底层是一段连续的空间，并且可以动态扩容，是一个动态类型的顺序表 ;

2、ArrayList 的构造：

ArrayList 的构造.png

3、ArrayList 的使用：

import java.util.ArrayList;
public class TestDemo {
    public static void main(String[] args) {
       //构造一个空的列表 
       List<Integer> list1 = new ArrayList<>(); 
        //构造一个具有10个容量的列表 
       List<Integer> list2 = new ArrayList<>(10); 
       list2.add(1); 
       list2.add(2); 
       list2.add(3); 
       //list3构造好之后，与list中的元素一致（使用另外一个ArrayList进行初始化）
       ArrayList<Integer> list3 = new ArrayList<>(list2); 
    } 
}

4、ArrayList的扩容机制：

这段代码是否有问题？

public class TestDemo {
   public static void main(String[] args) { 
        List<Integer> list = new ArrayList<>(); 
             for (int i = 0; i < 100; i++) { 
                 list.add(i); 
             } 
   }
}

这段代码其实并没有问题，我们看看ArrayList的底层：

1、可以看到ArrayList继承AbstractList，实现了List, RandomAccess, Cloneable, Serializable接口；

aa567744e9705b96830813f2b46a9ae.png

2、 所以在 List<Integer> list = new ArrayList<>();中，我们认为ArrayList的底层虽然是一个数组，但是当前的这个数组没有大小，大小为0；但是为什么我在ArrayList中add元素，没有抛出数组越界异常的问题？此时，我们需要看看add在底层是如何实现的？

//空数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//携带初始容量的
public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }
//默认的构造，初始容量为0
public ArrayList() {
  this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
 }

3、ArrayList初始容量以及扩容

//1、确定真正的容量，是否要扩容
public boolean add(E e) {
      ensureCapacityInternal(size + 1);  // Increments modCount!!
      elementData[size++] = e;
       return true;
 }
//2、判断是否扩容
private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
           //默认的扩容数DEFAULT_CAPACITY
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        ensureExplicitCapacity(minCapacity);
 }

//3、默认扩容数是10
private static final int DEFAULT_CAPACITY = 10;

ArrayList扩容结构.png

所以，我们可以得出结论：

如果ArrayList调用不带参数的构造方法，那么顺序表的大小为0；当第一次add的时候，整个顺序表的容量才变为10，当这10个空间太小了，就会开始以1.5的方式扩容。如果调用的是给定容量的构造方法，那么我们的顺序表的容量的大小就是我们给定的大小，放满了还是以1.5倍的方式去扩容。

注意:

• 这里的grow函数就是实现数组扩容的方法;
• Arrays.copyOf()是复制数组的操作, 会消耗较多的时间;

private void grow(int minCapacity) {//扩容方法
   // overflow-conscious code
   int oldCapacity = elementData.length;  //旧容量
   int newCapacity = oldCapacity + (oldCapacity >> 1); //新容量=旧容量+旧容量/2 10+10/2=15
   if (newCapacity - minCapacity < 0)//如果新容量-期望的最小容量<0 说明新容量还是不够用
       newCapacity = minCapacity;//新容量=期望的最小容量
       if (newCapacity - MAX_ARRAY_SIZE > 0)// 如果新容量-最大容量>0 说明新容量还是不够用 说明数组已经很大了 不能再扩容了
          newCapacity = hugeCapacity(minCapacity);//新容量=最大容量
          // minCapacity is usually close to size, so this is a win://期望的最小容量通常接近于size，所以这是一个赢利
        elementData = Arrays.copyOf(elementData, newCapacity);//将数组扩容到新容量
 }
//        此时就完成了ArrayList的扩容

5、如何避免ArrayList的扩容

• 在创建ArrayList集合时，根据自己的使用情况，指定一个初始容量；

6、ArrayList的扩容机制：

ensureCapacityInternal方法判断是否要扩容首先获取数组的旧容量，然后计算新容量的值，计算使用位运算，将其扩容至原来的1.5倍。默认容量是10，得到新容量的值后，校验扩容后的容量是否大于需要的容量，如果小于，则把最小需要容量当作扩容后的新容量。并确保扩容后的容量不超过数组能设置的最大大小值。最后将老数组的数据复制到新的数组中。

二、LinkedList分析：

1、LinkedList介绍：

LinkedList由双链表实现，增删由于不需要移动底层数组数据，其底层是链表实现的，只需要修改链表节点指针，对元素的插入和删除效率较高。

异步的，有poll方法\peak方法，可以从链接中拿出来数据。

LinkedList的关系图.png

2、LinkedList特点：

• LinkedList实现List接口，内部元素是有序的。
• LinkedList实现Deque接口，需要提供队列，以及双端队列里的两组增删索引方法，此外还有栈方法。
• LinkedList实现Cloneable接口，需要提供clone方法。
• LinkedList实现Serializable接口，需要提供序列化，反序列化方法。
• LinkedList是双向链表结构，增删效率快，迭代效率慢，此外，迭代的方式只能通过链表挨个遍历。

3、LinkedList构造函数

LinkedList构造函数.png

4、LinkedList常用API

LinkedList常用API.png

5、LinkedList的继承关系

java.lang.Object
   ↳     java.util.AbstractCollection<E>
         ↳     java.util.AbstractList<E>
               ↳    

public class LinkedList<E> extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable {}

6、LinkedList如何初始化

LinkedList底层数据结构是一个具有头尾节点的双向链表。双向链表的优点就是通过某个节点访问其前驱和后驱表较方便。缺点是需要额外存储其前驱和后驱的空间。LinkeList链表允许null元素；

LinkedList构造函数有两种，无参构造和带集合的构造函数
1.无参构造，初始化集合大小size=0，初始不用存储任何数据，内存占用低；
 public LinkedList() {
        this.size = 0;
 }

2.带集合的构造函数，创建一个大小和传入集合大小一致的链表，记录头尾节点
 public LinkedList(Collection<? extends E> c) {
        this();
        this.addAll(c);
 }
3.接着2我们来看下addAll方法，他的参数有index和传入的集合，猜想index应该是传入集合存储开始的地方。
 public boolean addAll(int index, Collection<? extends E> c) {
        //判断这个index是否超过链表有效位置的范围，超出的话会报IndexOutOfBoundsException.
        this.checkPositionIndex(index);
       //返回包含这个集合中所有数据的数组，感觉是个耗时操作
        Object[] a = c.toArray();
      //获取参数集合的长度，是构造之后链表的长度
        int numNew = a.length;
     //参数集合长度为0，说明不需要存储任何数据，就不用做任何事了直接返回。
        if (numNew == 0) {
            return false;
        } else {
      //辅助构造链表
            LinkedList.Node pred;
            LinkedList.Node succ;
        //index = this.size从链表尾部插入
            if (index == this.size) {
                succ = null;
                pred = this.last;
            } else {
       //index != this.size从链表中间插入
                succ = this.node(index);
                pred = succ.prev;
            }

            Object[] var7 = a;
            int var8 = a.length;
        //遍历参数集合的数组，从插入的位置index开始插入
            for(int var9 = 0; var9 < var8; ++var9) {
                Object o = var7[var9];
                LinkedList.Node<E> newNode = new LinkedList.Node(pred, o, (LinkedList.Node)null);
              //插入集合的第一个节点
                if (pred == null) {
                    this.first = newNode;
                } else {
               //上一个节点记录一下当前节点，形成链表
                    pred.next = newNode;
                }
                //pred记录当前节点，开始下一个节点的插入
                pred = newNode;
            }
           //succ =null说明是从链表尾部开始插入的，所以记录一下链表头部，就行了。
            if (succ == null) {
                this.last = pred;
            } else {
           //相反的不是从链表尾部插入，从第index个插入，index元素排在插入的数据后面，形成新链表。
                pred.next = succ;
                succ.prev = pred;
            }
         //记录新的链表长度
            this.size += numNew;
            ++this.modCount;
            return true;
        }
    }

7、LinkedList怎么插入数据？

LinkedList堆插入操作做了相关优化。由于其基于双端链表实现，所以其在头尾插入速度较快，在链表中部插入相对较慢。

    1.头部插入元素，直接通过头节点first插入，头节点变成第二个元素，更新头节点，非常简单。
    private void linkFirst(E e) {
        LinkedList.Node<E> f = this.first;
        LinkedList.Node<E> newNode = new LinkedList.Node((LinkedList.Node)null, e, f);
        this.first = newNode;
        if (f == null) {
            this.last = newNode;
        } else {
            f.prev = newNode;
        }

        ++this.size;
        ++this.modCount;
    }
 2.尾部插入元素，直接通过尾节点插入新元素 ，待插入节点变成新的尾节点。
    void linkLast(E e) {
        LinkedList.Node<E> l = this.last;
        LinkedList.Node<E> newNode = new LinkedList.Node(l, e, (LinkedList.Node)null);
        this.last = newNode;
        if (l == null) {
            this.first = newNode;
        } else {
            l.next = newNode;
        }

        ++this.size;
        ++this.modCount;
    }
 3.中间插入元素，如果index=链表长度则表示在链表尾部插入数据，否则实在指定元素之前插入元素。
    public void add(int index, E element) {
        this.checkPositionIndex(index);
        if (index == this.size) {
            this.linkLast(element);
        } else {
            this.linkBefore(element, this.node(index));
        }
    }
 4.在看linkBefore之前我看下node方法，这个方法是通过index找到链表中的某个数据。通过以下代码我们可以看到它使用了一次二分查找，提高了一次查找效率，但是随着数据增多这个函数的效率会变得越来越低。
   LinkedList.Node<E> node(int index) {
        LinkedList.Node x;
        int i;
        if (index < this.size >> 1) {
            x = this.first;
            for(i = 0; i < index; ++i) {
                x = x.next;
            }
            return x;
        } else {
            x = this.last;
            for(i = this.size - 1; i > index; --i) {
                x = x.prev;
            }
            return x;
        }
    }
 5.接着看下linkBefore方法。找到指定元素就非常好办了，生成新节点，把新节点放在指定元素的前面就可以了。
    void linkBefore(E e, LinkedList.Node<E> succ) {
        LinkedList.Node<E> pred = succ.prev;
        LinkedList.Node<E> newNode = new LinkedList.Node(pred, e, succ);
        succ.prev = newNode;
     //如果succ是头节点，还需要更新头节点指针。
        if (pred == null) {
            this.first = newNode;
        } else {
            pred.next = newNode;
        }
        ++this.size;
        ++this.modCount;
    }

8、LinkedList怎么删除元素

删除节点和增加节点都是通过node方法找到指定元素，然后删除指定节点，链表的基本操作，这里不再赘叙。

三、Vector分析：

1、Vector介绍：

Vector是实现了List接口的子类，其底层是一个对象数组，维护了一个elementData数组，是线程安全的，Vector类的方法带有synchronized关键字，在开发中考虑线程安全中使用Vector。

结构图.png

总结：Vector 和 ArrayList 类似，顶级父类为 Collection，区别于 ArrayList 的重要一点，Vector 集合类为线程安全类，

2、Vector的构造方法

（1）无参构造方法

    public Vector() {
        this(10);
    }

总结：Vector的无参构造方法中会调用有参构造方法，创建一个内部数组，该内部数组的初始容量为10，增量为0

（2）带初始容量的构造方法

    public Vector(int initialCapacity) {
        this(initialCapacity, 0);
    }

总结：构造一个内部数组，该数组的容量为指定的容量，增量为0。

（3）带初始容量和增量的构造方法

    public Vector(int initialCapacity, int capacityIncrement) {
        super();
        //如果初始容量小于0，抛出异常
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        //指定容量
        this.elementData = new Object[initialCapacity];
        //指定增量
        this.capacityIncrement = capacityIncrement;
    }

总结：构造一个具有初始容量和增量的数组。

（4）集合型构造方法

    public Vector(Collection<? extends E> c) {
        elementData = c.toArray();
        elementCount = elementData.length;
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, elementCount, Object[].class);
    }

总结：构造指定集合元素的数组。

3、Vector中的变量

• Vector底层也是数组实现的，其主要变量有：
• elementData:：Vector是基于数组的一个实现，elementData就是底层的数组
• elementCount：数组元素个数
• capacityIncrement：指定Vector容量不足的扩容量，不指定的情况下默认翻倍

4、add方法解析

从上面对于Vector构造方法的分析，不难发现Vector和ArrayList的默认初始容量都是10。那么，我们看看Vector的add()方法又是如何实现的？

    public synchronized boolean add(E e) {
        //AbstractList中的变量
        modCount++;
        //确保数组容量是否足够
        ensureCapacityHelper(elementCount + 1);
        //把元素添加到数组中
        elementData[elementCount++] = e;
        return true;
    }

可以看到：add方法添加一个元素到列表的末尾。它首先通过ensureCapacityHelper(elemetnCount+1)来保证Object[]数组有足够的空间存放添加的数据，然后再将添加的数据存放到数组对应位置上。

    private void ensureCapacityHelper(int minCapacity) {
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

通过ensureCapacityHelper()方法判断最小容量和当前数组长度，若所需的最小容量大于数组大小，则需要进行扩容，然后调用grow()方法实现扩容。

    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
 
    private void grow(int minCapacity) {
        //旧数组的长度
        int oldCapacity = elementData.length;
        //如果指定了增量，则新数组长度=旧数组长度+增量；如果没有指定容量，则新数组长度=旧数组长度2倍
        int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                         capacityIncrement : oldCapacity);
        //判断新容量减去最小容量是否小于0，如果是第一次调用add，则必然小于
        if (newCapacity - minCapacity < 0)
            //将最小容量赋给新容量
            newCapacity = minCapacity;
        /判断新容量减去最大数组大小是否大于0，如果时则计算出一个超大容量
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        //调用数组工具类方法，创建一个新数组，将新数组的地址赋值给elementData
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
    private static int hugeCapacity(int minCapacity) {
        //如果最小容量小于0，抛出异常；否则就比较并返回
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

Step1：先将当前数组大小赋值给oldCapacity，然后判断是否有指定增量的值，如果有，则新数组长度=旧数组长度+增量；如果没有，则新数组长度=旧数组长度*2。

Step2：利用newCapacity进行两次判断：

• 第一次判断 if (newCapacity - minCapacity < 0)，判断扩容后容量是否大于minCapacity，若小于minCapacity，则直接将minCapacity赋值给newCapacity
• 第二次判断 if (newCapacity - MAX_ARRAY_SIZE > 0)，判断newCapacity 是否超出了ArrayList所定义的最大容量，若超出了，则调用hugeCapacity()来比较minCapacity和 MAX_ARRAY_SIZE， 如果minCapacity大于MAX_ARRAY_SIZE，则新容量则为 Interger.MAX_VALUE，否则，新容量大小则为 MAX_ARRAY_SIZE。

Step3：最终得到newCapacity，然后调用Arrays.copyOf（）方法进行扩容

综合上述分析，有以下几个点：

• Vector如果不指定初始容量，则默认创建一个长度为10的数组。
• Vector如果不指定初始增量，则扩容机制为：新数组长度=旧数组长度*2；如果指定初始增量，则扩容机制为：新数组长度=旧数组长度+增量。
• Vector的add()方法是加了synchronized关键字的，这就意味着它是线程安全的。

接下来可以看看如何在指定位置添加元素

    //在指定位置添加元素
    public void add(int index, E element) {
        insertElementAt(element, index);
    }
    //添加元素到指定位置
    public synchronized void insertElementAt(E obj, int index) {
        modCount++;
        //检查位置合法性
        if (index > elementCount) {
            throw new ArrayIndexOutOfBoundsException(index
                                                     + " > " + elementCount);
        }
        //判断是否需要扩容
        ensureCapacityHelper(elementCount + 1);
        //拷贝数组
        System.arraycopy(elementData, index, elementData, index + 1, elementCount - index);
        //添加元素
        elementData[index] = obj;
        elementCount++;
    }

可以看到：在指定位置添加元素，首先进行了数组范围的检查，防止越界，然后调用方法检验是否要扩容，且增量++，之后完成数组拷贝即可。

5、remove()方法

    public boolean remove(Object o) {
        return removeElement(o);
    }
    public synchronized boolean removeElement(Object obj) {
        modCount++;
        //获取该元素所在的数组下标
        int i = indexOf(obj);
        //如果该元素存在，则移除元素
        if (i >= 0) {
            removeElementAt(i);
            return true;
        }
        return false;
    }
    public synchronized void removeElementAt(int index) {
        modCount++;
        //如果下标越界，抛出异常
        if (index >= elementCount) {
            throw new ArrayIndexOutOfBoundsException(index + " >= " +
                                                     elementCount);
        }
        else if (index < 0) {        //下标小于0，抛出异常
            throw new ArrayIndexOutOfBoundsException(index);
        }
        //删除元素
        int j = elementCount - index - 1;
        if (j > 0) {
            System.arraycopy(elementData, index + 1, elementData, index, j);
        }
        elementCount--;
        elementData[elementCount] = null; /* to let gc do its work */
    }

由上述分析：删除元素同样需要进行范围校验。然后计算删除需要移动的数据，再通过数组拷贝移动数组。其次还有一个小细节，可以发现remove()方法是有返回值的，而这个返回值就是我们删除的元素的值。 同样的，真正移除元素的remove()方法也是加锁了的。

6、set()方法

该方法加了synchronized关键字保证安全性，用来设置指定下标的数据，进行元素数据的更新。

    public synchronized E set(int index, E element) {
        //判断合法性
        if (index >= elementCount)
            throw new ArrayIndexOutOfBoundsException(index);
        //修改旧值
        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }

7、 get()方法

该方法用来获取对应下标的数据，也是加锁的方法。

    public synchronized E get(int index) {
        if (index >= elementCount)
            throw new ArrayIndexOutOfBoundsException(index);
 
        return elementData(index);
    }

8、其他方法

    Vector中的其他方法，如：判断是否为空、获取长度等方法，都是加了锁的。因此，可以认为Vector是线程安全的。

 public synchronized int size() {
        return elementCount;
    }
public synchronized boolean isEmpty() {
     return elementCount == 0;
}

9、Vector简单总结

• Vector的底层实现也是数组，在不指定初始容量的情况下，默认初始数组大小为10，其扩容机制为：当指定了增量的时候，新扩容的容量=旧数组长度+容量；如果没有指定增量，新扩容容量=旧数组长度*2。
• Vector是线程安全的，因为它对很多方法都加锁了。
• Vector和ArrayList都是数组实现的，因此其支持快速随机访问，但增加元素和删除元素的操作却是比较耗时的。

10\对比ArrayList

** 相同：两个类都实现了List接口，它们都是有序且元素可重复的集合。**

**不同：**

• （1）ArrayList 是线程不安全的，Vector 是线程安全的。ArrayList 是线程不安全的，所以当我们不需要保证线程安全性的时候推荐使用 ArrayList，如果想要在多线程中使用 ArrayList 可以通过 Collections.synchronizedList(new ArrayList()) 或 new CopyOnWriteArrayList 的方式创建一个线程安全的 ArrayList 集合；Vector 类的所有方法都是同步的。可以有两个线程安全的访问一个 Vector 对象，但是一个线程访问 Vector 的话会在同步操作上耗费大量的时间。

• （2）ArrayList 使用默认构造器创建对象时是在调用 add() 方法时对 ArrayList 的默认容量进行初始化的，Vector 在调用构造器时就对容量进行了初始化

• （3）ArrayList 存储数据的 Object 数组使用了transient关键字，Vector 的 Object 数组没有。
  关于transient关键字的说明：如果用 transient 声明一个实例变量，当对象存储时，它的值不需要维持。这里的对象存储是指，Java 的 serialization 提供的一种持久化对象实例的机制。当一个对象被序列化的时候，transient型变量的值不包括在序列化的表示中，然而非transient型的变量是被包括进去的。例如：当持久化对象时，可能有一个特殊的对象数据成员，我们不想用 serialization 机制来保存它。为了在一个特定对象的一个域上关闭 serialization，可以在这个域前加上关键字 transient。
简单的说，就是被 transient 修饰的成员变量，在序列化的时候其值会被忽略，在被反序列化后， transient 变量的值被设为初始值， 如 int 型的是 0，对象型的是 null。

• （4）扩容机制不同。ArrayList扩容机制为变为原来的1.5倍，而Vector扩容时如果指定了增量，则新数组长度=旧数组长度+增量，如果没有指定，就扩容为原来的2倍。

---

ArrayList参考：https://blog.csdn.net/Poem_coder/article/details/123076554
https://blog.csdn.net/weixin_47053593/article/details/127127688
Vector链接：https://blog.csdn.net/weixin_47382783/article/details/125881166