java中List集合底层理解，ArrayList的扩容机制

java中List集合底层理解，ArrayList的扩容机制

1 、 先看看List、Set集合的 继承结构图

• 实现了Collection接口，可以实现Collection中的方法
• 主要的实现列有ArrayList、Vector、LinkedList

特点

• 添加顺序和取出顺序是一致的
• 每个元素都有其对应的索引

List集合的常用方法8个

1. add 添加
2. addAll 添加全部
3. get(int index) 取出指定索引的元素
4. indexOf（返回集合 中首次出现的位置）
5. lastIndexOf （返回集合 中最后一次出现的元素的位置/索引）
6. remove 移除，是从第一个元素开始，可以指定索引
7. set （int index, Object element）设置
8. subList(int fromIndex, int toIndex) 返回fromIndex到toIndex的子集合

ArrayList等同于Vector ，线程不安全，线程安全

ArrayList底层扩容机制

• 维护了一个transient 修饰的 Object类型的elementData[ ]数组，transient关键字表示这个数组不可被序列化。 Object类型表示可以存储任意数据类型

• 补充一点：序列化是什么？

  将数据或对象转换成二进制字节流的过程

  blog.csdn.net/weixin_4555… 这篇文章关于序列化的详细说明，说的很好

      public ArrayList() {
          this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
      }
      
      // non-private to simplify nested class access
      transient Object[] elementData; 
  
  

• 扩容机制，如果调用的是无参构造器，创建的就是一个空数组，当插入数据时，扩容大小为10，第二次扩容大小为原来的1.5倍。

• 如果调用了是有参构造，指定了容量大小，那么初始容量就是指定的大小，扩容为容量大小的 1.5倍

第一次扩容

• DEFAULT_CAPACITY = 10；

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    ensureExplicitCapacity(minCapacity);
}

再次扩容，或者是传参之后的扩容都是走这边的底层源码：使用的是Arrays.copyOf（）方法，Arrays.copyOf会保留原来的数据进行拷贝

    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        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);
    }

Vector

• 注意Vector的扩容倍数不同，底层极致都相差不大~

LinkedList 底层结构

1. LinkedList底层维护了一个双向链表
2. LinkedList中维护了两个属性first和last分别指向首节点和尾节点
3. 每个节点(Node对象)，里面又维护了prev、next、item三个属性，其中通过prev指向前一个,通过next指向后一个节点。最终实现双向链表.
4. 所以LinkedList的元素的添加和删除，不是通过数组完成的，相对来说效率较高。

一个简单的双向列表

public class LinkedListTest {
    public static void main(String[] args) {
        Node ll = new Node("老李");
        Node lzq = new Node("lzq");
        Node aq = new Node("阿强");

        // 连接两个节点，形成双向链表
        // ll->lzq->aq
        ll.next = lzq;
        lzq.next=aq;

        // lzq->aq-ll
        aq.pre=lzq;
        lzq.pre=ll;

        Node first=  ll;
        Node last = aq;

        System.out.println("前往后进行遍历~");
        while (true) {
            if(first ==null) {
                break;
            }
            System.out.println(first);
            first = first.next;
        }
        System.out.println("后往前进行遍历~");
        while (true) {
            if(last ==null) {
                break;
            }
            System.out.println(last);
            last = last.pre;
        }

        Node smith = new Node("smith");
        smith.next=aq;
        smith.pre=lzq;
        lzq.next=smith;
        aq.pre= smith;

        // 让first再次指向ll
        first = ll;
        System.out.println("插入之后，前往后进行遍历~");
        while (true) {
            if(first ==null) {
                break;
            }
            System.out.println(first);
            first = first.next;
        }
    }
}
class Node {
    public Object item;  //真正存放数据
    public Node next; // 指向后一个结点
    public Node pre; // 指向前一个结点
    public Node(Object name) {
        this.item = name;
    }
    @Override
    public String toString() {
        return "Node{" +
                "item=" + item +
                '}';
    }
}

运行结果

前往后进行遍历~
Node{item=老李}
Node{item=lzq}
Node{item=阿强}
后往前进行遍历~
Node{item=阿强}
Node{item=lzq}
Node{item=老李}
插入之后，前往后进行遍历~
Node{item=老李}
Node{item=lzq}
Node{item=smith}
Node{item=阿强}

ArrayList与LinkedList的比较与使用

	底层结构	增删效率	改查效率
ArrayList	可变数组 Object elementData[ ]	较低、数组扩容	较高
LinkedList	双向链表	较高、通过来链表追加	较低

ArrayList与LinkedList如何选择使用

1. 如果我们改查的操作多，选择ArrayList
2. 如果我们增删的操作多，选择LinkedList
3. 一般来说，在程序中，80%-90%都是查询，因此大部分情况下会选择ArrayList
4. 在一个项目中，根据业务灵活选择，也可能这样，一个模块使用的是ArrayList,另外一个模块是LinkedList.