List集合（源码学习）
本文共 23968 字，大约阅读时间需要 79 分钟。
没有什么是必须得到的，也没有什么是不可失去的。
List集合
文章目录
前言
List集合是有序集合，集合中的元素可以重复；
List集合人家集合的每个元素都有自己的编号–索引值；
List接口继承于，集合的每个元素都有其对应的顺序索引。 一、List集合详解
它提供了一套增删改查数据和通过索引插入删除替换集合元素的方法的规范； List允许添加重复元素；List允许拥有Null元素；List支持泛型；
An ordered collection (also known as a sequence). The user of this
interface has precise control over where in the list each element is inserted. The user can access elements by their integer index (position in *the list), and search for elements in the list.
大家学习可以看一下源码的英文注释。个人感觉很有用 ，你想知道的，人家都给你说清楚了。
二、ArrayList
前面咱们说过ArrayList的实现原理就是数组，他是一种动态数组；
正因为它的数据结构是动态数组，所以它的查询快、增删慢； 那么动态数组和数组有什么区别？
和Java中的数组相比，ArrayList能够动态的改变数组的大小； 
很明显数组的大小是动态的变化的； ArrayList允许空值和重复元素，当ArrayList中添加的元素的数量大于其底层数组的容量的时候，ArrayList会通过扩容机制生成一个更大的数组；
ArrayList是非线程安全的，并发的情况下，多个线程同时操作ArrayList，会出现错误；ArrayList扩容机制
ArrayList的初始化方式
ArrayList有三种初始化的方式：
/** * Default initial capacity. * 默认初始化数组数组的容量大小 10； */ private static final int DEFAULT_CAPACITY = 10; /** * Shared empty array instance used for empty instances. */ private static final Object[] EMPTY_ELEMENTDATA = { }; /** * Shared empty array instance used for default sized empty instances. We * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when * first element is added. */ private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = { }; /** * The array buffer into which the elements of the ArrayList are stored. * The capacity of the ArrayList is the length of this array buffer. Any * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA * will be expanded to DEFAULT_CAPACITY when the first element is added. */ transient Object[] elementData; // non-private to simplify nested class access /** * The size of the ArrayList (the number of elements it contains). * * @serial */ private int size; /** * Constructs an empty list with the specified initial capacity. * * @param initialCapacity the initial capacity of the list * @throws IllegalArgumentException if the specified initial capacity * is negative * 带初始容量参数的构造函数，用户可以自己定义初始容量 */ public ArrayList(int initialCapacity) { if (initialCapacity > 0) { this.elementData = new Object[initialCapacity];//如果初始容量大于0，初始一个自定义大小的数组，大小为initialCapacity； } else if (initialCapacity == 0) { this.elementData = EMPTY_ELEMENTDATA;//如果初始容量等于0，创建一个空数组； } else { throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);//如果初始容量小于0，抛出异常； } } /** * Constructs an empty list with an initial capacity of ten. * 无参构造，默认的构造函数，使用初始容量10构造一个空列表； */ public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;//这里初始化赋值的是一个空的数组，当真正的添加第一个元素的时候，会初始化数组的长度10； } /** * Constructs a list containing the elements of the specified * collection, in the order they are returned by the collection's * iterator. * * @param c the collection whose elements are to be placed into this list * @throws NullPointerException if the specified collection is null *构造一个包含指定collection元素的列表，元素利用集合的迭代器按顺序返回； *如果集合为null，抛出异常； */ public ArrayList(Collection c) { elementData = c.toArray(); if ((size = elementData.length) != 0) { // c.toArray might (incorrectly) not return Object[] (see 6260652) if (elementData.getClass() != Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); } else { // replace with empty array. this.elementData = EMPTY_ELEMENTDATA; } } add方法
/** * Appends the specified element to the end of this list. * * @param e element to be appended to this list * @return true (as specified by {@link Collection#add}) * 将集合追加到列表的最后 */ public boolean add(E e) { //添加元素之前，会调用ensureCapacityInternal方法 ensureCapacityInternal(size + 1); // Increments modCount!! //添加元素的实质就是给数组赋值 elementData[size++] = e; return true; } ensureCapacityInternal方法
private void ensureCapacityInternal(int minCapacity) { ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); } 这里涉及两个方法， ensureExplicitCapacity方法和calculateCapacity方法；
calculateCapacity方法
//计算容量 private static int calculateCapacity(Object[] elementData, int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { //如果数组是默认的空数组的话，比较初始话数组的默认容量和minCapacity的大小，如果是默认的构造方法，那么我们的默认的容量的大小就是 //DEFAULT_CAPACITY 10；获取默认容量和传入参数的较大值； //数组不是在这里扩容的； return Math.max(DEFAULT_CAPACITY, minCapacity); } //如果容量不是空的话，默认返回的容量就是传入的参数； return minCapacity; } ensureExplicitCapacity方法
private void ensureExplicitCapacity(int minCapacity) { modCount++;//记录集合扩容的次数 // overflow-conscious code if (minCapacity - elementData.length > 0) grow(minCapacity);//调用这个方法，表示数组开始扩容了； } 分析：添加第一个元素到ArryList时，elementData.length是0；此时执行了calculateCapacity方法，这时的minCapacity是10.minCapacity - elementData.length > 0满足条件，所以会执行grow(minCapacity)方法，开始扩容；添加第二个元素到ArrayList时，此时elementData.length是10，因为上一步，我们扩容成为10了。minCapacity - elementData.length > 0不满足条件，不会执行grow(minCapacity)方法。一直到添加第十一个元素到ArrayList中，minCapacity此时是11，elementData.length是10，elementData.length > 0满足条件，所以会执行grow(minCapacity)方法，开始扩容；
接下来，我们看一下grow（）扩容的逻辑；
grow方法
/** * Increases the capacity to ensure that it can hold at least the * number of elements specified by the minimum capacity argument. * * @param minCapacity the desired minimum capacity */ private void grow(int minCapacity) { // overflow-conscious code //注意oldCapacity是扩容前的容量，newCapacity是新容量； int oldCapacity = elementData.length; //这里采用的是位运算，意思就是扩容成为原来的1.5倍 int newCapacity = oldCapacity + (oldCapacity >> 1); //如果扩容后的大小还是小于需要的大小，新容量就是minCapacity； if (newCapacity - minCapacity < 0) newCapacity = minCapacity; // 如果新容量大于 MAX_ARRAY_SIZE,进入(执行) `hugeCapacity()` 方法来比较 minCapacity 和 MAX_ARRAY_SIZE， //如果minCapacity大于最大容量，则新容量则为`Integer.MAX_VALUE`，否则，新容量大小则为 MAX_ARRAY_SIZE 即为 `Integer.MAX_VALUE - 8`。 if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity); } hugeCapacity() 方法
private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // overflow throw new OutOfMemoryError(); //对minCapacity和MAX_ARRAY_SIZE进行比较 //若minCapacity大，将Integer.MAX_VALUE作为新数组的大小 //若MAX_ARRAY_SIZE大，将MAX_ARRAY_SIZE作为新数组的大小 //MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; } ArrayList基础操作
import java.util.ArrayList;import java.util.Iterator;import java.util.List;/** * @version 1.0 * @auther WangCode * @date 2021/2/19 11:46 */public class Test { public static void main(String[] args) { ArrayList list = new ArrayList<>(); //添加元素 list.add("a"); list.add("b"); list.add("c"); list.add("d"); list.add("e"); //遍历 for (String s : list) { System.out.println(s); } //迭代器 Iterator iterator = list.iterator(); while (iterator.hasNext()){ String next = iterator.next(); System.out.println("next = " + next); } //删除 list.remove(3); for (String s : list) { System.out.println("s = " + s); } //修改 list.set(1,"修改的部分"); System.out.println("修改部分的输出============"); for (String s : list) { System.out.println(s); } }} 输出结果：
三、LinkedList
构造方法
添加元素
普通尾部添加元素
public boolean add(E e) { linkLast(e); return true; } /** * Links e as last element. */ void linkLast(E e) { //获取原来尾节点 final Node l = last; //l是前驱节点，e是新的节点、null是后继节点 //new 一个新的节点将前驱节点指向原来的尾节点，后继节点指向空； final Node newNode = new Node<>(l, e, null); //将last指向新添加的节点； last = newNode; //判断原来的尾节点是空，就是链表没有尾节点，证明原来的链表是空的； if (l == null) //添加原来链表的first指向新的节点； first = newNode; else //如果原来的链表不是空的，那么原来链表的尾节点指向新添加的节点； l.next = newNode; //链表的大小加1 size++; //修改次数加1 modCount++; } 指定元素位置插入
/** * Inserts the specified element at the specified position in this list. * Shifts the element currently at that position (if any) and any * subsequent elements to the right (adds one to their indices). * * @param index index at which the specified element is to be inserted * @param element element to be inserted * @throws IndexOutOfBoundsException {@inheritDoc} */ public void add(int index, E element) { //检查元素的下标是否合法 checkPositionIndex(index);//如果添加元素的下标等于链表的大小，就是添加元素到链表的尾部的意思和上面的插入是一样的，这也是linkLast(element);封装的原因 if (index == size) linkLast(element); else //否则就执行linkBefore(element, node(index))方法 ； //element是要插入的节点；node（index）是原来的index对应的节点； linkBefore(element, node(index)); } void linkBefore(E e, Nodesucc) { // assert succ != null; //原来index对应节点的前继节点 final Node pred = succ.prev; //新节点的前继节点就是原来inde下对应节点的前继节点； //新节点的后继节点就是原来index对应节点 final Node newNode = new Node<>(pred, e, succ); //原来index对应节点的前驱节点对应的是现在的新的节点 succ.prev = newNode; //如果原来index对应的前驱节点是空的话，说明你要插入的位置是头节点的位置，直接赋值就是了 if (pred == null) first = newNode; else //否则将原来index对应的节点的后继节点指向新的节点 pred.next = newNode; //链表的大小加一 size++; //修改的次数加一 modCount++; }
addAll的自己看好吧；
删除方法
/** * Removes the first occurrence of the specified element from this list, * if it is present. If this list does not contain the element, it is * unchanged. More formally, removes the element with the lowest index * {@code i} such that * (o==null ? get(i)==null : o.equals(get(i))) * (if such an element exists). Returns {@code true} if this list * contained the specified element (or equivalently, if this list * changed as a result of the call). * * @param o element to be removed from this list, if present * @return {@code true} if this list contained the specified element */ public boolean remove(Object o) { //如果你删除的额对象是个空的null if (o == null) { //从链表的头节点开始依次遍历链表 for (Node x = first; x != null; x = x.next) { //如果遍历到节点的值就是null的话 if (x.item == null) { //将节点值是null的这个节点unlink(x)； //我们需要看一下这个是个啥操作； //释放指定的元素节点 unlink(x); return true; } } } else { for (Node x = first; x != null; x = x.next) { if (o.equals(x.item)) { unlink(x); return true; } } } return false; } /** * Unlinks non-null node x. */ //释放非空节点 E unlink(Nodex) { // assert x != null; //获取节点的值； final E element = x.item; //获取节点的前驱和后继 final Node next = x.next; final Node 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; }//原来节点的值置空，目的是帮助java进行垃圾回收 x.item = null; size--; modCount++; return element; }
查找方法
public E get(int index) { //检查元素小标的索引是否合法 checkElementIndex(index); //返回指定下标的节点的元素值 return node(index).item; } //获取index位置的链表的节点 Nodenode(int index) { // assert isElementIndex(index);//如果节点的下标值小于链表大小的一半，位运算 if (index < (size >> 1)) { //从链表的头部开始遍历 Node x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { //如果节点的下标值大于链表大小的一半，从链表的尾部开始遍历，优化了链表的查询速度； Node x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } }
遍历
ArrayList查找和LinkedList查找对比：
LinkedList:package unionlotto;import java.util.LinkedList;import java.util.List;/** * @version 1.0 * @auther WangCode * @date 2021/3/12 21:28 */public class Test { public static void main(String[] args) { //程序执行开始时间 long start = System.currentTimeMillis(); //创建集合 List list = new LinkedList<>(); //测试长度； int testL = 100000; for (int i = 0; i < testL; i++) { list.add("测试数据"+i); } for (int i = 0; i < testL; i++) { list.get(i); } //程序执行结束时间 long end = System.currentTimeMillis(); System.out.println("程序运行需要的时间是"+(end-start)); }} 运行结果：
插入、遍历10万条数据花费了15秒的时间，是比较可怕的； package unionlotto;import java.util.ArrayList;import java.util.LinkedList;import java.util.List;/** * @version 1.0 * @auther WangCode * @date 2021/3/12 21:28 */public class Test { public static void main(String[] args) { //程序执行开始时间 long start = System.currentTimeMillis(); //创建集合 List list = new ArrayList<>(); //测试长度； int testL = 100000; for (int i = 0; i < testL; i++) { list.add("测试数据"+i); } for (int i = 0; i < testL; i++) { list.get(i); } //程序执行结束时间 long end = System.currentTimeMillis(); System.out.println("程序运行需要的时间是"+(end-start)); }} 相同的代码。只是创建的是ArrayList的对象。猜测一下我们的程序运行结果：
程序的运行时间是25毫秒，这里以本人的人品担保，使用的是同一台电脑，程序运行间隔不超过一分钟； 可是为什么两段代码的差距这么大？ 
ArrayList是直接返回index对应的元素，LinkedList是需要从头部或从尾部一次的走指针才能锁定index对应的元素； （这个先这样，后面有重要的再进行补充） 三、Vector
Vector集合是List接口的实现类，他底层的数据结构是数组；
它的内部实现和ArrayList差不多，但是他的很多实现方法上面都增加了同步语句；
这样保证了所有对外接口都会以Vector对象为锁； 相对的是线程安全的，这个是一个比较深的点需要去研究一下👀 public class Vectorextends AbstractList implements List , RandomAccess, Cloneable, java.io.Serializable
实现了RandomAccess接口，提供了随机访问的功能；
实现了Cloneable接口，提供了能被克隆的功能； 实现了Serializable，支持序列化操作；相对线程安全
这里是学习前辈的一个例子；
package unionlotto;import java.util.Vector;import java.util.concurrent.CountDownLatch;/** * @version 1.0 * @auther WangCode * @date 2021/3/12 21:28 */public class Test { public static void main(String[] args) throws InterruptedException{ //CountDownLatch 多线程控制工具类，用来控制线程等待、它可以让某一个线程等待直到倒计时结束，再开始执行； //实例化并指定计数个数 CountDownLatch countDownLatch = new CountDownLatch(2); Vector vector = new Vector<>(); MyThread myThread1 = new MyThread(countDownLatch, vector, "abc"); MyThread myThread2 = new MyThread(countDownLatch, vector, "abc"); myThread1.start(); myThread2.start(); //等待检查，等待两个线程都执行完成后，主线程才能继续执行 countDownLatch.await(); int vectorSize = vector.size(); System.out.println("vector size: " + vectorSize); for (int i = 0; i < vectorSize; i++) { System.out.println("index " + i + ": " + vector.get(i)); } } static class MyThread extends Thread { private CountDownLatch countDownLatch; private Vector vector; private String element; public MyThread(CountDownLatch countDownLatch, Vector vector, String element) { this.countDownLatch = countDownLatch; this.vector = vector; this.element = element; } @Override public void run() { super.run(); try { //如果vector不包含元素 if (!vector.contains(element)) { //线程睡眠1秒 Thread.sleep(1000); //添加元素 vector.add(element); } } catch (InterruptedException e) { e.printStackTrace(); } finally { countDownLatch.countDown();//个数-1； } } }} 设想一个场景：
线程1和线程2同时运行这段代码，线程1判断if (!vector.contains(element)) ，结果是false，进入睡眠； 线程2运行判断是否if (!vector.contains(element)) ，结果也是false，进入睡眠；最终两个线程就会出现下面的结果；
所以Vector的线程安全也是相对的； 
解决这个问题的方法就是：
在我们出问题的那个地方加上同步控制，
package unionlotto;import java.util.Vector;import java.util.concurrent.CountDownLatch;/** * @version 1.0 * @auther WangCode * @date 2021/3/12 21:28 */public class Test { public static void main(String[] args) throws InterruptedException{ //CountDownLatch 多线程控制工具类，用来控制线程等待、它可以让某一个线程等待直到倒计时结束，再开始执行； //实例化并指定计数个数 CountDownLatch countDownLatch = new CountDownLatch(2); Vector vector = new Vector<>(); MyThread myThread1 = new MyThread(countDownLatch, vector, "abc"); MyThread myThread2 = new MyThread(countDownLatch, vector, "abc"); myThread1.start(); myThread2.start(); //等待检查，等待两个线程都执行完成后，主线程才能继续执行 countDownLatch.await(); int vectorSize = vector.size(); System.out.println("vector size: " + vectorSize); for (int i = 0; i < vectorSize; i++) { System.out.println("index " + i + ": " + vector.get(i)); } } static class MyThread extends Thread { private CountDownLatch countDownLatch; private Vector vector; private String element; public MyThread(CountDownLatch countDownLatch, Vector vector, String element) { this.countDownLatch = countDownLatch; this.vector = vector; this.element = element; } @Override public void run() { super.run(); try { //如果vector不包含元素 synchronized (vector){ if (!vector.contains(element)) { //线程睡眠1秒 Thread.sleep(1000); //添加元素 vector.add(element); } } } catch (InterruptedException e) { e.printStackTrace(); } finally { countDownLatch.countDown();//个数-1； } } }} 运行结果：
Stack学习
Stack是Vector的一个子类，它的意义是实现了一个先进后出的栈；
接下来，俺们一起剖析一下这些方法： 构造方法
public Stack() { } push方法
元素入栈
/** * Pushes an item onto the top of this stack. This has exactly * the same effect as: ** * @param item the item to be pushed onto this stack. * @return the* addElement(item)itemargument. * @see java.util.Vector#addElement */ public E push(E item) { //添加元素 addElement(item); return item; }
//同步的，传入的参数是添加的元素； public synchronized void addElement(E obj) { //修改次数+1 modCount++; //扩容机制，这里的elementCount是栈的实际容量 ensureCapacityHelper(elementCount + 1); //数组追加一个传入的元素 elementData[elementCount++] = obj; } private void ensureCapacityHelper(int minCapacity) { // overflow-conscious code //如果实际需要的大小大于数组的大小，进行扩容 if (minCapacity - elementData.length > 0) //扩容方法 grow(minCapacity); } //传入的参数是实际需要的大小 private void grow(int minCapacity) { // overflow-conscious code //oldCapacity是数组原来的大小 int oldCapacity = elementData.length; //这个capacityIncrement在Stack里面不能被设置，但是默认是0； //可以推出每次扩容的大小是原来的两倍； int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity); //如果扩容后的大小还是不能满足实际需要的大小 if (newCapacity - minCapacity < 0) //将扩容的数组大小转换成为实际需要的大小 newCapacity = minCapacity; //如果扩容的大小大于Integer.MAX_VALUE - 8，也就是MAX_ARRAY_SIZE的话； if (newCapacity - MAX_ARRAY_SIZE > 0) //这里实际上会直接限制实际的最大值 newCapacity = hugeCapacity(minCapacity); //执行复制操作 elementData = Arrays.copyOf(elementData, newCapacity); } peek方法
获取栈顶元素
public synchronized E peek() { //获得栈的大小 int len = size();//如果是个空栈的话，抛出空异常 if (len == 0) throw new EmptyStackException(); //这里返回的是最后一个添加到数组的元素，按照栈的原则，也就是栈顶的元素； //注意这里只是返回栈顶的元素，并不会对栈的具体的结构产生影响； return elementAt(len - 1); } public synchronized E elementAt(int index) { //如果元素的索引值大于等于栈的实际大小，抛出异常 if (index >= elementCount) { throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount); }//否则返返回一个index的数组的值 return elementData(index); } E elementData(int index) { //返回指定索引值的数组元素，即数组的下标是index的值 return (E) elementData[index]; } pop方法
元素出栈，返回出栈元素的值
public synchronized E pop() { E obj; //返回栈的大小 int len = size(); //执行peek方法，获得栈顶的元素 obj = peek(); //移除栈顶元素 removeElementAt(len - 1); return obj; } public synchronized void removeElementAt(int index) { //修改次数加一 modCount++; //判断索引值的合理性 if (index >= elementCount) { throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount); } else if (index < 0) { throw new ArrayIndexOutOfBoundsException(index); } //下两步操作是直接给人家栈顶的元素的那个值穿小鞋呀，栈顶元素的index，正好满足elementCount - index - 1=0的操作；这不明摆着吗 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 */ } empty方法
判断栈是否为空
public boolean empty() { return size() == 0; } search方法
public synchronized int search(Object o) { int i = lastIndexOf(o); if (i >= 0) { //栈的排序和数组的下标值顺序是反的 return size() - i; } return -1; } public synchronized int lastIndexOf(Object o) { //o元素的值；elementCount-1元素索引的大小 return lastIndexOf(o, elementCount-1); } public synchronized int lastIndexOf(Object o, int index) { //判断索引是否合理 if (index >= elementCount) throw new IndexOutOfBoundsException(index + " >= "+ elementCount);//如果对象的值是空的 if (o == null) { //c从栈顶开始遍历 for (int i = index; i >= 0; i--） if (elementData[i]==null) return i; } else { //判断内容是否相等 for (int i = index; i >= 0; i--) if (o.equals(elementData[i])) return i; } return -1; } 接下来，我们就开始学习Map了，它会比这个要麻烦；
但是难啃的骨头才是香的嘛；
转载地址：http://nqqoz.baihongyu.com/
你可能感兴趣的文章