Java-数据结构-ArrayLis与线性表 (๑╹◡╹)ﾉ“““

本文主要是介绍Java-数据结构-ArrayLis与线性表 (๑╹◡╹)ﾉ“““，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、List的简单的介绍：

在我们了解 List 之前呢，我们要先看一个图片：

我们可以看到这个图片的最左边呢就是我们List，这个List继承了 Collection 接口，Collection接口又继承了 Iterable，接口，所以我们的 List 接口就有了这两个接口的所有方法。

在我们站在数据结构的角度来看呢，List 接口就是一个线性表，就是n个具有相同类型的元素的有限序列，在这个序列上可以进行增删查改的操作。

注意我们的List是一个接口，不能实例化，要是使用的话，只能去实例化List的实现类。

二、线性表：

常见的线性表为：顺序表、链表、栈、队列....

对于线性表我们从逻辑上来说呢，其是线性结构，相当于是连续的一条直线，线性表在存储时候呢，通常以数组和链式结构来存储的。

三、顺序表：

我们呢先来介绍线性表中的顺序表。我们来看看：

顺序表呢，是使用一段物理地址连续的存储单元依次存储数据，一般情况下呢，我们使用数组进行存储，在数组上进行对元素的增删查改操作。

这次能我们就是用数组来进行对数据的增删查改操作，在我们使用数组的时候呢，数组自带的方法不能满足我们的使用，这时候呢我们就自己定义一个类，让这个类来进行对方法的实现，以便于我们使用。

那么接下来我们自己定义一个类，来进行对数组的增删查改等操作。

我们来看看它的代码的每一步的实现：

1、基本代码：

我们的类里里面用的是数组，所以我们要在类中定义一个数组：

由上面的图可知并且我们要使用构造方法来初始化数组：

对于类的基本成员就结束了，接下来我们就差操作方法了，接下来看我们来看看，对于操作方法我们可以定义一个接口，便于我们管理：

那么我们如果我们的数组长度不够了，我们想要改变其数组容量的话，要怎么办？那我们是不是可以把其长度定义成成员变量，使其进行改变：

这里我们还有一个需要注意的点就是，我们这个类是实现了IList这个接口的，所以我们可以向上转型来调用方法：

Ok，我们对于这个顺序表的基本的都已经写完了，接下来我们就开始一一实现这里的方法了

2、操作代码：

display()方法：

打印顺序表。

这个是非常简单的，就是对数组的遍历，我们再一一打印出来，我们来看看代码的实现：

这个代码呢，是有一些问题的，我们用的是数组的长度，但是呢对于数组是不是可能不是每一个下标都放数据了，所以呢，我们只需要有效的数据就可以了，而且当我们有效的数据很小而我们的数组长度很大，是不是就浪费时间了呢？

所以这里哦我们呢要用有效的数组长度：

我们调用一下代码，看看会不会报错：

我们来对比下，当我们使用数组长度的时候会输出什么呢：

add(int data)方法：

新增元素，默认在数组的最后添加。在写代码之前我们先来看个图：

是不是看到这个图片，觉得对于add代码是不是非常简单呢？

是不是有人这样写的呢？

那你想的太简单了︿(￣︶￣)︿，如果我们添加数据，要是满了怎么办呢?所以不是很简单的，那么这个正确代码就是：

我们可以看到，代码执行之后是没有问题的。

add(int pos,int data)方法：

和add(int data)构成重载方法，这个是在指定的位置放入数据，我们来看看它的原理： 我们来看看代码是怎样实现的：

我们来看看其代码运行的结果会不会报错：

我们可以看到没有异常发生，我们再看看当我们pos不合法会输出什么：

contains(int toFind)方法：

查找和 toFind 这个数据相等的元素，有就返回true，没有就返回false。这个方法就是非常简单的了，就是遍历一次数组就可以了，我们来看看图：

接下来我们来看看，这个方法的代码的实现：

我们来执行一下看看：

我们可以看到没有任何的问题。

indexOf(int toFind)方法：

这个方法和上面的方法是类似的，这个是返回其toFind的下标这个位置，所以我们的代码都差不多的。

get(int pos)方法：

我们返回这个 pos 位置的下标的值，这个代码我们乍一看是不是觉得很简单呢？那你看对了，这个代码很简单，但是我们需要谨慎，我们要在这个代码执行执行之前呢，要查找两个方面是否有异常：

1、pos位置不能 < 0 或者不能 >= usedSize这个有效数组长度。
2、我们要看看我们的顺序表也就是数组是否为空

我们来看代码：

我们执行一下看看有没有问题：

set(int pos,int value)方法：

这个方法和上面的方法是类似的，我们也是需要判断两次异常，才能执行代码。

我们直接看代码和执行结果：

remove(int toRemove)方法：

这个方法呢，是删除这个第一次出现的这个toRemove这个值

我们先来看看代码的实现：

我们可以看到我们的代码是没有问题的。

size()方法：

获得数组的有效长度，这个代码是非常简单的。我们来看：

clear()方法：

这个方法也是很简单的，我们对于这些代码是不是都是对于有效长度来说的，所以当我们把有效数组长度设置为0时呢，我们是不是就把顺序表清空了呢？所以这个是非常简单的：

对于这样的clear方法只能处理一些基本的数据类型，我们正常的写法呢，应该是：

但是为什么报错呢，因为我们现在是基本数据类型，不涉及到内存的泄露，直接把有效长度赋值为0，就可以了。

我们来看一下整体的代码是什么样的：

3、整体代码：

package list;public interface IList {// 打印顺序表，注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的void display();// 新增元素,默认在数组最后新增void add(int data);// 在 pos 位置新增元素void add(int pos, int data);// 判定是否包含某个元素boolean contains(int toFind);// 查找某个元素对应的位置int indexOf(int toFind);// 获取 pos 位置的元素int get(int pos);// 给 pos 位置的元素设为 valuevoid set(int pos, int value);//删除第一次出现的关键字keyvoid remove(int toRemove);// 获取顺序表长度int size();// 清空顺序表void clear();}

package list;
import java.util.Arrays;public class MyArrayList implements IList{public int[] array;public int usedSize;//数组的有效的个数//默认的容量，长度不变的public static final int DEFAULT_SIZE = 10;public MyArrayList() {this.array = new int[DEFAULT_SIZE];//长度为十，默认初始化值为0}@Overridepublic void display() {// 打印顺序表for (int i = 0; i < this.usedSize; i++) {System.out.print(array[i] + " ");}System.out.println("");}@Overridepublic void add(int data) {// 新增元素,默认在数组最后新增if (isFull()) {//满了，不能放数据了，我们要进行扩容Expansion();}//进行添加数据的操作this.array[this.usedSize] = data;this.usedSize++;}//对于判满这个操作，我们在别的方法中也会使用//所以我们可以单独创建一个方法public boolean isFull() {//判满return this.usedSize == DEFAULT_SIZE;}private void Expansion() {//扩容操作，我们不想让别的类调用这个方法，我们只想在自己的类中调用this.array = Arrays.copyOf(this.array,2*this.array.length);//我们一般按照2倍或者1.5倍进行扩容}private void checkPos(int pos) throws PosIsNotlegally{if (pos < 0 || pos > usedSize) {throw new PosIsNotlegally("Pos位置不合法");}}@Overridepublic void add(int pos, int data) {// 在 pos 位置新增元素try{checkPos(pos);//判断pos这个位置合不合法if (isFull()) {Expansion();}int end = this.usedSize;while(pos != end) {this.array[end] = this.array[end - 1];end--;}this.array[pos] = data;this.usedSize++;}catch(PosIsNotlegally e) {System.out.println("输入的Pos位置不合法");e.printStackTrace();}}@Overridepublic boolean contains(int toFind) {// 判定是否包含某个元素for (int i = 0; i < this.usedSize; i++) {if (this.array[i] == toFind) {return true;}}return false;}@Overridepublic int indexOf(int toFind) {// 查找某个元素对应的位置for (int i = 0; i < this.usedSize; i++) {if (this.array[i] == toFind) {return i;}}return -1;}private void checkPos2(int pos) throws PosIsNotlegally{if (pos < 0 || pos >= usedSize) {throw new PosIsNotlegally("Pos的位置不合法");}}@Overridepublic int get(int pos) {// 获取 pos 位置的元素try {//判断是否出现异常checkPos2(pos);checkEmpty();//没有异常的话，直接返回pos下标的值return this.array[pos];}catch (PosIsNotlegally e) {System.out.println("pos的位置不合法");e.printStackTrace();}catch (EmptyException e) {System.out.println("顺序表为空");e.printStackTrace();}return -1;}private boolean isEmpty() {return usedSize == 0;}private void checkEmpty() throws EmptyException{if (isEmpty()) {throw new EmptyException("顺序表为空");}}@Overridepublic void set(int pos, int value) {// 给 pos 位置的元素设为 valuetry {//这个也要判断异常checkPos2(pos);checkEmpty();//没有异常给pos位置赋值this.array[pos] = value;}catch (PosIsNotlegally e) {System.out.println("pos位置不合法");e.printStackTrace();}catch (EmptyException e) {System.out.println("顺序表为空");e.printStackTrace();}}@Overridepublic void remove(int toRemove) {//删除第一次出现的关键字toRemovetry{checkEmpty();int pos = indexOf(toRemove);if (pos == -1) {return;}for (int i = pos; i < usedSize - 1; i++) {array[i] = array[i + 1];}usedSize--;}catch (EmptyException e) {System.out.println("顺序表为空");e.printStackTrace();}}@Overridepublic int size() {// 获取顺序表长度return this.usedSize;}@Overridepublic void clear() {// 清空顺序表
//        for (int i = 0; i < usedSize; i++) {
//            array[i] = null;
//        }usedSize = 0;}
}

package list;public class PosIsNotlegally extends RuntimeException{public PosIsNotlegally() {}public PosIsNotlegally(String message) {super(message);}
}

package list;public class EmptyException extends RuntimeException{public EmptyException() {}public EmptyException(String message) {super(message);}
}

四、ArrayList简介：

上面的呢，是我们用Java自己实现的 ArrayList 类，但是呢，对于Java来说呢，不像C语言，Java里面是有 ArrayList 的，不像C语言只能自己实现。

但是呢，我们自己定义的MyArrayList这个类和编译器自带的 ArrayList 这个类是大同小异的。

但是呢，在我们使用编译器里面自带的ArrayList这个类的时候我们有一些需要注意的地方：

注意：

1、ArrayList是以泛型方式实现的，在使用时必须要进行初始化。

2、ArrayList实现了RandomAccess接口，表明ArrayList支持随机访问

3、ArrayList实现了Cloneable接口，表明ArrayList是可以clone的

4、ArrayList底层是一段连续的空间，并且可以动态扩容，是一个动态类型的顺序表

对于Java自带的顺序表ArrayList来说，遍历顺序表呢就是直接打印就可以了。

五、ArrayList的使用：

1、ArrayList的构造方法：

对于我们想要是用ArrayList呢，我们是不是要先创建对象啊，所以我们来看看对于Java里自带的ArrayList的构造方法是什么样的：

对于Java自带的构造方法呢，我们有三种构造方法：

1、无参构造：

2、有参构造：

创建一个自定的参数的顺序表。

3、传表来构造：

对于都可以传入什么值，我们来看看这个构造方法的源代码：

这里是要实现了Collection这个接口，我们这个？是通配符，我们后面介绍，这里的？是E或者是E的子类

2、ArrayList的常见操作：

add方法：

1、add(E e)

相当于我们自己写的add方法，也是在尾部插入。

2、add(int index,E element)

在index位置插入element这个值。

3、addAll(Collection < ? extends E > c)

将c中的元素全部进行尾插操作。

remove方法：

1、remove(int index):

删除index下标的的元素。

2、remove(Object o)方法：

删除数据o

get(int index)方法：

获得index位置的数据

这个方法和我们自己实现的是差不多的，这里我们就不实现了

set(int index,E element)方法：

将index下标的数据设置为element

clear()方法：

清空

contains(Object o)方法：

判断o是否在顺序表中

indexOf(Object o)方法：

返回第一个o所出现的下标

lastIndexOf(Object o)方法：

返回最后一个o的下标。

这些方法呢，和我们自己实现的都差不多，这里我就不在重复实现了。