数据结构之ArrayList

系列文章目录

---

目录

系列文章目录

前言

一、数据结构的前置语法

1. 时空复杂度

2. 包装类

3. 泛型

二、ArrayList 和顺序表

1. 顺序表的模拟实现

2. 源码

3. ArrayList 的优缺点

---

前言

本文介绍数据结构的前置算法，以及 ArrayList 的模拟实现，部分源码及优缺点概括。

---

一、数据结构的前置语法

1. 时空复杂度

时间复杂度和空间复杂度：用来衡量算法的效率（时间和空间），通常用大O渐进法进行表示；

 常见的时间复杂度：O(1), O(logN), O(N), O(N*logN), O(N^2)；

2. 包装类

解释下面代码的原理：

Integer a = 100;
Integer b = 100;System.out.println(a == b); // 输出 trueInteger c = 200;
Integer d = 200;System.out.println(c == d); // 输出 false

valueOf(): Integer 源码：

public static Integer valueOf(int i) {if (i >= IntegerCache.low && i <= IntegerCache.high)return IntegerCache.cache[i + (-IntegerCache.low)];return new Integer(i);
}

Integer.Cache.high = 127, Integer.Cache.low = -128

cache数组中在 [0, 255] 空间中存的是 -128 ~127；

如果数字 i 的值在 [-128， 127] 之间，返回 cache 数组的对应下标 [0, 255] 区间的值，即 -128 ~ 127；否则则会 new 一个新的引用变量；

因此当 i 在 [-128, 127] 之间，返回的都是同一个哈希值，即引用变量相等，否则返回不同的哈希值，即引用变量不相等；

3. 泛型

类名后面写一个 "<T>" ，表示这是一个泛型类；

"<>" 只能存放包装类型，不能存放基本类型；

编译的时候会把 T 类型都替换成 Object 类型，这称为泛型的擦除机制；

泛型的上界：

泛型类：class 类名<T extends XXX> ，XXX 就是泛型的上界；

泛型方法 ：<T> 返回类型 方法名<T extends XXX>(){...}， XXX 就是泛型的上界；

二、ArrayList 和顺序表

顺序表底层是一个数组，是使用数组来完成的一种结构；

实现了 List 接口，通常使用 "List<T> list = new ArrayList<>() " 这种向上转型的形式去定义顺序表；

1. 顺序表的模拟实现

下面模拟实现顺序表，理解顺序表的底层原理：

定义一个数组 elem，用于存放元素，定义一个 usedSize 用于表示存放了几个元素；

定义一个常数 DEFAULT_SIZE，用来表示新建一个顺序表默认开辟空间的大小；

定义一个无参的构造方法，默认开辟的空间大小为 DEFAULT_SIZE；

定义一个有一个参数的构造方法，参数用于指定开辟空间的大小；

public class MyArrayList {private int[] elem;private int usedSize;private static final int DEFAULT_SIZE = 10;public MyArrayList(){this.elem = new int[DEFAULT_SIZE];}public MyArrayList(int capacity){this.elem = new int[capacity];}// 方法的位置// ......
}

下面实现顺序表的方法（增删改查）：

打印顺序表的所有元素：

    // 打印元素public void display(){for(int i = 0; i < usedSize; i++){System.out.print(this.elem[i] + " ");}}

向顺序表中增加一个元素：

注意：在顺序表中增加元素的时候，需要先判断当前是否已经存满，如果存满了要先进行扩容才可以再往顺序表中添加元素；

isFull(): boolean 判断顺序表是否存满；每次增加元素都需要判断顺序表是否存满；

add(int data): void 向顺序表最后一个位置新增一个元素；

add(int pos, int data): void 向顺序表的 pos 位置新增一个元素；

需要判断 pos 位置是否合法，不合法要抛出异常；

如果合法，就要将 pos 位置以及 pos 后面的元素，往后挪一个位置，考虑到可能覆盖后一个元素的问题，需要从后往前依次向后挪每个元素；

增加元素一定不要忘记 usedSize++;

    // 判断是否满public boolean isFull(){if(this.usedSize == this.elem.length) {return true;}return false;}// 新增元素，默认在数组最后新增public void add(int data){if(isFull()){// 扩容this.elem = Arrays.copyOf(this.elem, 2 * this.elem.length);}this.elem[usedSize] = data;usedSize++;}// 在 pos 位置新增元素public void add(int pos, int data){if(pos < 0 || pos > this.usedSize){throw new PosOutOfBoundsException(pos + "位置不合法");}if(isFull()){// 扩容this.elem = Arrays.copyOf(this.elem, 2 * this.elem.length);}for(int i = usedSize - 1; i >= pos; i--){this.elem[i + 1] = this.elem[i];}this.elem[pos] = data;this.usedSize++;}

查找元素：

contains(int toFind): boolean 判断元素 toFind 是否在顺表中存在；

indexOf(int toFind): int 找元素 toFind 的下标，找到则返回对应下标，找不到返回 -1；

checkPos(int pos): void 判断下标是否合法，查找某个下标元素需要先判断下标是否合法，不合法直接抛出异常；

get(int pos): int 获取 pos 位置元素的下标；需要先判断给定的 pos 下标是否合法；

    // 判断是否包含某个元素public boolean contains(int toFind){for(int i = 0; i < this.usedSize; i++){// 如果是引用类型，可以使用 equals 方法if(this.elem[i] == toFind){return true;}}return false;}// 查找某个元素对应的位置public int indexOf(int toFind){for(int i = 0; i < this.usedSize; i++){if(this.elem[i] == toFind){return i;}}return -1;}// 判断下标是否合法    private void checkPos(int pos){if(pos < 0 || pos >= this.usedSize){throw new PosOutOfBoundsException(pos + "位置不合法");}}// 获取某个位置的元素public int get(int pos){checkPos(pos);return this.elem[pos];}

修改某个位置元素：

set(int pos, int value): void 修改 pos 位置的元素为 value，修改前同样需要判断 pos 位置是否合法；

    // 给 pos 位置的元素设为 valuepublic void set(int pos, int value){checkPos(pos);this.elem[pos] = value;}

删除某个元素：

remove(int toRemove): void 删除元素 toRemove；

先查找该元素的下标；

如果元素不存在直接返回；

如果元素存在则删除该元素，并将该元素后面的元素都往前移一个位置；如果是引用类型的数据，一定记得把最后一个引用置 null；

删除元素一定不能忘记 usedSize--；

    // 删除第一次出现的关键字 keypublic void remove(int toRemove){int index = indexOf(toRemove);if(index == -1){return;}for(int i = index; i < this.usedSize - 1; i++){this.elem[i] = this.elem[i + 1];}// 如果是引用类型，最后一个位置就要置 null// this.elem[this.usedSize - 1] = nullthis.usedSize--;}

求顺序表长度：

size(): int 求顺序表长度，直接返回 usedSize 即可；

    // 获取顺序表长度public int size(){return this.usedSize;}

清空顺序表：

clear(): void 清空顺序表；

如果是基本类型，直接将 usedSize 置 0 即可；

如果是引用类型，需要遍历一遍顺序表，将每个引用都置 null；

    // 清空顺序表public void clear(){// 如果是引用类型，就要遍历置为 null
//        for(int i = 0; i < this.usedSize; i++){
//            this.elem[i] = null;
//        }this.usedSize = 0;}

2. 源码

构造方法：

ArrayList(int initialCapacity)：一个参数的构造方法，initialCapacity 用于指定顺序表的空间；

ArrayList()：无参的构造方法，并没有分配内存，第一次增加元素的时候才会扩容；

ArrayList(Collection<? extends E> c)：可以传 E 类型的子类或者 E 类型本身的 实现了Collection 接口的数据结构；除了 Map 没实现， Collection，List，Queue，Set 都实现了；

public ArrayList(int initialCapacity) {if (initialCapacity > 0) {this.elementData = new Object[initialCapacity];} else if (initialCapacity == 0) {this.elementData = EMPTY_ELEMENTDATA;} else {throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);}}/*** Constructs an empty list with an initial capacity of ten.*/public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}/*** Constructs a list containing the elements of the specified* collection, in the order they are returned by the collection's* iterator.** @param c the collection whose elements are to be placed into this list* @throws NullPointerException if the specified collection is null*/public ArrayList(Collection<? extends E> c) {elementData = c.toArray();if ((size = elementData.length) != 0) {// c.toArray might (incorrectly) not return Object[] (see 6260652)if (elementData.getClass() != Object[].class)elementData = Arrays.copyOf(elementData, size, Object[].class);} else {// replace with empty array.this.elementData = EMPTY_ELEMENTDATA;}}

ArrayList 扩容机制：

    Object[] elementData;   // 存放元素的空间private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};  // 默认空间private static final int DEFAULT_CAPACITY = 10;  // 默认容量大小public boolean add(E e) {ensureCapacityInternal(size + 1);  // Increments modCount!!elementData[size++] = e;return true;}private void ensureCapacityInternal(int minCapacity) {ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));}private static int calculateCapacity(Object[] elementData, int minCapacity) {if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {return Math.max(DEFAULT_CAPACITY, minCapacity);}return minCapacity;}private void ensureExplicitCapacity(int minCapacity) {modCount++;// overflow-conscious codeif (minCapacity - elementData.length > 0)grow(minCapacity);}private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;private void grow(int minCapacity) {// 获取旧空间大小int oldCapacity = elementData.length;// 预计按照1.5倍方式扩容int newCapacity = oldCapacity + (oldCapacity >> 1);// 如果用户需要扩容大小 超过 原空间1.5倍，按照用户所需大小扩容if (newCapacity - minCapacity < 0)newCapacity = minCapacity;// 如果需要扩容大小超过MAX_ARRAY_SIZE，重新计算容量大小if (newCapacity - MAX_ARRAY_SIZE > 0)newCapacity = hugeCapacity(minCapacity);// 调用copyOf扩容elementData = Arrays.copyOf(elementData, newCapacity);}private static int hugeCapacity(int minCapacity) {// 如果minCapacity小于0，抛出OutOfMemoryError异常if (minCapacity < 0)throw new OutOfMemoryError();return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;}

3. ArrayList 的优缺点

优点：可以通过下标进行随机访问，时间复杂度 O(1)；

缺点：

往某个位置添加元素，需要往后移动后面的元素；

删除某个元素，需要移动把后面的元素往前移动；

扩容的时候，每次都需要拷贝所有元素；扩容之后可能会浪费空间；

总结：适合静态的数据查找和更新，不适合插入和删除数据。