编辑
前言
大家好，我还是那个不会打拳的程序猿。本期给大家带来的是数据结构之线性表是什么，顺序表、模拟实现ArrayList中的方法、ArrayList的使用、顺序表的优缺点等等。
编辑
目录
1.什么是线性表
线性表是n具有相同特性的数据元素的有限序列，它在数据结构中时常出现。常见的线性表有：顺序表、链表、栈、队列等等。
下图为顺序表的一个简图：
编辑
下图为链表的一个简图：
编辑
今天我们主要学习的是顺序表，通过上图我们可以了解到顺序表就是一个数组。没错，它就是一个数组，只是顺序表相对与数组来说更有逻辑性一些。下面我就来讲解顺序表是什么，以及顺序表实现的一些方法。
2.顺序表
顺序表是一组连续存储单元来储数据元素的线性结构，一般使用数组来存储。实现数据的增删改查。
ArrayList是个动态数组，实现List接口，主要用来存储数据，如果存储基本类型的数据，如int，long，boolean，short，byte，那只存储它们对应的包装类。
2.1模拟实现List接口中的方法
接口中的方法有：
public class SeqList { // 打印顺序表 public void display() { } // 新增元素,默认在数组最后新增 public void add(int data) { } // 在某下标位置新增元素 public void add(int pos, int data) { } // 判定是否包含某个元素 public boolean contains(int toFind) { return true; } // 查找某个元素对应的位置 public int indexOf(int toFind) { return -1; } // 获取某下标的元素 public int get(int pos) { return -1; } // 给pos下标位置的元素修改为value public void set(int pos, int value) { } //删除第一次出现的关键字key public void remove(int toRemove) { } // 获取顺序表长度 public int size() { return 0; } // 清空顺序表 public void clear() { } }
那么这些，接口方法就是ArrayList底层的源码实现。当我们实例化一个ArrayList时调用的就是这些方法。比如:
编辑
因此，我们来实现这些接口方法，让我们理解ArrayList底层是怎样工作的。在以后我们进行调用这些方法时，知道它是用来进行什么样的操作的！
2.1.1创建顺序表
public class ArrayList { //常量 public static final int DEFAULT_SIZE = 10; //下标的有效值 public int useSize; //初始化一个数组 public int[] arr = new int[DEFAULT_SIZE]; public void myArratList() { this.arr = new int[DEFAULT_SIZE]; } }
以上代码中useSize为有效数据下标值，并且创建了一个arr数组。此时arr数组里面没有任何的元素，我们可以通过add方法来添加，add方法会在下方讲解。
2.1.2遍历顺序表
public void disPlay() { //遍历顺序表 for (int i = 0; i < useSize; i++) { System.out.println(arr[i]); } }
遍历数组我们直接使用for循环来遍历即可，但上述代码中我还没添加任何的元素，因此遍历的为空。
2.1.3判断顺序表是否满了
//判断顺序表是否满了 public boolean isFull() { return this.useSize == arr.length; }
判断顺序表是否满了，我们直接拿当前有效数据下标与数组的总长度进行比较即可，也急速useSize与arr.length进行比较。
2.1.4新添元素
//新添元素 public void add(int date) { if (isFull()) { this.arr = Arrays.copyOf(arr,2*arr.length); } this.arr[useSize] = date; useSize++; }
新添元素，我们得先判断这个数组是否满了。如果满了，我们就得先把数组进行扩容，在扩容的基础上我们才能新添元素。在上述代码中，默认按照顺序表最后一位处增添，还有Arrays.copyOf方法的作用是使数组扩大输入的倍数，如Arrays.copuOf(数组名,扩大倍数);。
2.1.5判断顺序表是否包含某个元素
//判断是否包含某个元素 public boolean contains(int toFind) { for (int i = 0; i < this.useSize; i++) { if (toFind == arr[i]) { return true; } } return false; }
判断顺序表中是否有某个元素，我们直接通过for循环遍历来寻找即可，通过判断语句依次访问数组中的每个元素有则返回true无则返回false。
2.1.6查找某个元素位置
//查找某个元素的位置(下标) public int indexOf(int toFind) { for (int i = 0; i < this.useSize; i++) { if (toFind == arr[i]) { return i+1; } } return -1; }
查找某个元素的位置也就是下标，跟查找是否有某个元素是一样的。直接用for循环遍历，直至找到该元素返回下标，如果没有则返回-1。因为数组里面是没有下标为-1的元素的。
2.1.7获取某下标的元素
//获取某下标的值 public int getNum(int pos) { isLegal2(pos); return this.arr[pos]; }
获取某下标的元素首先我们得先检查这个下标是否合法，一个下标是否合法的体现为，它不能小于0，它不能大于有效下标。因此我们设置一个isLegal2方法来判断。
//判断是否合法 public void isLegal2(int pos) { if (pos <0 || pos>=this.useSize) { throw new IndexOutOfException("输入的下标不合法"); } }
当我们的下标并不合法时候，我们又可以自定义一个异常来提示这个下标不合法，因此我们可以新建一个名为IndexOutOfException的方法继承RuntimeException(运行时异常)。当我们下标不合法就会抛出该异常。
public class IndexOutOfException extends RuntimeException{ public IndexOutOfException() { }; public IndexOutOfException(String msg){ super(msg); } }
2.1.8修改元素
//修改元素 public void set(int pos,int date) { isLegal2(pos); this.arr[pos] = date; }
修改元素也是需要判断下标的合法性，因此可以复用上述获取某下标的元素中的isLegal2方法来判断是否合法
2.1.9删除第一次出现的关键字
//删除第一次出现的元素 public boolean delFirst(int date) { int flag = indexOf(date); if (flag == -1) { return false; } for (int i = flag; i < useSize; i++) { this.arr[flag] = this.arr[flag+1]; } this.useSize--; this.arr[useSize] = 0; return true; }
当我们删除了第一次出现的关键字后，我们得把当前的有效下标数进行自减一次。
2.1.10获取顺序表的长度
//获取顺序表长度 public int size() { return this.useSize; }
获取顺序表的长度也是非常简单的，我们只需要返回有效下标的值即可。主要不要返回数组总长度，因为一个数组里不一定有元素。
2.1.11清空顺序表
//清空顺序表 public void clearArrayList() { for (int i = 0; i < this.useSize; i++) { this.arr[i] = 0; } this.useSize = 0; }
清空顺序表因为不考虑顺序表里面有引用类型，我们只要把顺序的所有元素置为0就行，当顺序表里面为引用类型时就置为null。
3.ArrayLIst的使用
3.1ArrayList进行构造
| 方法 | 解释 |
| ArrayList() | 无参进行构造 |
| ArrayList(Collection <? extends E> c) | 利用其他的Collection来进行创建ArrayList |
| ArrayList(int initialCapacity) | 指定顺序表初始化内容 |
public class Test { public static void main(String[] args) { //不指定长度，最常见的用法 List<Integer> list1 = new ArrayList<>(); //指定顺序表的长度为5 List<Integer> list2 = new ArrayList<>(5); list1.add(1); //报错,因为list1中的类型为整型不得存放字符串型 list1.add("abc"); //list3内容与list1一致 List<Integer> list3 = new ArrayList<>(list1); //没有指明泛型类中的泛型类 List list4 = new ArrayList<>(); list4.add(1); list4.add("abc"); } }
编辑
以上就是对顺序表的几种构造方式。
3.2ArrayLIst的使用
| 方法 | 解释 |
| boolean add(E e) | 尾插 e(最后一位开始插入) |
| void add(int index, E element) | 将 e 插入到 index 位置 |
| boolean addAll(Collection<? extends E> c) | 尾插 c 中的元素 |
| E remove(int index | 删除 index 位置元素 |
| boolean remove(Object o) | 删除遇到的第一个 o |
| E get(int index) | 获取下标 index 位置元素 |
| E set(int index, E element) | 将下标 index 位置元素设置为 element |
| void clear() | 清空所有元素 |
| boolean contains(Object o) | 判断 o 是否在线性表中 |
| int indexOf(Object o) | 返回第一个 o 所在下标 |
| int lastIndexOf(Object o) | 返回最后一个 o 的下标 |
| List<E> subList(int fromIndex, int toIndex) | 截取部分 list |
以上表格中的方法，我们在2.模拟实现接口中的方法中已经给大家展示到了。 现在我们使用ArrayList来实现一下这些方法:
public class Test { public static void main(String[] args) { //实例化一个泛型类为Integer的ArrayList List<Integer> list = new ArrayList<>(); //add来添加5个元素 list.add(11); list.add(12); list.add(13); list.add(14); list.add(15); //输出该顺序表 System.out.println(list); //将6插入到4下标的位置 list.add(4,6); //输出顺序表 System.out.println(list); //去除4下标位置的元素 list.remove(4); //输出顺序表 System.out.println(list); //得到2下标的值并输出 System.out.println(list.get(2)); //把0下标的值修改为9 list.set(0,9); System.out.println(list); } }
运行后输出:
编辑
以上代码，就是对ArrayList中的一些方法进行的一些操作，当然我只是演示了一部分。感兴趣的伙伴可以下来自行测试！
3.3ArrayList进行遍历
ArrayLIst遍历方式有三种:for循环进行遍历、foreach进行遍历、迭代器进行遍历。
(1)for循环遍历
public class Test { public static void main(String[] args) { //实例化一个Integer类型的list引用 List<Integer> list = new ArrayList<>(); //添加5个元素 list.add(1); list.add(2); list.add(3); list.add(4); list.add(5); //for循环进行遍历 for (int i = 0; i < list.size(); i++) { System.out.print(list.get(i)+" "); } } }
运行后输出：
编辑以上代码，通过list.size()方法来获取顺序表中的有效下标，并且通过get()方法来获取i下标中的元素。
(2)foreach遍历
public class Test { public static void main(String[] args) { List<Integer> list = new ArrayList<>(); //添加5个元素 list.add(1); list.add(2); list.add(3); list.add(4); list.add(5); //foreach进行遍历 for (Integer integer:list) { System.out.print(integer+" "); } } }
运行后输出:
编辑
foreach就比较方法了，直接用一个Integer类的数据，直接访问了顺序表中的每个元素。
(3)迭代器遍历
public class Test { public static void main(String[] args) { List<Integer> list = new ArrayList<>(); //添加5个元素 list.add(1); list.add(2); list.add(3); list.add(4); list.add(5); //使用迭代器实现 Iterator<Integer> it = list.listIterator(); while(it.hasNext()){ System.out.print(it.next() + " "); } System.out.println(); } }
运行后输出：
编辑
通过上文中的接口方法我们可以看到顺序有一些不足，顺序表优缺点：
优点:查找数据非常的方便，当我们查一个数据时我们直接使用下标即可访问。因此它的时间复杂度为O(1)。
缺点：插入和删除、扩容。插入或删除数据非常得麻烦，当我们插入一个数据时，我们必须把插入值的下标往后的下标，依次一个个的往后移。当我们的顺序表满的时候，我们还得进行扩容，扩容会造成我们空间的浪费。比如我们的顺序表长度为100，我进行扩容数组1.5，我只需要存储一个元素，因此浪费了49个空间。
因此，为了插入、删除、扩容更方便的去操作。我们有了链式存储这个数据结构，这个结构我们称为链表。下期我会给大家讲解。
对顺序表接口方法进行讲解是为了我们更好的去使用，也是为了让我们了解到这些接口方法底层是怎样进行操作的，本期博客到这里就结束了，感谢你的阅读。
编辑
下期预告:ArrayList实现大众麻将、扑克牌洗牌操作。
