数据结构之ArrayList与顺序表（上）

找往期文章包括但不限于本期文章中不懂的知识点：
   个人主页：我要学编程(ಥ_ಥ)-CSDN博客
  所属专栏：数据结构（Java版）
  顺序表的学习，点我
上面这篇博文是关于顺序表的基础知识，以及顺序表的实现。
目录
手动实现顺序表的源码：
分析Java 8 的 ArrayList 的源码 
字段：
构造方法：
ArrayList本身的扩容机制和分配内存机制
ArrayList常见操作
ArrayList的遍历 
平凡for循环遍历
for-each遍历 
toString方法遍历 
迭代器遍历 

---

手动实现顺序表的源码：

下面是Java版的顺序表源码：

1. public class MyArraylist {
2.     public int[] elem;
3.     public int usedSize;//0
4.     //默认容量
5.     private static final int DEFAULT_SIZE = 10;
7.     public MyArraylist() {
8.         this.elem = new int[DEFAULT_SIZE];
9.     }
11.     /**
12.      * 打印顺序表:
13.      *   根据usedSize判断即可
14.      */
15.     public void display() {
16.         for (int i = 0; i < this.usedSize; i++) {
17.             System.out.print(this.elem[i]+" ");
18.         }
19.         System.out.println();
20.     }
22.     // 新增元素,默认在数组最后新增
23.     public void add(int data) {
24.         // 增加元素之前得先判断数组是否已满
25.         if (isFull()) {
26.             expansion();
27.         }
28.         // 尾插数据不需要判断 pos 位置是否合法
29.         elem[this.usedSize++] = data;
30.     }
32.     // 扩容
33.     private void expansion() {
34.         // 原来数组的2倍扩容
35.         this.elem = Arrays.copyOf(this.elem, 2 * this.elem.length);
36.     }
38.     /**
39.      * 判断当前的顺序表是不是满的！
40.      * @return true:满   false代表空
41.      */
42.     public boolean isFull() {
43.         // 判断这个数组的有效元素个数是否等于数组的长度
44.         return this.usedSize == this.elem.length;
45.     }
48.     private boolean checkPosInAdd(int pos) {
49.         if (pos < 0 || pos > this.usedSize) {
50.             return false;
51.         }
52.         return true;//合法
53.     }
55.     // 在 pos 位置新增元素
56.     public void add(int pos, int data) throws PosofAddException{
57.         if (!checkPosInAdd(pos)) {
58.             throw new PosofAddException("add(int pos, int data) " +
59.                     "pos位置不合法");
60.         }
61.         // 判断是否为尾插
62.         if (pos == this.usedSize) {
63.             add(data);
64.         }else {
65.             // 开始移除元素（从后往前移除）
66.             for (int i = this.usedSize; i > pos; i--) {
67.                 this.elem[i] = this.elem[i-1];
68.             }
69.             // 开始插入数据
70.             this.elem[pos] = data;
71.             this.usedSize++;
72.         }
73.     }
75.     // 判定是否包含某个元素
76.     public boolean contains(int toFind) {
77.         // 先判断这个数组是否有元素
78.         if (isEmpty()) {
79.             return false;
80.         }
81.         for (int i = 0; i < this.usedSize; i++) {
82.             if (this.elem[i] == toFind) {
83.                 return true;
84.             }
85.         }
86.         return false;
87.     }
89.     // 查找某个元素对应的位置
90.     public int indexOf(int toFind) {
91.         for (int i = 0; i < this.usedSize; i++) {
92.             if (this.elem[i] == toFind) {
93.                 return i;
94.             }
95.         }
96.         return -1;
97.     }
99.     // 获取 pos 位置的元素
100.     public int get(int pos) throws PosofGetException{
101.         if (pos < 0 || pos > this.usedSize) {
102.             throw new PosofGetException("get(int pos)" +
103.                     "pos位置不合法");
104.         }
105.         return this.elem[pos];
106.     }
108.     private boolean isEmpty() {
109.         // 有效数据个数为0，就是为空
110.         return this.usedSize == 0;
111.     }
113.     // 给 pos 位置的元素设为【更新为】 value
114.     public void set(int pos, int value) throws PosofSetException{
115.         // 先得判断这个 pos 位置是否合法
116.         if (pos < 0 || pos >= this.usedSize) {
117.             throw new PosofSetException("set(int pos, int value)" +
118.                     "要修改的位置不合法");
119.         }
120.         this.elem[pos] = value;
121.     }
123.     /**
124.      * 删除第一次出现的关键字key
125.      * @param key
126.      */
127.     public void remove(int key) throws PosofRemoveException{
128.         int pos = indexOf(key); // 下标
129.         if (pos < 0) {
130.             throw new PosofRemoveException("remove(int key)" +
131.                     "没有您要删除的数据");
132.         }
133.         for (int i = pos; i < this.usedSize - 1; i++) {
134.             // 后一个位置往前覆盖
135.             this.elem[i] = this.elem[i+1];
136.         }
137.         this.usedSize--;
138.     }
140.     // 获取顺序表长度
141.     public int size() {
142.         return this.usedSize;
143.     }
145.     // 清空顺序表
146.     public void clear() {
147.         // 由于存放的是基本数据类型，直接清空即可
148.         this.usedSize = 0;
149.         // 如果存放的是引用数据类型就得通过for循环遍历把数组的内容置为null
150.         // 注意：如果直接把数组置为null的话，就会存在安全问题，而且源码也是遍历的方式
151.     }
152. }

复制代码

异常：
PosofAddException：

1. public class PosofAddException extends RuntimeException{
2.     public PosofAddException() {
4.     }
5.     public PosofAddException(String msg) {
6.         super(msg);
7.     }
8. }

复制代码

 PosofGetException：

1. public class PosofGetException extends RuntimeException{
2.     public PosofGetException() {
4.     }
5.     public PosofGetException(String msg) {
6.         super(msg);
7.     }
8. }

复制代码

PosofSetException： 

1. public class PosofSetException extends RuntimeException{
2.     public PosofSetException() {
4.     }
5.     public PosofSetException(String msg) {
6.         super(msg);
7.     }
8. }

复制代码

PosofRemoveException： 

1. public class PosofRemoveException extends RuntimeException{
2.     public PosofRemoveException() {
4.     }
5.     public PosofRemoveException(String msg) {
6.         super(msg);
7.     }
8. }

复制代码

分析Java 8 的 ArrayList 的源码 

实现了咱们本身写的顺序表了之后，就该来看Java本身的源码是怎么写的以及与我们的有什么差别？（注意：由于Java 17封装性太强，不好观看源码，因此下面的源码来自Java 8。）
字段：

elementData 就是我们本身实现的 elem 数组。
size 就是 usedSize ，也就是这个数组的有效元素的个数。 
构造方法：

Java 8 实现的顺序表有三个构造方法。 
带有一个 int 类型的参数的构造方法： 

 不带参数的构造方法：

带一个 Collection 类型的参数的构造方法：
下面的是其源码： 

首先，我们得知道Collection 到底是这个啥？ 

根据上面这个图可以得知：Collection 是一个接口。
上面的参数先不看泛型，那就是Collection c  这个意味着只要实现了Collection 接口，就可以被当成实参传过来。而从上图的关系可知：ArrayList 继承了 AbstractLIst 这个抽象类 ，而且实现了LIst这个接口，而 LIst 这个接口拓展了 Collection 这个接口的功能。也就意味着 ArrayList 这个类实现了 Collection 这个接口。那么 ArrayList 就可以被当成参数传过来。
接下来，就是了解 <? extends E> ，？就可以当成是被传过来的 ArrayList 中的泛型，也就是说被传过来的 ArrayList 中的泛型要是 E 或者 E的子类。例如：

了解了这些，我们就来看源码吧。这个源码的大概意思是把传入的 ArrayList 中的元素给全部拷贝到原来的 ArrayList 的后面。
ArrayList本身的扩容机制和分配内存机制

既然我们在创建一个顺序表的时间，原本是空，那么当我们去增加元素的时间，扩容的机制又是如何呢？

上面是分析过程（可忽略），总之，得出了下面这个结论： 
当顺序表为空时，我们如果去增加元素，就会初始化一个大小10的数组。而且数组在满了之后，会按照1.5倍的扩容方式来扩容。如果用户所需大小凌驾预估1.5倍大小，则按照用户所需大小扩容。
ArrayList常见操作

ArrayList常用方法  boolean add(E e)尾插evoid add(int index, E element)将 e 插入到 index 位置boolean addAll(Collection<? extends E> c)将c 中的元素举行尾插E remove(int index)删除 index 位置元素boolean remove(Object o)删除碰到的第一个oE get(int index)获取下标index位置元素E set(int index, E element)将下标 index 位置元素改为 elementvoid clear()清空boolean contains(Object o）判断是否在顺序表中int indexOf(Object o)返回第一个o所在下标int lastlndexOf(Object o)返回最后一个o的下标List<E> subList(int fromlndex, int tolndex)截取部门list 大部门方法，我们都很认识。因此这里只展示 addAll()方法 和 subList 方法。

addAll () 方法可以实现 ArrayList 的带Collection 类型的参数的构造方法。
从上面打印的效果可以看出来，ArrayList 是重写了toString 方法的。

从这里我们就可以看出来，被分割的数组应该是下面这样：

ArrayList的遍历 

平凡for循环遍历

1. public class Test {
2.     public static void main(String[] args) {
3.         ArrayList<Integer> arrayList = new ArrayList<>();
4.         arrayList.add(1);
5.         arrayList.add(2);
6.         arrayList.add(3);
7.         for (int i = 0; i < arrayList.size(); i++) {
8.             System.out.print(arrayList.get(i)+" ");
9.         }
10.     }
11. }

复制代码

for-each遍历 

1. public class Test {
2.     public static void main(String[] args) {
3.         ArrayList<Integer> arrayList = new ArrayList<>();
4.         arrayList.add(1);
5.         arrayList.add(2);
6.         arrayList.add(3);
7.         for (Integer x : arrayList) {
8.             System.out.print(x+" ");
9.         }
10.     }
11. }

复制代码

toString方法遍历 

1. public class Test {
2.     public static void main(String[] args) {
3.         ArrayList<Integer> arrayList = new ArrayList<>();
4.         arrayList.add(1);
5.         arrayList.add(2);
6.         arrayList.add(3);
7.         System.out.println(arrayList.toString());
8.     }
9. }

复制代码

迭代器遍历 

1. public class Test {
2.     public static void main(String[] args) {
3.         ArrayList<Integer> arrayList = new ArrayList<>();
4.         arrayList.add(1);
5.         arrayList.add(2);
6.         arrayList.add(3);
7.         // 调用iterator方法生成一个迭代器，用Iterator<E>来接收
8.         Iterator<Integer> integerIterator = arrayList.iterator();
9.         // 如果下一个元素有值话，就进入while循环，并且打印下一个值，最后自己往后走
10.         while (integerIterator.hasNext()) {
11.             System.out.print(integerIterator.next()+" ");
12.         }
13.     }
14. }
15.         

复制代码

只要是实现了 Iterator 接口就可以利用迭代器的方式来遍历。就是下面这张图：

好啦！本期 数据结构之ArrayList与顺序表（上）的学习就到此结束啦！我们下一期再一起学习吧！

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