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

PHP教程|ASP.NET教程|JAVA教程|ASP教程|编程技术|

服务器之家 - 编程语言 - JAVA教程 - Java ArrayList 实现实例讲解

Java ArrayList 实现实例讲解

2020-06-30 11:05有女朋友的程序猿 JAVA教程

ArrayList是基于数组实现的,是一个动态数组,其容量能自动增长,类似于C语言中的动态申请内存,动态增长内存。这篇文章主要介绍了java ArrayList 实现的相关资料,需要的朋友可以参考下

 ArrayList概述: 

ArrayList是基于数组实现的,是一个动态数组,其容量能自动增长,类似于C语言中的动态申请内存,动态增长内存。

    ArrayList不是线程安全的,只能用在单线程环境下,多线程环境下可以考虑用Collections.synchronizedList(List l)函数返回一个线程安全的ArrayList类,也可以使用concurrent并发包下的CopyOnWriteArrayList类。

    ArrayList实现了Serializable接口,因此它支持序列化,能够通过序列化传输,实现了RandomAccess接口,支持快速随机访问,实际上就是通过下标序号进行快速访问,实现了Cloneable接口,能被克隆。

   每个ArrayList实例都有一个容量,该容量是指用来存储列表元素的数组的大小。它总是至少等于列表的大小。随着向ArrayList中不断添加元素,其容量也自动增长。自动增长会带来数据向新数组的重新拷贝,因此,如果可预知数据量的多少,可在构造ArrayList时指定其容量。在添加大量元素前,应用程序也可以使用ensureCapacity操作来增加ArrayList实例的容量,这可以减少递增式再分配的数量。 

   注意,此实现不是同步的。如果多个线程同时访问一个ArrayList实例,而其中至少一个线程从结构上修改了列表,那么它必须保持外部同步。

下面对java arraylist做一个记录和总结吧

?
1
2
3
4
5
6
7
8
public class arraylist<E> {
  /**
   * 存放集合的元素
   *
   */
  private transient Object[] elementData;
  /** 元素的大小 */
  private int size;

定义了一个泛型类,一个object的数组和一个私有变量来记录该集合的元素数量,原文多了一个私有变量,我也不知道干嘛用的,作者也没解释也没提及到,我没使用也没事

?
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
28
29
30
31
32
33
/**
   * 根据指定大小初始化
   * @param initialCapacity
   */
  public arraylist(int initialCapacity){
    super();
    if(initialCapacity<=0){
      //抛异常
      throw new IllegalArgumentException("初始化参数不能小于0");
    }else{
      //初始化数组
      this.elementData=new Object[initialCapacity];
    }
  }
  /**
   * 默认初始化
   */
  public arraylist(){
    this(10);
  }
  /**
   * 根据一个集合类初始化
   * @param c 一个必须继承了Collection接口的类
   */
  public arraylist(Collection<? extends E> c){
    //初始化
    elementData=c.toArray();
    size=elementData.length;
    //如果不是任意类型的数组就转换Objec类型
    if (elementData.getClass() != Object[].class){
      elementData=Arrays.copyOf(elementData,size, Object[].class);
    }
  }

3个初始化方法,根据默认大小进行数组的初始化,给定大小初始化和传递一个继承了Collection集合接口的类进行转换赋值初始化

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
   * 扩容集合
   * @param minCapacity
   */
  public void ensureCapacity(int minCapacity){
    /** 当前数组的大小 */
    int oldCapacity = elementData.length;
    if (minCapacity > oldCapacity) {
      /**
       * oldData 虽然没有被使用,但是这是关于内存管理的原因和Arrays.copyOf()方法不是线程安全
       * oldData在if的生命周期内引用elementData这个变量,所以不会被GC回收掉
       * 当Arrays.copyOf()方法在把elementData复制到newCapacity时,就可以防止新的内存或是其他线程分配内存是elementData内存被侵占修改
       * 当结束是离开if,oldData周期就结束被回收
       */
      Object oldData[] = elementData;
      int newCapacity = (oldCapacity * 3)/2 + 1; //增加50%+1
        if (newCapacity < minCapacity)
          newCapacity = minCapacity;
     //使用Arrays.copyOf把集合的元素复制并生成一个新的数组
     elementData = Arrays.copyOf(elementData, newCapacity);
    }
  }

这是一个核心的方法,集合的扩容,其实是对数组的扩容,minCapacity集合的大小,进行对比判断是否应该进行扩容,使用了Arrays.copyOf()方法进行扩容,

原文有进行详细的解释,这个方法把第一个参数的内容复制到一个新的数组中,数组的大小是第二个参数,并返回一个新的数组,关于oldData的变量上文有详细的注释

?
1
2
3
4
5
6
7
8
9
/**
  * 检查索引是否出界
  * @param index
  */
 private void RangeCheck(int index){
   if(index > size || index < 0){
     throw new IndexOutOfBoundsException("下标超出,Index: " + index + ", Size: " +size);
   }
 }

一个下标的检索是否出 1 /**

?
1
2
3
4
5
6
7
8
9
10
11
* 添加元素
   * 将指定的元素添加到集合的末尾
   * @param e 添加的元素
   * @return
   */
  public boolean add(E e){
    ensureCapacity(size+1);
    elementData[size]=e;
    size++;
    return true;
  }

添加元素,先进行扩容,在赋值,然后元素加一,注意 size+1 字段size并没有加一,这里进行的是算术的运算,所以在后面才需要进行自增

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
   * 添加元素
   * 将元素添加到指定的位置
   * @param index 指定的索引下标
   * @param element 元素
   * @return
   */
  public boolean add(int index, E element){
    RangeCheck(index);
    ensureCapacity(size+1);
    // 将 elementData中从Index位置开始、长度为size-index的元素,
    // 拷贝到从下标为index+1位置开始的新的elementData数组中。
    // 即将当前位于该位置的元素以及所有后续元素右移一个位置。
    System.arraycopy(elementData, index, elementData, index+1, size-index);
    elementData[index]=element;
    size++;//元素加一
    return true;
  }

这里不同的是 System.arraycopy(elementData, index, elementData, index+1, size-index);

这是一个c的内部方法,详细的原文有解释,这里就不说了,这个也是整个ArrayList的核心所在,也Arrays.copyOf()的内部实现原理

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
   * 添加全部元素
   * 按照指定collection的迭代器所返回的元素顺序,将该collection中的所有元素添加到此列表的尾部。
   * @param c
   * @return
   */
  public boolean addAll(Collection < ? extends E>c){
    Object[] newElement=c.toArray();
    int elementLength=newElement.length;
    ensureCapacity(size+elementLength);
    //从newElement 0的下标开始,elementLength个元素,elementData size的下标
    System.arraycopy(newElement, 0, elementData, size, elementLength);
    size+=elementLength;
    return elementLength!=0;
  }

基本上其他方法都只是根据不同的情况进行不同的处理,比如通过接口把数据对象传递进来然后获取长度进行扩容,在把数据使用System,arraycopy复制到新的数组中

?
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
/**
   * 指定位置,添加全部元素
   * @param index 插入位置的下标
   * @param c 插入的元素集合
   * @return
   */
  public boolean addAll(int index, Collection<? extends E> c){
    if(index > size || index < 0){
      throw new IndexOutOfBoundsException("Index: " + index + ", Size: " +size);
    }
    Object[] newElement=c.toArray();
    int elementLength=newElement.length;
    ensureCapacity(size+elementLength);
    int numMoved=size-index;
    //判断插入的位置是否在数组中间
    if(numMoved>0){
      //把index插入位置的后面的所有元素往后移
      //elementData index下标开始的numMoved个元素插入到elementData 的index+elementLength位置
      System.arraycopy(elementData, index, elementData, index+elementLength, numMoved);
    }
    //把newElement里从0开始的elementLength个元素添加到elementData index开始的位置
    System.arraycopy(newElement, 0, elementData, index, elementLength);
    size += elementLength;
    return elementLength != 0;
  }
  
  /**
   * 指定下标赋值
   * @param index
   * @param element
   * @return
   */
  public E set(int index,E element){
    RangeCheck(index);
    E oldElement=(E)elementData[index];
    elementData[index]=element;
    return oldElement;
  }
  
  /**
   * 根据下标取值
   * @param index
   * @return
   */
  public E get(int index){
    RangeCheck(index);
    return (E)elementData[index];
  }
  
  /**
   * 根据下标移除元素
   * @param index
   */
  public E remove(int index){
    RangeCheck(index);
    E oldElement=(E)elementData[index];
    /** 移除的下标后面的元素数量 */
    int numMoved=size-index-1;
    //如果在数组范围内就进行移动
    if(numMoved>0)
      System.arraycopy(elementData, index+1, elementData, index, numMoved);
    //移除
    elementData[--size]=null;
    return oldElement;
  }
  
  /**
   * 根据元素移除
   * @param obj
   * @return
   */
  public boolean remove(Object obj){
    //Arraylist允许存放null,所以也要进行判断处理
    if(obj==null){
      for(int index=0;index<size;index++){
        if(elementData[index]==null){
           remove(index);
           return true;
        }
      }
    }else{
      for(int index=0;index<size;index++){
        if(obj.equals(elementData[index])){
           remove(index);
           return true;
        }
      }
    }
    return false;
  }
  
  /**
   * 根据下标移除指定范围内的元素
   * @param fromIndex 开始
   * @param toIndex 结束
   */
  protected void removeRange(int fromIndex, int toIndex){
    RangeCheck(fromIndex);
    RangeCheck(toIndex);
    //要移动的元素数
    int numMoved = size - toIndex;
    //把toIndex后面的元素移动到fromIndex
    System.arraycopy(elementData, toIndex, elementData, fromIndex, numMoved);
    //要移除的元素数量
    int newSize=size-(toIndex-fromIndex);
    while(size!=newSize){
      elementData[--size]=null;
    }
  }
  
  /**
   * 把数组容量调整到实际的容量
   */
  public void trimToSize(){
    int leng=elementData.length;
    if(size<leng){
      Object[] old=elementData;
      elementData=Arrays.copyOf(elementData, size);
    }
  }
  /**
   * 把集合元素转换成数组
   * @return
   */
  public Object[] toArray(){
    return Arrays.copyOf(elementData, size);
  }
  
  public <T>T[] toArray(T[] a){
    if(a.length<size){
      return (T[]) Arrays.copyOf(elementData,size, a.getClass());
    }
    //把集合元素复制到a数组中
    System.arraycopy(elementData, 0, a, 0, size);
     if (a.length > size){
       for(int index=size;index<a.length;index++){
         a[index] = null;
       }
     }
     return a;
  }

基本上都是对数组进行操作和使用c的方法进行赋值移动等,详细的可以查看原文,原文中除了那个私有变量外也没多少问题,代码可以完美运行,这李要注意的和难点就会是System,arraycopy和Arrayist.copy()这2个方法
和在扩容方法里oldData这个变量的使用,这个变量真的很好,一开始我也不知道为什么要这么使用,在原文的末尾会进行解释。

以上所述是小编给大家介绍的Java ArrayList 实现实例讲解,希望对大家有所帮助,如果大家有任何疑问欢迎给我留言,小编会及时回复大家的,在此也非常感谢大家对服务器之家网站的支持!

原文链接:http://www.cnblogs.com/xiaohuihui96/archive/2016/11/03/6025102.html

延伸 · 阅读

精彩推荐