java基础-数组扩容详解

数组与链表的比较：

数组通过下标访问的话是O(1)
数组一旦声明长度就是固定的
数组的数据是物理逻辑均连续的
链表增删要快一些, 数组遍历快一些
长度一定的话，数组的存储空间比链表要小

ArrayList：

ArrayList是List接口的实现类，它是支持根据需要而动态增长的数组；java中标准数组是定长的，在数组被创建之后，它们不能被加长或缩短。这就意味着在创建数组时需要知道数组的所需长度，但有时我们需要动态程序中获取数组长度。ArrayList就是为此而生的。

扩容机制发生在add()方法调用的时候；

				?

									public boolean add(E e) {

									     //扩容

									      ensureCapacityInternal(size + 1);  // Increments modCount!!

									      elementData[size++] = e;

									      return true;

									  }

该行代码ensureCapacityInternal()是用来扩用的，形参是最小扩容量，进入该方法后：

				?

									private void ensureCapacityInternal(int minCapacity) {

									    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));

									}

通过方法calculateCapacity(elementData, minCapacity)获取:

				?

									private static int calculateCapacity(Object[] elementData, int minCapacity) {

									     //如果传入的是个空数组则最小容量取默认容量与minCapacity之间的最大值

									     if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {

									         return Math.max(DEFAULT_CAPACITY, minCapacity);

									     }

									     return minCapacity;

									 }

使用 ensureExplicitCapacity方法可以判断是否需要扩容：

				?

									private void ensureExplicitCapacity(int minCapacity) {

									         modCount++;

									         // 如果最小需要空间比elementData的内存空间要大，则需要扩容

									         if (minCapacity - elementData.length > 0)

									             //扩容

									             grow(minCapacity);

									     }

需要扩容，进入ArrayList扩容的关键方法grow():扩大为原来的1.5倍；

				?

									private void grow(int minCapacity) {

									          // 获取到ArrayList中elementData数组的内存空间长度

									          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);

									         // 调用Arrays.copyOf方法将elementData数组指向新的内存空间时newCapacity的连续空间

									         // 并将elementData的数据复制到新的内存空间

									         elementData = Arrays.copyOf(elementData, newCapacity);

									     }

									复制代码

至此得出ArrayList扩容的本质是计算出新的扩容数组的size后实例化，并将原有数组内容复制到新数组中去。

LinkedList：

链表实现扩容，直接在尾指针后面加入新的元素即可。

实现LinkedList:LinkedList的底层实现是链表。更深理解是一个双向链表。

节点代码：

				?

									//节点

									public class Node {

									    Node previous;//前继，指向前一个Node

									    Object data;//节点数据

									    Node next;//后继，指向后一个Node

									    public Node() {

									    }

									    public Node(Node previous, Object data, Node next) {

									        super();

									        this.previous = previous;

									        this.data = data;

									        this.next = next;

									    } 

									}

初始化MyLinkedList:

				?

									public class MyLinkedList {

									    private Node first;//首节点

									    private Node last;//尾节点

									    private int size;//链表大小

									    public MyLinkedList() {

									        first = null;

									        last = null;

									        size = 0;

									    }

									}

尾部添加，实现add(Object obj)方法：

				?

									public void add(Object obj){

									        Node node = new Node(null,null,null);

									        if(first==null){//first=null,说明LinkedList中没有一个节点

									            node.data = obj;

									            first = node;

									            last = node;//第一个节点和最后一个节点都是node

									            size++;

									        }else{

									            node.data = obj;

									            last.next = node;//和最后一个连接起来

									            node.previous = last;

									            last = node;//当前节点变为末尾节点

									            size++;

									        }

现get(int index)方法，获取index处的节点并返回Node:

使用循环，遍历链表：

				?

									public Node get(int index) {

									        RangeCheck(index);

									        Node temp = null;

									        if(index < (size>>1)){//改进的遍历方法，右移运算符的巧用

									            temp = first;

									            for(int i=0;i<index;i++){

									                temp = temp.next;

									            }

									        }else {

									            temp = last;

									            for(int i=size-1;i>index;i--){

									                temp = temp.previous;

									            }

									        }

									        return temp;

									    }

任意位置插入，实现add(int index,Object obj)方法：插入的步骤注意顺序，不要产生断链。

				?

									public void add(int index,Object obj) {

									        RangeCheck(index);//对传入的索引必须进行检查，判断是否越界

									        Node node = new Node(null,null,null);

									        node.data = obj;

									        Node node2=first;

									        for(int i=0;i<index-1;i++){

									            node2 = node2.next;

									        }

									        node.next = node2.next;

									        node2.next.previous=node;

									        node2.next = node;

									        node.previous=node2;

									        size++;

									    }

RangeCheck():

				?

									private void RangeCheck(int index) {

									        if(index<0||index >= size){

									            throw new IndexOutOfBoundsException("IndexOutOfBounds"+index);//不合法则抛出异常

									        }

									    }

实现remove(Object obj)方法：

				?

									public boolean remove(Object obj) {

									        Node node = first;

									        if(obj==null){

									            while(node!=null){

									                if(node.data==null){

									                    removefast(node);

									                    return true;

									                }

									                node = node.next;

									            }

									        }else {

									            while(node!=null){

									                if(obj.equals(node.data)){

									                    removefast(node);

									                    return true;

									                }

									                node = node.next;

									            }

									        }

									        return false;

									    }

									    private void removefast(Node node){

									        node.previous.next=node.next;

									        size--;

									        node.data=null;

									        node.previous = node.next = null;

									    }

实现set(int index,Object obj)方法：

				?

									public Object set(int index,Object obj) {

									        Node node = get(index);

									        Object oldObject=node.data;

									        node.data = obj;

									        return oldObject;

									    }