JAVA数据结构顺序表的实现（工程文件会上传至博客）

1.什么是List

在集合框架中，List是一个接口，继承自Collection

 实现了List接口就相当于同时实现了Collection和Iterable接口。

2.ArrayList与顺序表

1.线性表

定义：线性表是n个具有相同特征的数据元素的优先序列，线性表广泛的在实际中广泛使用数据结构，常用的数据结构现性表：顺序表，链表，栈，队列等

线性表在逻辑上是线性结构，也就是说连续的一条直线，但是在物理上不一定是连续的（链表），线性表在物理存储时，通常以数组和链表结构的形式存储。

2.顺序表

2.1引出顺序表

1.疑问？为什么需要顺序表？

顺序表是在数组中进行存储

那么既然在数组中存储，为什么还需要线性表？

图解：（1）定义一个elem类型的数组，数组中存入1，23，6，三个数字

           （2）我要求你知道数组的长度，你采取的方式估计是运用for循环来对数组进行便利，当便利到0数字的时候，就计算出来了数组的长度。

           （3）这样是不行的，万一你存入的数字还有一个0，那么长度实际上是4，但是输出的长度会是3这时候就会有问题

            （4）所以我们要用顺序表来对问题进行解决，给数组添加进行操作的方法（这些方法不止可以对数组进行排序还有其他好多方法），这时候就产生了一种新的数据类型，这个类型就是顺序表，是用来操作数组的。

 2.顺序表的实现

（1）java中数据结构是可以直接调包进行使用的，这里我不用掉包进行讲解，我会实现一个简单的顺序表的底层逻辑代码。让大家了解数据结构。（源码比我严谨，我只是仿照源码逻辑实现不要较真）

2.1顺序表的具体实现

2.1.1顺序表具体实现前期准备

定义两个类，Frank是测试类和MyArrayList类实现顺序表

定义一个接口Ilist，MyArrayList用implement语句接入Ilist中的方法并进行重写。

现在我们的主要目的就是实现重写的方法，也就是数据的crud 增删改查（数据结构的本质是对数据的操作方式）

 2.1.2display方法：打印顺序表中的元素

  便利数组输出数组元素

2.1.3将元素添加进入顺序表中的方法完整版步骤（从一小部分开始慢慢完善）

2.1.3.1将元素一个一个放入顺序表的add方法

（1）：add方法将元素添加到数组最后位置这时候有一部分人就会想到下面的写法（不严谨错误的），满了放不了就不行了，所以放之前要先判断是否满了，如果满了就要对数组进行扩容

public void add(int data) {
     elem[usedsize] = data;
     usedsize++;
    }

（2）： isFull方法如果元素满了，返回值为false。

在接口中定义isFull方法，在MyArrayList类中重写isFull方法

（3）结合isFull方法改善add方法 

  如果这个数组满了那么这个数组就运用拷贝语句进行扩容,扩容的倍数是2倍（去看JAVASE常见接口的文章复习）

   代码实现图片

（2）在Frank类中测试add方法是否满足需求

（3）在Frank测试类中的第8行打上断点， 进行调试可以看到在没有运行第8行的时候是只能存储5个数据，其中第五个数据没有存储进去，调试在往下两个步骤就是将5存入顺序表然后对数组扩容。

（4）往后两步的调试结果，第一步可以看到编译器进入了isFull中来判断继续存储空间是否足够，发现是足够的就将5存储到了第五个位置

 

（5）最后一步存储 6这个数据的时候是将数组扩容了，下一步就是将6存储进入到了第六个位置

2.1.3.2将元素放到顺序表指定位置的add方法 

（1）定义一个elem数组，分别有三个位置是pos，和i位置，i位置是数组最后的位置。

（2）需要将元素从后往前移动

（3）将元素放到pos位置

（4）图解

（5）代码实现

定义一个add方法，i从数组的倒数第二个位置开始便利，便利的条件是i在要插入数组元素的pos位置的左边，如果pos的位置大于数组最大长度的位置就将数组进行扩容，将原来没扩容的usedsize的位置放入pos位置要插入元素的值，在for循环中，不断的交换位置，前后进行交换，到i等于pos的时候循环终止这时候就会空出一个位置，将元素就可以放入空缺的位置中了。如果elem不足够存进pos位置的值那么就可以将数组进行扩容然后将元素存入usesize位置。

（6）代码约束

如果用户输入pos的小于0的位置我们要检查出来。要不合法。

定义一个框架，这时候我们需要自定义一个异常，如果输入的不合法要报错，所以就使用了自定义的异常类。

定义一个异常类 PosException使用大驼峰的写法

定义异常

通过throw语句来抛出异常。在抛出异常的时候会告诉你为什么会发生异常，并且会让你来进行判断。

 这时候就发生了方法的重载，分别有两个add方法，使用一般插入就是尾插法，还可以指定位置i进行插入。

 2.1.4查找该元素是否在数组中toFind方法

查找是否有相同的，如果不相写sout语句可以将返回值改为-1，如果是引用类型就要用equals方法进行比较

2.1.5用下标获取元素get方法

private私有方法是为了严谨，满足不合法条件就输出异常，这时候还有一种情况就是pos位置为空的情况，我们也要对这种情况定位不合法情况

在接口中定义一个方法来判断它是否为空,判断是否合法应用到get方法中（isEmpty方法）

2.1.6更新pos位置的值为value的set方法。

1.定义一个方法set方法，调用checkposofGet方法传入pos来对pos的值进行判断是否合法

2.再用if语句调用isEmpty方法来判断数组是否为空，如果为空，那么就输出顺序表为空，

3.如果不为空那么就将pos位置的值进行更新

2.1.7 remove方法，删除这个下标下的元素

使用之前定义的indexof的方法，来对要删除的元素进行查找

 用indexof方法找到下标

这时候的i要执行i+1位置的值赋值给i位置的值，所以i要小于原本i+3位置，所以要usesize - 1  

 

2.1.8clear方法清空数组元素 

1.内存泄漏

一个位置的数据使用完要为空，但是有时候程序员没有至为null，而它要用的时候就会一直引用没有回收的部分就会导致内存泄漏。

2.在ArrayList原本顺序表中的clear方法中也运用了null也就是垃圾回收

3.clear方法的实现，由于我放入的是int类型所以在这里我就全部重置为0了，所以

以上就是所有顺序表方法的实现（在源码中也是一样和我一样是这样）

 3.ArrayList源码简介jdk17

 这是java jdk包中的ArrayList源码使用，其实这和我的方法的名字和功能都是和我写的一样的但是jak包中的更加严谨。

1.ArrayList是泛型类所以一定要实例化

2.还可以通过list接口来引用一个具体的对象，也就是Arraylist。

3.源码对比

源码

我写的

可以发现一些区别 ，但是原理是相同的。

所以接下来我会再进入源码来对顺序表来进行讲解

3.1源码的详细讲解

3.1.1add方法的源码讲解

初始定义的元素

默认容量是10

两个空的Object的数组

一个size相当于我写的usesize数组的长度

接下来是源码中的构造方法（有参数）

（1）有一个参数，加入是15，那么object的数组大小就是15。

（2）如果数组中的参数加入的是0，那么就让这个引用指向在开始定义的EMPTY—-ELEMNETDARTA数组，也就是一个空数组。

（3）如果小于0的化就会抛出异常。

 无参的构造方法

疑问？既然这个数组根本没有分配大小，这个代码咋样执行的，

既然没有分配大小怎么可以放元素，所以add方法分配大小了。

来到add方法进行分析 ，可以看到ensurCapacotyInternal这个方法，所以问题出在这个方法中了

进入这个方法的源码中 ,依次进行递推就可以总结一个逻辑图这些代码都是源码

（1）进入顺序表的源码可以发现并没有对数组分配大小而是指向了一个引用

（2）既然没有分配大小那么就和add放法有关

（3）在add方法中可以看到一个方法是ensureCapacityInternal方法，它对数组的长度进行了扩容

（4）进入ensureCapacityInternal这个方法中我们进行分析

（5）可以发现在ensureCapacityInternal 中的minCapacity的值的大小是上面传入的size+1，也就是1

  (6)在下面一行中将（5）步骤中的参数minCapaciyu的值进行传入也就是size+1（1），可以看成1，（因为）还有elementDate

（7）方法的返回值作为参数，进入calculateCapacity方法中

（8）在一开始的ArreyList方法中定义了elementDate的大小是10，所以这时候在这个方法calculateCapacity中elementDate的值也就是10，所以在这个方法的判断语句中是满足的都是相同的都是10.这时候在minCapaciyu的值和10中选一个大的作为机制来返回数值的大小

（9）直接就走完了返回了10，这是这个方法第一次调用

（10）这个10又返回到了calculateCapacity中（绿色箭头）

（11）这时候我们进行calculateCapacity这个方法中，可以发现这个方法传入的参数是minCapacity这个参数也就是10

（12）10减去0等于几如果大于0，那么就会调用grow方法

（13）进入这个扩容的方法grow方法，这个方法传入的参数是minCapacity也就是10

（14）这个方法中oldCapacity拿到的是0因为数组里面没东西

（15）newCapacity中用0+0/2还是0

（16）如果0减去10小于0

（17）那么newCapacity就是等于10

（18）这时候进入if语句

（19）10减去interMax（非常大），这个一定不大于0

（20）这时候重新分配内存，最后指向了一个长度为10的数组

结论1：第一次add的时候分配了内存内存为0

结论2：扩容的时候是1.5倍进行扩容。oldCapacity

3.1.2add方法中第二个特殊的构造方法

这个E就是Number中的arrayList2，这个相当于继承了arraylist1的特征，

在逻辑图的右上角解释了泛型规定是啥意思 

这个利用了向上转型，忘记的同学自己看一下

4.sublis截取方法(List是一个接口)

使用方法

  

5.顺序表的遍历方式

5.1表示方式（普通）

代码图片

sout输出直接sout

for循环

foreach循环

 5.2迭代器表示方式

利用while循环进行遍历条件是一直又下一个，当下一个没有的时候结束循环

这个迭代器有多种使用方式

进入源码其中有一个ListIterator这个是Iterator的子类

所以我们将Iterator改成ListIterator,两个的区别就是一个只能迭代list还有一个可以迭代任何一个

5.3从后向前表示方式(迭代器)

6复习题自己看懂很简单

比较两串字符输出相同数字

其中要注意的一点是，List 只能调用接口当中包含的方法

                                    Arrayliust 只能调用当前类自己的方法和接口中的方法。

建议返回值用List我建议