数据结构-ArrayLIst-一起探索顺序表的底层实现

各位看官早安午安晚安呀
  假如您以为这篇文章对您有帮助的话
  欢迎您一键三连，小编尽尽力做到更好
欢迎您分享给更多人哦

  大家好，我们本日来学习java数据结构的第一章ArrayList（顺序表）
  1.ArrayList的概念

   那小伙伴就要问了线性表到底是什么呢？           线性表    （    linear list    ）    是    n    个具有雷同特性的数据元素的有限序列。     线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列...（我们后续都会进行讲授）         线性表起首是一个序列，也就是说，元素之间是有顺序的，假如元素存在多个，那么第一个元素无前驱。末了一个元素无后驱。其他每个元素都必须有一个前驱和后驱。     例如：   

      usedSize这个变量黑白常紧张的，我们的增删查改都要用到   1.2ArrayList的模拟实现

1. import java.util.Arrays;
3. public class MyArrayList {
5.     private int []elem;//用来存放数据
6.     private int usedSize;//非常重要，代表当前顺序表当中的有效数据个数
8.     private static final int DEFAULT_SIZE = 2;
10.     public MyArrayList() {
11.         this.elem = new int[DEFAULT_SIZE];
12.     }
13.     public MyArrayList(int initCapacity){
14.         this.elem = new int[initCapacity];
15.     }
17.     // 新增元素,默认在数组最后新增
18.     public void add(int data) {
19.         if(elem.length == usedSize){
20.             elem = Arrays.copyOf(elem,elem.length*2);
21.         }
22.         elem[usedSize] = data;
23.         this.usedSize++;//一定不要忘记加
24.     }
25.     // 在 pos 位置新增元素
26.     public void add(int pos, int data) {//只要带pos的都要进行检查
27.         if(checkPos(pos) ==false ){
28.             return;
29.         }
30.             if (elem.length == usedSize) {
31.             elem = Arrays.copyOf(elem, elem.length * 2);
32.         }
33.             //下面这种写法就错误了，导致pos后面的值都是pos位置的值
34.         /*for (int i = pos; i < usedSize -1; i++) {
35.             elem[i+1] = elem[i];
36.         }*/
37.         //应该从后往前
38.         for (int i = usedSize-1 ; i >= pos; i--) {
39.             elem[i+1] = elem[i];
40.         }
41.         elem[pos] = data;
42.         usedSize++;
43.     }
45.     /*public void delete(int pos){
46.         if(checkPos(pos) == false)
47.         if(this.usedSize == 0){
48.             System.out.println("数组里面没有元素了");
49.             return;
50.         }
51.         for (int i = 0; i < usedSize - 1; i++) {
52.             elem[i] = elem[i+1];
53.         }
54.     }
55. */
57.     // 判定是否包含某个元素
58.     public boolean contains(int toFind) {//啥意思
59.         for (int i = 0; i < usedSize; i++) {
60.             if(elem[i] == toFind ) //这里是int类型，所以你能够直接比较，其他类型的话，要重写equals方法
61.                 return true;
62.         }
63.         return false;
64.     }
66.     // 查找某个元素对应的位置
67.     public int indexOf(int toFind) {
68.         for (int i = 0; i < usedSize; i++) {
69.             if(elem[i] == toFind)
70.             return i;
71.         }
72.         System.out.println("没有你要找的值");
73.         return -1;
74.     }
76.     public boolean checkPos(int pos){
77.         if( pos < 0 || pos >= usedSize){
78.             System.out.println("下标错误");
79.             return false;
80.         }
81.         return true;
82.     }
83.     // 获取 pos 位置的元素
84.     public int get(int pos) {
86.         if(checkPos(pos) == false){
87.             return -1;
88.         }
89.         return elem[pos];
90.     }
92.     // 给 pos 位置的元素设为 value
93.     public void set(int pos, int value) {
94.         if(checkPos(pos) == false){
95.             return;
96.         }
97.         elem[pos] = value;
98.     }
100.     //删除第一次出现的关键字key
101.     public void remove(int data) {
102.         int index = this.indexOf(data);
103.         if(index == -1){
104.             System.out.println("没有这个数据");
105.             return;
106.         }
107.         for (int i = data; i < usedSize - 1; i++) {
108.             elem[i] = elem[i+1];
109.         }
110.        //如果是引用类型的话： elem[index] = null;
111.         this.usedSize--;
113.     }
115.     // 获取顺序表长度
116.     public int size() {
117.         return this.usedSize;
118.     }
120.     // 清空顺序表
121.     public void clear() {
122.         this.usedSize = 0;
123.         //但是如果是引用类型的话
124. /*
125.         for (int i = 0; i < usedSize; i++) {
126.             elem[i] = null;
127.             记得全部置为空
128.             引用类型的话，删除也要置为null
129.         }
130. */
131.     }
133.     // 打印顺序表，注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的
134.     public void display() {
135.         for (int i = 0; i < usedSize; i++) {
136.             System.out.print(this.elem[i] + " ");
137.         }
138.     }
139. }

复制代码

  目前我们自己实现了顺序表这种结构，以后用到的时间，Java已经为我们提供好了
  ArrayList（就是一个平凡的类实现了List接口）
  （自己看一下方法）（ArrayLIst内里的方法，底层方法）（我们可以看出来ArrsyList底层的数组我们在实例化对象时也是默认长度为我们的常量值，有效元素个数非常紧张，我们增加删除元素等方法都要用的）

2：构造方法

我们要了解一个类起首要了解他的构造方法
ArrayList<E>中的E就表现列表中存储的元素的类型
ArrayList

2.1:构造方法一，三

1.        ArrayList<Integer> list = new ArrayList<>();   这种能用的方法更多
2.        List<Integer> list = new ArrayList<>();    一般我们用这一种，向上转型，动态绑定的等等，你俩用哪个主要看自己业务场景
3.        ArrayList<Integer> list = new ArrayList<>(15)

复制代码

我们可以看到默认数组长度是10，前面源码图解上有
2.2:构造方法二

然后我把list1指定的类型换成Integer就解决问题了！

大家也可以看到我显着对于list3只add了一次但是，打印出来的值却把list1数组内里的内容也拷贝过来了（拷贝在外面构造方法那一步就完成了）
2.3:ArrayList常见利用

  

1. public static void main(String[] args) {
2.         ArrayList<Integer> list = new ArrayList<>();
3.         list.add(1);
4.         list.add(2);
5.         list.add(3);
6.         list.add(1,4);
7.         System.out.println(list);//到这里是【1,4,2，3】
9.         list.remove(1);//这两个老是搞混，这个是删除1小标的值
10.         list.remove(new Integer(1));//要删除1这个元素的值一定要用这种方法，因为这个参数是Object类型的
11.         System.out.println(list);//到这里是【2,3】
13.         // list.get(2);//这里会报一个数组越界异常，就是用来和UsedSize比较
15.         list.add(99);
16.         list.add(100);
17.         list.add(101);
18.         boolean isFalse = list.contains(new Integer(100));//这里最好用Integer类型的
19.         System.out.println(isFalse);//true
21.         List<Integer> list1 = list.subList(1,4);//左闭右开
22.         System.out.println(list1);
24.         list.set(1,200);
25.         System.out.println(list);
26.         System.out.println(list1);
27.         //list1得到的是从list数组里面的引用，只要改变其中一个元素的值，另一个也会改变
29.         list.clear();
30.         System.out.println(list);
31.         //全部清除
32.     }

复制代码

2.4:ArrayList的三种遍历

   ArrayList   可以使用三方方式遍历：  for  循环  +  下标、  foreach  、使用迭代器

1. public static void main(String[] args) {
2. List<Integer> list = new ArrayList<>();
3. list.add(1);
4. list.add(2);
5. list.add(3);
6. list.add(4);
7. list.add(5);
8. // 使用下标+for遍历
9. for (int i = 0; i < list.size(); i++) {
10. System.out.print(list.get(i) + " ");
11. }
12. System.out.println();
13. // 借助foreach遍历
14. for (Integer integer : list) {
15. System.out.print(integer + " ");
16. }
17. System.out.println();
19. //迭代器
20. Iterator<Integer> it = list.listIterator();
21. //ListIterator<Integer> it = list.listIterator();也可以
22. //ListIterator是Iterator的子类
23. while(it.hasNext()){
24. System.out.print(it.next() + " ");
25. }
26. System.out.println();
27. }

复制代码

     注意：        1. ArrayList   最长使用的遍历方式是：   for   循环   +   下标 以及    foreach        2.    迭代器是设计模式的一种，后续博客我会继续讲授    2.5：ArrayList的扩容机制的缺陷

   ArrayList是一个动态类型的顺序表，即：在插入元素的过程中会自动扩容。以下是ArrayList源码中扩容方式           【    总结    】           1.     检测是否真正必要扩容，假如是调用    grow    准备扩容           2.     预估必要库容的大小           初步预估按照    1.5    倍大小扩容 ，假如用户所需大小超过预估1.5    倍大小，则按照用户所需大小扩容           真正扩容之前检测是否能扩容成功，防止太大导致扩容失败           3.     使用    copyOf    进行扩容       3：杨辉三角

力扣杨辉三角
实现：

1. import java.util.ArrayList;
2. import java.util.Iterator;
3. import java.util.List;
4. public class Test {
5.     public static void main(String[] args) {
6.         int num = 5;
7.         List<Integer> row = new ArrayList<>();
8.         List<List<Integer>> ret = new ArrayList<>();
9.         row.add(1);
10.         ret.add(row);
11.         for (int i = 1; i < num; i++) {
12.             List<Integer> curRow1 = new ArrayList<>();
13.             curRow1.add(1);//每行的第一个元素都是1
15.             List<Integer> previousRow = ret.get(i - 1);
17.             for (int j = 1; j < i; j++) {
18.                 Integer x = previousRow.get(j) + previousRow.get(j - 1);
19.                 curRow1.add(x);
21.             }
22.             curRow1.add(1);//每行的最后一个元素也都是1
24.             ret.add(curRow1);//把这一行的数组加进去
25.         }
26.         for (List<Integer>list:ret   //遍历数组
27.              ) {
28.             System.out.println(list);
29.         }
30.         System.out.println("============================");
31.         Iterator<List <Integer>> it = ret.listIterator();//使用迭代器遍历数组
32. //ListIterator<Integer> it = list.listIterator();也可以
33. //ListIterator是Iterator的子类
34.         while(it.hasNext()){
35.             System.out.print(it.next() + " ");
36.             System.out.println();
37.         }
39.     }
40.     }

复制代码

   上述就是数据结构-ArrayLIst-数组的深入包装 的全部内容了，能看到这里相信您肯定对小编的文章有了肯定的认可，数据结构的出现让我们对于数据的组织的使用有了更加方便的使用~~
  有什么问题欢迎各位大佬指出
欢迎各位大佬评论区留言修正

您的支持就是我最大的动力​​​！！！！

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