【Java/数据结构】ArrayList的实现及使用

从本博客起，我将带各人学习Java当中的数据结构。
那让我们从顺序表开始吧，本博客内容包括但不限于实现一个本身的ArrayList、干系的API先容、干系API的实现以及使用。
一.顺序表概述

1.ArrayList的位置

顺序表（ArrayList）是线性表（List）的一种，继承自AbstractList类，并实现了List接口，以下是它在Java继承体系中的位置：

2.ArrayList的结构

        逻辑结构：元素的有序序列
        物理结构：顺序存储
ArrayList的本质是基于数组的一连存储结构，最大的优势就是对于确定位置的元素访问及其方便。
如下是它的存储示意图：

只要知道数据下标，就可以快速拿到元素，时间复杂度为O(1)。

二.ArrayList的实现

ArrayList在jdk当中的实现有足足1732行，我们挑选了部分核心方法来实现：

ps：想要查看源码，按住Ctrl+Alt选中ArrayList并点击，弹出选项框点击要查找的类即可：

想要深入相识建议查看源码，不过不建议初学者看源码，因为涉及一些Java高级特性。
核心方法

我们要实现的核心方法如下（为了学习，简便，先不考虑泛型）：

1.     // 新增元素,默认在数组最后新增
2.     public void add(int data) {}
4.     //判断是否已满
5.     public boolean isFull() {}
7.     // 在 pos 位置新增元素
8.     public void add(int pos, int data) {}
10.     // 判定是否包含某个元素
11.     public boolean contains(int toFind) {}
13.     // 查找某个元素对应的位置
14.     public int indexOf(int toFind) {}
16.     // 获取 pos 位置的元素
17.     public int get(int pos) {}
19.     // 给 pos 位置的元素设为 value [更新]
20.     public void set(int pos, int value) {}
22.     //检查pos位置是否合法
23.     private void checkPos(int pos) { }
25.     //删除第一次出现的关键字key
26.     public void remove(int toRemove) {}
28.     // 获取顺序表长度
29.     public int size() {}
31.     // 清空顺序表
32.     public void clear() {}

复制代码

1.属性

Java当中顺序表的存储结构如下：

嗯......这可能有些复杂，为了方便学习，我们简化一下：

先不考虑泛型实现，也不考虑io流，这些以后再说！我们假设存储的元素都是整形，那我们本身的ArrayList就有了3个属性：
用来存储的结构，数组
用来表示有效元素的个数的数，usedSize
用来初始化数组大小的自界说常量，DEFAULT_SIZE
ok！这下我们的ArrayList就初步构建完成。

2.构造方法

1.     //默认初始化
2.     public MyArrayList() {
3.         this.elem = new int[DEFAULT_SIZE];
4.     }
6.     //指定容量初始化
7.     public MyArrayList(int initCapacity) {
8.         this.elem = new int[initCapacity];
9.     }

复制代码

初始化之后，我们就可以操作顺序表了，即增、删、查、改。
3.增

1.     //新增元素
2.     public void add(int data) {
3.         if (isFull()) {
4.             this.elem = Arrays.copyOf(this.elem,2*this.elem.length);
5.         }
6.         this.elem[this.usedSize] = data;
7.         this.usedSize++;
8.     }
9.    
10.     //在 pos 位置新增元素
11.     public void add(int pos, int data) {
12.         if (isFull()) {
13.             this.elem = Arrays.copyOf(this.elem,2*this.elem.length);
14.         }
15.         checkPos(int pos)
16.         for (int i =usedSize-1; i > pos; i--) {
17.             this.elem[i+1] = this.elem[i];
18.         }
19.         this.elem[pos] = data;
20.         this.usedSize++;
21.     }
23.     //判断非满
24.     public boolean isFull() {
25.         if (this.usedSize == this.elem.length) {
26.             return true;
27.         }
28.         return false;
29.     }
31.     //检查位置是否合法
32.     private void checkPos(int pos) {
33.         if (pos < 0 || pos >this.elem.length) {
34.             throw  new PosOutOfBoundsException("pos out of bounds!");
35.         }
36.     }

复制代码

我们提供2种新增元素方式，即默认新增和指定位置新增，它们构成了方法的重载。
在新增元素之前，我们必须检查数组是否已满，否则就可能发生StackOutOfBounds异常。判断是否已满的方式很简朴，只要比较有效元素个数是否等于数组长度即可（.length为数组自带属性）。
如果数组已满，我们就要扩容，扩容方式是调佣Arrays方法库中的复制数组，并指定大小为2倍，再赋值给原数组elme。随后就可以新增元素了。
默认新增：在数组的末尾添加元素，直接this.elem[this.usedSize] = data即可。
指定位置（下标）新增：首先我们要判断这个“位置”是否合法，使用私有方法checkPos()，即是否在原数组边界外（由于是线性表，元素必须是一连的，不能空一个元素），不合法抛出我们自界说异常PosOutOfBoundsException，合法则把所有pos后元素后移一位，然后插入即可。

4.查

1. //判定是否包含某个元素
2. public boolean contains(int toFind) {
3.     for (int i = 0; i < this.usedSize; i++) {
4.         if (this.elem[i] == toFind) {
5.             return true;
6.         }
7.     }
8.     return false;
9. }
11. //查找某个元素对应的位置
12. public int indexOf(int toFind) {
13.     for (int i = 0; i < this.usedSize; i++) {
14.         if (this.elem[i] == toFind) {
15.             return i;
16.         }
17.     }
18.     return -1;
19. }
21. //获取 pos 位置的元素
22. public int get(int pos) {
23.     checkPos(pos);
24.     return this.elem[pos];
25. }

复制代码

5.删

删除一个元素，我们有2件事要做，即找到谁人元素位置、把之后的元素前移1格覆盖要删除的元素。

1. //删除第一次出现的关键字key
2. public void remove(int toRemove) {
3.    int index = this.indexOf(toRemove);
4.     if (index == -1) {
5.         System.out.println(toRemove + " is not found!");
6.         return;
7.     }
8.     for (int i = index+1; i < this.elem.length; i++) {
9.         this.elem[i] = this.elem[i-1];
10.     }
11.     this.usedSize--;
12. }

复制代码

indexOf()方法实现了查找某元素位置，remove()则实现删除，即前移后置元素，这里的实现很简朴，就不赘述了。
6.改

1. // 给 pos 位置的元素设为 value [更新]
2. public void set(int pos, int value) {
3.     checkPos(pos);                        //任然要检查位置是否合法
4.     this.elem[pos] = value;
5. }

复制代码

7.其他

一些其他方法的实现：

1. //展示元素
2. public void display() {
3.     for (int i = 0; i <= usedSize; i++) {
4.         System.out.print(elem[i] + " ");
5.     }
6. }
8. // 获取顺序表长度
9. public int size() {
10.     return this.usedSize;
11. }
13. // 清空顺序表
14. public void clear() {
15.     this.usedSize = 0;
16. }

复制代码

三.ArrayList常用方法使用示例

以下代码给出了常用方法的使用方法，供各人学习参考：

1. import java.util.ArrayList;
2. import java.util.Arrays;
4. public class ArrayListDemo {
5.     public static void main(String[] args) {
6.         // 1. 初始化
7.         List<String> fruits = new ArrayList<>();
8.         //ArrayList<String> fruits = new ArrayList<>()也可
9.         System.out.println("初始化列表: " + fruits);  // []
11.         // 2. 添加元素
12.         fruits.add("Apple");     // 末尾添加
13.         fruits.add(0, "Banana");// 指定位置插入
14.         fruits.addAll(Arrays.asList("Orange", "Grape"));
15.         System.out.println("添加元素后: " + fruits); // [Banana, Apple, Orange, Grape]
17.         // 3. 访问元素
18.         System.out.println("\n访问元素演示:");
19.         System.out.println("索引1的元素: " + fruits.get(1));  // Apple
20.         System.out.println("列表大小: " + fruits.size());    // 4
21.         System.out.println("包含Orange? " + fruits.contains("Orange")); // true
22.         System.out.println("Mango的位置: " + fruits.indexOf("Mango")); // -1
24.         // 4. 修改元素
25.         System.out.println("\n修改元素演示:");
26.         fruits.set(2, "Lemon");
27.         System.out.println("修改后: " + fruits); // [Banana, Apple, Lemon, Grape]
29.         // 5. 删除元素
30.         System.out.println("\n删除元素演示:");
31.         fruits.remove("Banana");            // 按对象删除
32.         fruits.remove(0);                   // 按索引删除
33.         System.out.println("删除后: " + fruits); // [Lemon, Grape]
35.         // 6. 其他操作
36.         System.out.println("\n其他操作演示:");
37.         System.out.println("是否为空? " + fruits.isEmpty()); // false
38.         
39.         // 遍历方式1：for循环
40.         System.out.print("for循环遍历: ");
41.         for(int i=0; i<fruits.size(); i++){
42.             System.out.print(fruits.get(i) + " ");
43.         }
44.         
45.         // 遍历方式2：增强for循环
46.         System.out.print("\n增强for循环: ");
47.         for(String fruit : fruits){
48.             System.out.print(fruit + " ");
49.         }
50.         
51.         // 遍历方式3：forEach方法，fruit会在集合内遍历，结合Lambda表达式可以减少代码量
52.         System.out.print("\nforEach方法: ");
53.         fruits.forEach(fruit -> System.out.print(fruit + " "));
55.         // 清空列表
56.         fruits.clear();
57.         System.out.println("\n清空后: " + fruits); // []
58.     }
59. }

复制代码

说明1：初始化时，有2种选择：

1. List<T> list = new ArrayList<>()
2. ArrayList<T> list = new ArrayList<>()

复制代码

2种方式区别不大，但大部分情况下选择第一种，由于多态特性，虽然不能用ArrayList的特定方法，但是不指定实际绑定类型，可以让list有更灵活的变化可能，如转换成链表（虽然大部分情况下不使用）：

1. List<String> list = new ArrayList<>();
2. list.add("Java");
3. list = new LinkedList<>(); // 允许替换实现

复制代码

  合理选择初始化方式，可以让代码在灵活性和功能性之间到达最佳平衡。这也是 Java 集合框架设计的英华地点。
  当然，实际情况实际选择，如需要调用ArrayList特有方法，请用ArrayList类型初始化。
说明2：第三种方法结合了Lambda表达式，使循环更为简洁高效，而且这种方式支持链式编程，可以大大节流代码量，是当代编程首选。
另外，此处还等价于：

1. fruits.forEach(System.out::println);

复制代码

详情请参考Lambda表达式的使用及其化简。




结语

阅读过源码的朋友应该知道Java内部的实现比这要复杂一些，涉及了很多高级特性，但是其核心的方法内涵就是这么简朴，相识了这些后，使用ArrayList就能更加得心应手。
以为有帮助不妨点个赞，下一篇我们将先容链表，链表的一些方法和特性比顺序表复杂很多，我们会更加详细地讲解。 


免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。