avatar
文章
40
标签
36
分类
18
主页
时间轴
标签
类别
友链
娱乐
关于
Hobo's blog
主页
时间轴
标签
类别
友链
娱乐
关于
手写ArrayList（仿照源码）
|Java基础
字数总计:2k|阅读时长: 8 分钟
|阅读量:|评论数:

ArrayList简述

ArrayList底层使用的是数组，相对于LinkeList来说查询修改快，增删慢，适用于查询较多的场景。非线程安全。

  1. List 接口： List是Collection的子接口，它是一个元素有序(按照插入的顺序维护元素顺序)、可重复、可以为null的集合
  2. AbstractList 类： List接口的骨架实现类，最小化实现了List接口所需要实现的工作量
  3. 实现了Cloneable接口，即覆盖了函数clone()，能克隆;
  4. 实现了Cloneable接口，实现了该接口标示了类可以被序列化和反序列化
  5. RandomAccess 接口，实现了该接口的类支持快速随机访问

手写实现

定义属性

1
2
3
4
5
6
7
8
9
public class MyArrayList<E> {
    //初始容量
    private static final int DEFAULT_CAPACITY = 10;
    //初始的数组（空数组）
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    //底层数组
    Object[] elementData;
    //包含的元素个数
    private int size;

增删改查方法

插入

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
/**
     * 添加元素
     *
     * @param e
     * @return
     */
    public boolean add(E e) {
        //是否对数组进行扩容
        ensureCapacityInternal(size + 1);
        //此时数组长度已扩容或长度够不需要扩容
        elementData[size++] = e;
        return true;
    }

    /**
     * 确保内部容量
     * 判断数组的容量，小于minCapacity就进行扩容1.5倍
     *
     * @param minCapacity
     */
    private void ensureCapacityInternal(int minCapacity) {
        //如果是空数组则 minCapacity = 10
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        if (minCapacity - elementData.length > 0) {
            //原数组容量
            int oldCapacity = elementData.length;
            //扩容为之前的1.5倍（扩容因子为1.5）
            int newCapacity = oldCapacity + (oldCapacity >> 1);
            //如果新容量 小于 最小容量，则新容量 = 最小容量
            if (newCapacity - minCapacity < 0) {
                newCapacity = minCapacity;
            }
            //ArrayList最大数组长度为Integer.MAX_VALUE - 8
            if (newCapacity > (Integer.MAX_VALUE - 8)) {
                // overflow
                if (minCapacity < 0) {
                    throw new OutOfMemoryError();
                }
                newCapacity = (minCapacity > Integer.MAX_VALUE - 8) ? Integer.MAX_VALUE : Integer.MAX_VALUE - 8;
            }
            //创建新长度的数组，并将原数组数据赋值给新数组
            elementData = Arrays.copyOf(elementData, newCapacity);
        }
    }

    /**
     * 添加元素至索引处，索引处和其之后的元素全部后挪一位
     *
     * @param index
     * @param element
     * @return
     */
    public E add(int index, E element) {
        //检查index是否合法
        if (index > size || index < 0) {
            throw new IndexOutOfBoundsException("index不合法+ index:" + index + ",size:" + size);
        }
        //是否需要扩容,true->扩容
        ensureCapacityInternal(size + 1);
        //size-(index+1)+1
        System.arraycopy(elementData, index, elementData, index + 1, size - index);
        return null;
    }

    public void addAll(Collection<? extends E> e) {
    	//将集合e中的元素放到数组中
        Object[] a = e.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);
        //将新数组添加到底层数组的尾部
        System.arraycopy(a,0,elementData,size,numNew);
        size +=numNew;
    }

查询

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
* 根据索引查询（数组的随机查询，效率高）
* @param index
* @return
*/
public E get(int index) {
        //检查index是否合法（是否越界）
        rangeCheck(index);
        return (E) elementData[index];
        //返回查询的元素
    }

/**
 * 检查给定索引是否在数组的有效范围内
 *
 * @param index
 */
private void rangeCheck(int index) {
    if (index >= size) {
        throw new IndexOutOfBoundsException("index不合法！！index:" + index + ",size:" + size);
    }
}

修改

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
    * 根据索引修改元素
    * @param index
    * @param element
    * @return
    */
   public E set(int index, E element) {
       //检查index是否合法（是否越界）
       rangeCheck(index);
       E oldValue = (E) elementData[index];
       elementData[index] = element;
       return oldValue;
   }

删除

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
/**
    * 根据索引删除元素，并将其之后的元素向前移一位
    * @param index
    * @return
    */
   public E remove(int index) {
       rangeCheck(index);
       E oldValue = (E) elementData[index];
       //要改变下标的元素个数 size-（index+1）
       int numMoved = size - index - 1;
       if (numMoved > 0) {
           //从elementData数组的下标index+1开始，覆盖到从elementData数组的下标index的位置
           System.arraycopy(elementData, index + 1, elementData, index, numMoved);
       }
       //尾部的元素设置为null，size先-- 再使用
       elementData[--size] = null;
       return oldValue;
   }
/**
    * 根据元素删除，遍历数组找到第一个于 o == 的元素 获取他的索引将其删除
    * @param o
    * @return
    */
   public boolean remove(Object o) {
       if (o == 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 (o.equals(elementData[index])) {
                   remove(index);
                   return true;
               }
           }
       }
       return false;
   }

实现代码

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
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
package com.clh.test.mylist;

import java.util.*;

/**
 * 手写ArrayList，底层是数组（Array），在查询大量数据时for遍历效率大于Iterator
 * 特点：查询快，增删慢 线程不安全 效率高
 *
 * @author 华华
 * @date 2020/4/29
 **/
public class MyArrayList<E> {

    /**
     * 初始容量
     */
    private static final int DEFAULT_CAPACITY = 10;

    /**
     * 初始的数组（空数组）
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**
     * 底层数组
     */
    Object[] elementData;

    /**
     * 包含的元素个数
     */
    private int size;

    /**
     * 创建MyArrayList对象时，并且使elementData为默认长度（空）
     */
    public MyArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

    public MyArrayList(Collection<? extends E> e) {
        this();
        addAll(e);
    }


    public int size() {
        return size;
    }

    /**
     * 添加元素
     *
     * @param e
     * @return
     */
    public boolean add(E e) {
        //是否对数组进行扩容
        ensureCapacityInternal(size + 1);
        elementData[size++] = e;
        return true;
    }

    /**
     * 确保内部容量
     * 判断数组的容量，小于minCapacity就进行扩容1.5倍
     *
     * @param minCapacity
     */
    private void ensureCapacityInternal(int minCapacity) {
        //如果是空数组则 minCapacity = 10
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        if (minCapacity - elementData.length > 0) {
            //原数组容量
            int oldCapacity = elementData.length;
            //扩容为之前的1.5倍（扩容因子为1.5）
            int newCapacity = oldCapacity + (oldCapacity >> 1);
            //如果新容量 小于 最小容量，则新容量 = 最小容量
            if (newCapacity - minCapacity < 0) {
                newCapacity = minCapacity;
            }
            //ArrayList最大数组长度为Integer.MAX_VALUE - 8
            if (newCapacity > (Integer.MAX_VALUE - 8)) {
                // overflow
                if (minCapacity < 0) {
                    throw new OutOfMemoryError();
                }
                newCapacity = (minCapacity > Integer.MAX_VALUE - 8) ? Integer.MAX_VALUE : Integer.MAX_VALUE - 8;
            }
            //创建新长度的数组，并将原数组数据赋值给新数组
            elementData = Arrays.copyOf(elementData, newCapacity);
        }
    }

    /**
     * 添加元素至索引处，索引处和其之后的元素全部后挪一位
     *
     * @param index
     * @param element
     * @return
     */
    public E add(int index, E element) {
        //检查index是否合法
        if (index > size || index < 0) {
            throw new IndexOutOfBoundsException("index不合法+ index:" + index + ",size:" + size);
        }
        //是否需要扩容,true->扩容
        ensureCapacityInternal(size + 1);
        //size-(index+1)+1
        System.arraycopy(elementData, index, elementData, index + 1, size - index);
        return null;
    }

    public void addAll(Collection<? extends E> e) {
        Object[] a = e.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);
        //将新数组添加到底层数组的尾部
        System.arraycopy(a,0,elementData,size,numNew);
        size +=numNew;
    }

    /**
     * 根据索引查询（数组的随机查询，效率高）
     * @param index
     * @return
     */
    public E get(int index) {
        //检查index是否合法（是否越界）
        rangeCheck(index);
        return (E) elementData[index];
        //返回查询的元素
    }

    /**
     * 检查给定索引是否在数组的有效范围内
     *
     * @param index
     */
    private void rangeCheck(int index) {
        if (index >= size) {
            throw new IndexOutOfBoundsException("index不合法！！index:" + index + ",size:" + size);
        }
    }

    /**
     * 根据索引修改元素
     * @param index
     * @param element
     * @return
     */
    public E set(int index, E element) {
        //检查index是否合法（是否越界）
        rangeCheck(index);
        E oldValue = (E) elementData[index];
        elementData[index] = element;
        return oldValue;
    }


    /**
     * 根据索引删除元素，并将其之后的元素向前移一位
     * @param index
     * @return
     */
    public E remove(int index) {
        rangeCheck(index);
        E oldValue = (E) elementData[index];
        //要改变下标的元素个数 size-（index+1）
        int numMoved = size - index - 1;
        if (numMoved > 0) {
            //从elementData数组的下标index+1开始，覆盖到从elementData数组的下标index的位置
            System.arraycopy(elementData, index + 1, elementData, index, numMoved);
        }
        //尾部的元素设置为null，size先-- 再使用
        elementData[--size] = null;
        return oldValue;
    }

    /**
     * 根据元素删除，遍历数组找到第一个于 o == 的元素 获取他的索引将其删除
     * @param o
     * @return
     */
    public boolean remove(Object o) {
        if (o == 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 (o.equals(elementData[index])) {
                    remove(index);
                    return true;
                }
            }
        }
        return false;
    }
}

总结

很多场景下ArrayList更受欢迎，但是还有些情况下LinkedList更为合适。譬如：

  1. 你的应用不会随机访问数据。因为如果你需要LinkedList中的第n个元素的时候，你需要从第一个元素顺序数到第n个数据，然后读取数据。

  2. 你的应用更多的插入和删除元素，更少的读取数据。因为插入和删除元素不涉及重排数据，所以它要比ArrayList要快。

上述是关于ArrayList和LinkedList的差别。当需要一个不同步的基于索引的数据访问时，请尽量使用ArrayList。但是要记得要给定一个合适的初始大小，尽可能的减少更改数组的大小。

文章作者: Hobo
文章链接: https://hobo-clh.github.io/2020/04/29/%E6%89%8B%E5%86%99ArrayList/
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Hobo's blog！
Java集合数组
打赏
  • 微信
    微信
  • 支付宝
    支付宝
相关推荐
2020-06-08
队列（使用Java数组模拟队列）
2020-05-07
稀疏数组
2020-05-04
HashMap在JDK1.7和1.8的区别
2020-04-28
java集合
评论
繁