服务器之家:专注于服务器技术及软件下载分享
分类导航

PHP教程|ASP.NET教程|Java教程|ASP教程|编程技术|正则表达式|C/C++|IOS|C#|Swift|Android|VB|R语言|JavaScript|易语言|vb.net|

服务器之家 - 编程语言 - Java教程 - java基础-数组扩容详解

java基础-数组扩容详解

2021-11-29 11:36haijiao12138 Java教程

这篇文章主要介绍了Java数组扩容实现方法解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下

数组与链表的比较:

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

ArrayList:

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

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

?
1
2
3
4
5
6
public boolean add(E e) {
     //扩容
      ensureCapacityInternal(size + 1);  // Increments modCount!!
      elementData[size++] = e;
      return true;
  }

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

?
1
2
3
private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

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

?
1
2
3
4
5
6
7
private static int calculateCapacity(Object[] elementData, int minCapacity) {
     //如果传入的是个空数组则最小容量取默认容量与minCapacity之间的最大值
     if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
         return Math.max(DEFAULT_CAPACITY, minCapacity);
     }
     return minCapacity;
 }

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

?
1
2
3
4
5
6
7
private void ensureExplicitCapacity(int minCapacity) {
         modCount++;
         // 如果最小需要空间比elementData的内存空间要大,则需要扩容
         if (minCapacity - elementData.length > 0)
             //扩容
             grow(minCapacity);
     }

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

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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的底层实现是链表。更深理解是一个双向链表。

节点代码:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
//节点
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:

?
1
2
3
4
5
6
7
8
9
10
public class MyLinkedList {
    private Node first;//首节点
    private Node last;//尾节点
    private int size;//链表大小
    public MyLinkedList() {
        first = null;
        last = null;
        size = 0;
    }
}

尾部添加,实现add(Object obj)方法:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
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:

使用循环,遍历链表:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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)方法:插入的步骤注意顺序,不要产生断链。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
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():

?
1
2
3
4
5
private void RangeCheck(int index) {
        if(index<0||index >= size){
            throw new IndexOutOfBoundsException("IndexOutOfBounds"+index);//不合法则抛出异常
        }
    }

实现remove(Object obj)方法:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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)方法:

?
1
2
3
4
5
6
public Object set(int index,Object obj) {
        Node node = get(index);
        Object oldObject=node.data;
        node.data = obj;
        return oldObject;
    }

总结

本篇文章就到这里了,希望能给你带来帮助,也希望您能够多多关注服务器之家的更多内容!

原文链接:https://blog.csdn.net/qq_40604313/article/details/118683783

延伸 · 阅读

精彩推荐