java基础-数组扩容详解

• arraylist：
• linkedlist：

数组与链表的比较：

• 数组通过下标访问的话是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;
	}

总结

本篇文章就到这里了，希望能给你带来帮助，也希望您能够多多关注的更多内容！