专栏首页Liusy01List源码解析

List源码解析

开始看一下集合Collection,List是Collection的一个子接口,其是很常用的,主要是看一下其下的几个类。

1、AbstractList

2、ArrayList

3、Collections.synchronizedList

4、Vector

5、LinkedList

6、CopyOnWriteArrayList

一、AbstractList

这是一个抽象类,其是实现List接口基础类,像ArrayList、LinkedList和Vector都是继承此抽象类的。

1》如果要实现一个不可变的列表,必须实现get(int) 和size()方法

2》如果要实现一个可修改的列表,必须实现set(int,E),如果列表大小可变,必须另外实现add(int,E)和remove(int)方法

其内置了两个迭代器,是Itr和ListItr,继承关系如下

(1)Itr

private class Itr implements Iterator<E> {
    //游标
    int cursor = 0;
    
    //调用next方法时当前的下标索引值
    //,如果调用了remove方法,则重置为-1  
    int lastRet = -1;

    //列表被修改的次数,比如增、删、改、扩容等操作
    int expectedModCount = modCount;
    //是否还有元素
    public boolean hasNext() {
        return cursor != size();
    }
    //返回下一个元素
    public E next() {
        checkForComodification();
        try {
            int i = cursor;
            //get方法是调用具体实现类的
            E next = get(i);
            lastRet = i;
            cursor = i + 1;
            return next;
        } catch (IndexOutOfBoundsException e) {
            checkForComodification();
            throw new NoSuchElementException();
        }
    }
    //删除当前元素 
    public void remove() {
        if (lastRet < 0)
            throw new IllegalStateException();
        checkForComodification();
        try {
            AbstractList.this.remove(lastRet);
            if (lastRet < cursor)
                cursor--;
            lastRet = -1;
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException e) {
            throw new ConcurrentModificationException();
        }
    }
    //检查迭代的时候列表结构是否有被其他线程修改过 
    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

(2)ListItr

private class ListItr extends Itr implements ListIterator<E> {
    ListItr(int index) {
        cursor = index;
    }

    public boolean hasPrevious() {
        return cursor != 0;
    }
    //返回前一个元素
    public E previous() {
        checkForComodification();
        try {
            int i = cursor - 1;
            E previous = get(i);
            lastRet = cursor = i;
            return previous;
        } catch (IndexOutOfBoundsException e) {
            checkForComodification();
            throw new NoSuchElementException();
        }
    }

    public int nextIndex() {
        return cursor;
    }

    public int previousIndex() {
        return cursor-1;
    }
    //设值
    public void set(E e) {
        if (lastRet < 0)
            throw new IllegalStateException();
        checkForComodification();
        try {
            AbstractList.this.set(lastRet, e);
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }
    //添加元素
    public void add(E e) {
        checkForComodification();
        try {
            int i = cursor;
            AbstractList.this.add(i, e);
            lastRet = -1;
            cursor = i + 1;
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }
}

这两个迭代器在indexOf、lastIndexOf和removeRange方法中有调用

例如removeRange方法

protected void removeRange(int fromIndex, int toIndex) {
    //获取迭代器,fromIndex就是Itr里面的cursor 
    ListIterator<E> it = listIterator(fromIndex);
    for (int i=0, n=toIndex-fromIndex; i<n; i++) {
        it.next();
        it.remove();
    }
}

public ListIterator<E> listIterator(final int index) {
    rangeCheckForAdd(index);
    return new ListItr(index);
}

private class ListItr extends Itr implements ListIterator<E> {
        ListItr(int index) {
            cursor = index;
        }
}

二、ArrayList

这个列表是最常用的,继承自AbstractList,非线程安全,多线程下会抛出ConcurrentModificationException

(1)默认容量是10

 private static final int DEFAULT_CAPACITY = 10;

(2)底层数据结构是一个Object数组

transient Object[] elementData;

(3)扩容机制为扩容为当前容量的1.5倍,看add方法

public boolean add(E e) {
      //关键就是方法 
      ensureCapacityInternal(size + 1);  
      elementData[size++] = e;
      return true;
  }

扩容看ensureCapacityInternal方法

private void ensureCapacityInternal(int minCapacity) {
      ensureExplicitCapacity(
          calculateCapacity(elementData, minCapacity)
        );
  }

先看calculateCapacity方法

private static int calculateCapacity(Object[] elementData, int minCapacity) { 
      if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
          return Math.max(DEFAULT_CAPACITY, minCapacity);
      }
      return minCapacity;
 }

如果创建列表时没有指定大小,就从minCapacity和默认容量两个数中取最大。否则直接返回minCapacity

private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
        //如果minCapacity大于当前数组长度,则进行扩容
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

扩容最核心的方法是grow(minCapacity)方法。

private void grow(int minCapacity) {

    //当前容量
    int oldCapacity = elementData.length;
    //新容量,是当前容量的1.5倍 
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    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);
}

可以看到,扩容后容量为当前容量的1.5倍

三、Collections.synchronizedList

用Collections获取的这个List是线程安全的,其都是用synchronized关键字在代码块上进行加锁的。具体初始容量以及扩容看传入的是哪种List

返回的list是SynchronizedRandomAccessList或者是SynchronizedList,而SynchronizedRandomAccessList又是SynchronizedList的子类

所以主要看SynchronizedList,可以看到,这个类的所有方法都是用Synchronized加锁的。

四、Vector

Vector比较少用,其也是AbstractList的子类。

(1)默认容量,也是10

public Vector() {
    //调用另外一个构造方法  
    this(10);
}

上述默认空构造调用下面这个构造方法,其将capacityIncrement设为0,这个在扩容时有用

也可以用下面这个构造初始化容量和capacityIncrement

(2)底层数据结构是一个Object数组

protected Object[] elementData;

(3)扩容机制默认是2倍,也可以手动设置capacityIncrement扩容

(4)线程安全,用Synchronized在方法上加锁

五、LinkedList

这个链表结构如下,除了继承了AbstractList,还实现了Queue。

(1)底层实现是一个一个Node节点,节点中存有前后节点的引用,能连成一条链

六、CopyOnWriteArrayList

这个就比较牛逼了,中文名叫写时复制。属于JUC并发包里面的,线程安全,是ArrayList的变体。

(1)初始化是容量为0的Object数组

public CopyOnWriteArrayList() {
    setArray(new Object[0]);
}

这个数组是用volatile,保证变量内存可见性。

 private transient volatile Object[] array;

(2)用ReentrantLock(递归锁,又称可重入锁)加锁,扩容为添加一次就容量加1,然后用Arrays.copyOf将旧的数组复制到新数组内,比较耗内存。

本文分享自微信公众号 - Liusy01(Liusy_01),作者:Liusy01

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-01-03

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【设计模式-工厂相关模式】

    定义一个创建对象的接口,但让实现这个接口的类来决定实例化哪个类,工厂方法让类的实例化推迟到子类中进行。

    Liusy
  • 【设计模式-适配器模式】

    【导读】如果多样东西需要使用同一件物品,则需要进行适配,比如只有一个电源插口,但有多个需要用电的(有三相插头,有二相插头),此时就需要一个排查器进行适配,使三相...

    Liusy
  • 初识Kubernetes及快速安装

    之前几篇介绍了Docker是什么以及怎么使用,但Docker只是容器管理工具,如果想要在Docker上部署大型应用,首先就是要解决网络的问题,还有一系列复杂的问...

    Liusy
  • LWC 109: 933.Number of Recent Calls

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • JAVA通过BufferedImage进行图片的绘制,缩放,裁剪,水印等操作

    最近开发当中,通过JAVA对图片进行了很多的操作,之前很少接触这方面的知识,特此记录下来

    海加尔金鹰
  • leetcode398. Random Pick Index

    设计一个数据结构,使得从该数据结构中查询一个数字时,能够以等概率返回该数字所在的任何下标。额外的要求是只要占用O(1)的额外的空间复杂度。

    眯眯眼的猫头鹰
  • LeetCode 137 Single Number II

    ShenduCC
  • Dimple在左耳听风ARTS打卡(第一期)

    参加了左耳听风的ARTS打卡,坚持一个月,对自己会有什么情况呢,我不知道,但我会照着这个目标坚持下去,坚持100天。一个习惯养成是21天,那如果坚持100天,效...

    程序员小跃
  • 快速排序

    快速排序思想:如果要排数组p到r之间的一组数据,选择p到r之间任意一个一个数据作为pivot(分区点,这里选择的是s[r]作为pivot)。遍历p到r之间的数据...

    用户2937493
  • C++创建动态库C#调用(二)----回调函数的使用

    上一篇《C++创建动态库C#调用》我们练习了C++写的动态库用C#的调用方法,后来研究回调函数这块,就想练习一下回调函数的使用,学习并巩固一下,话不多说,我们直...

    Vaccae

扫码关注云+社区

领取腾讯云代金券