【数据结构】线性表（ List）和 顺序表（ArrayList）

一、线性表 List

1. 线性表定义：具有多个元素，且元素之间为一个挨着一个。
2. 线性表特点：每个元素，都只有一个前驱，一个后继。

3. 线性表再往下细分，又分为两种实现方式：

• 顺序表 ==> 数组（经过封装后的数组，就称为顺序表）
• 链表
  

顺序表和链表 最本质的区别：

（1） 顺序表上的元素 在连续的内存空间上（物理上和逻辑上都是线性的）
（2） 链表上的元素，则不要求连续。通过一些其他的方式，来把前驱和后继联系起来。
（逻辑上是线性的，有前有后；物理上，放在离散的空间也可以）

4. 在集合框架中，List 是⼀个interface（接⼝），继承自Collection（Collection 是标准库里内置的高级接口）。
   List 定义了一个线性表，应该支持哪些功能，这些具体的功能，交给实现 List 的类来完成。

Java 中，实现 List 的类，核心是两个：
（1）ArrayList 对应到 顺序表
（2）LinkedList 对应到 链表

学习 数据结构中 的 顺序表 和 链表，分别对应 Java 中 ArrayList 和 LinkedList 这两个类的使用。

二、List 接口的常用方法

和 StringBuilder 很相似，StringBuilder 管理的是一系列的 char，而此处 List 是泛型的，可以管理任何需要的对象。

三、ArrayList与顺序表

3.1 引入顺序表的原因？

• 对于数组来说，只能通过 [ ] 数组下标 来 取 / 修改 元素，.length 获取长度。
• 而我们希望顺序表能够具备更多的功能：将下面的方法写一个类，把数组包裹一下，后续再给这个类提供这些方法的实现，更方便得使用这个顺序表。
  
• 所以，在以后的开发中，很少直接使用数组，能用ArrayList 就用 ArrayList。

3.2 ArrayList 的使用

3.2.1 ArrayList 的创建

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.List;public class Demo4 {//ArrayList的使用public static void main(String[] args) {//创建 ArrayList 对象，构造空的顺序表//（1）创建ArrayList对象，方式1ArrayList<String> arrayList= new ArrayList<>();//空盒子，盒子里没有东西，盒子本体还在//ArrayList就是带有泛型参数的类//创建ArrayList对象，就根据泛型的语法创建ArrayList<String> arrayList2 = null;//（3）连盒子都没有//（2）创建ArrayList对象，方式2List<String> list= new ArrayList<>();//向上转型//ArrayList类定义的时候，实现了List 接口//完全可以使用 List引用 指向 ArrayList 实例，这就是向上转型//(4)使用 arrayList 复制一份，生成 arrayList3ArrayList<String> arrayList3 = new ArrayList<>(arrayList);//(5)构造ArrayList的同时，可以取指定初始容量ArrayList<String> arrayList4 = new ArrayList<>(10);//10 :当前构造出的 ArrayList，初始容量是10个元素//区别于数组：数组，创建好之后，容量就固定了，new int[]；//而ArrayList可以动态扩容，只要机器的内存足够用，就能一直持续扩容，保证元素否能被容纳进去（顺序表的一个核心功能）}
}

3.2.2 添加元素：list.add( )

import java.util.ArrayList;
import java.util.List;public class Demo5 {public static void main(String[] args) {//(6) .add(): 往ArrayList 添加元素List<String> list = new ArrayList<>();list.add("aaa");list.add("bbb");list.add("ccc");System.out.println(list);//[aaa, bbb, ccc]//Java中，集合类一般都可以直接打印//add这样的方法，内部就会涉及到自动扩容}
}

3.2.3 获取List元素个数：list.size()

import java.util.ArrayList;
import java.util.List;public class Demo6 {public static void main(String[] args) {List<String> list = new ArrayList<>();//(7)获取元素个数//数组提供了.length 属性，获取到元素个数；//ArrayList 也提供了.size()方法，获取元素个数list.add("aaa");list.add("bbb");list.add("ccc");System.out.println(list.size());//3}
}

数组通过 .length 属性 获取长度；
String 是通过 .length() 方法获取长度；
集合类（不仅仅是List）是通过.size() 方法 获取长度。

3.2.4 获取List 中的元素 / 设置 List 中的元素：list.get()

import java.util.ArrayList;
import java.util.List;public class Demo7 {public static void main(String[] args) {List<String> list = new ArrayList<>();//(8) 获取List 中的元素 / 设置 List 中的元素list.add("aaa");list.add("bbb");list.add("ccc");System.out.println(list.get(0));//aaaSystem.out.println(list.get(1));//bbbSystem.out.println(list.get(2));//ccc}
}

3.2.4 修改 List 中的元素：list.set()

import java.util.ArrayList;
import java.util.List;public class Demo8 {public static void main(String[] args) {List<String> list = new ArrayList<>();list.add("aaa");list.add("bbb");list.add("ccc");//(9) 修改 List 中的元素list.set(0,"eee");System.out.println(list);//[eee, bbb, ccc]}
}

List 是通过 get 和 set 操作下标，为什么不让 List 像数组一样，直接用[ ] 来获取 / 修改 元素？

• 数组直接用[ ] 来获取 / 修改 元素，称为运算符重载；
• 回顾之前的方法重载：同一个类或者同一个作用域中，有多个同名的方法（只要参数不一样），就可以视为方法重载。
• C++ / Python 也支持 运算符重载，也就是针对自己定义的类，可以指定让这个类，能够支持某个运算符并且定义该运算符的行为。（此处数组的[ ] ，属于下标访问运算符）
• 但是Java 中，没有采纳这样的运算符重载。

3.2.5 遍历 List 中的元素：下标 + for each / 迭代器

import java.util.ArrayList;
import java.util.List;public class Demo9 {public static void main(String[] args) {List<String> list = new ArrayList<>();list.add("aaa");list.add("bbb");list.add("ccc");//(10)遍历 List 中的元素，方式1：fori循环//遍历是可能会进行各种操作的，不局限于打印for (int i = 0; i < list.size(); i++) {System.out.println(list.get(i));}//遍历 List 中的元素，方式2：for each写法for (String s:list){System.out.println(s);/*      aaabbbccc*/}}
}

1. 遍历 List 中的元素 方式2 的 for each写法，不是所有类都可以这样写。要求这个类，必须实现Iterable接口。


2. “迭代和迭代器”是什么？
（1）迭代：一小步一小步的，逐渐接近；使用场景：集合类中，会用到迭代。
（2）迭代器：通过这样的对象，可以实现“迭代”的效果。

3.2.6 在指定位置，添加元素：list.add(1,“111”)

import java.util.ArrayList;
import java.util.List;public class Demo10 {public static void main(String[] args) {List<String> list = new ArrayList<>();list.add("aaa");list.add("bbb");//(11)在指定位置，添加元素//注意这里下标的含义：往指定下标之前插入元素 / 添加完毕后新元素的下标，就是这个数值/*    list.add(1,"111");System.out.println(list);//[aaa, 111, bbb]*///虽然list中不存在下标为2的元素，但是此处的添加，就相当于尾插list.add(2,"111");System.out.println(list);//[aaa, bbb, 111]}
}

3.2.7 删除元素： list.remove( )

import java.util.ArrayList;
import java.util.List;public class Demo11 {public static void main(String[] args) {List<String> list = new ArrayList<>();list.add("aaa");list.add("bbb");list.add("ccc");list.add("ddd");//(11)删除元素//a.按照下标来进行删除:删除下标为1的元素list.remove(1);System.out.println(list);//[aaa, ccc, ddd]//b.按照元素内容来进行删除list.remove("ccc");System.out.println(list);//[aaa, ddd]}
}

（1）如果list不是String类型，而是Integer类型的； remove删除是 通过 下标 删除的，而不是删除2这个元素。

（2）删除元素2的方法

3.2.8 判断元素是否存在：contains

import java.util.ArrayList;
import java.util.List;public class Demo13 {public static void main(String[] args) {List<String> list = new ArrayList<>();list.add("aaa");list.add("bbb");list.add("ccc");list.add("ddd");//（12）通过 contains 判断元素是否存在//是通过 equals 方法来判定的，字符串内容相同，就能判定存在；而不是非得是同一个对象。System.out.println(list.contains("aaa"));//true}
}

3.2.9 查询元素的位置：indexOf / lastIndexOf

import java.util.ArrayList;
import java.util.List;public class Demo14 {public static void main(String[] args) {List<String> list = new ArrayList<>();list.add("aaa");list.add("bbb");list.add("ccc");list.add("ddd");list.add("ccc");list.add("ccc");//(13)通过 indexOf 获取元素的位置System.out.println(list.indexOf("ccc"));//2：从前往后找，第一个ccc的下标System.out.println(list.indexOf("hhh"));//hhh不存在，则返回-1//通过 lastIndexOf 获取最后一次出现的元素的位置System.out.println(list.lastIndexOf("ccc"));//5}
}

3.2.10 获取顺序表中的 “子列表” ： sublist

String 作为不可变对象，它的subString 就不存在这样的问题。

3.2.11 清空整个顺序表： clear

import java.util.ArrayList;
import java.util.List;public class Demo16 {public static void main(String[] args) {List<String> list = new ArrayList<>();list.add("aaa");list.add("bbb");list.add("ccc");//通过 clear 清空 list 中的元素list.clear();//这里得到的是空盒子，与list = null 是有本质区别的}
}

Java 中存在“垃圾回收”机制（GC）：

• 无论通过 remove 删除的元素；
• 还是通过 clear 删除的元素；
• 还是通过 list = null ；
  List 中包含的所有的元素的内存空间，都能被释放掉，都是JVM手工完成的，不需要手工干预。

3.2.12 ArrayList 的扩容机制

在 ArrayList 内存空间不够的时候，自动申请额外的内存空间。

import java.util.ArrayList;
import java.util.List;public class Demo17 {public static void main(String[] args) {//关于自动扩容List<String> list = new ArrayList<>(10);for (int i = 0; i < 30; i++) {list.add("hello");}System.out.println(list);}
}

ArrayList 内部持有一个数组；设置的初始容量，相当于一个数组的大小。

new String[10] ; 就是 add的时候，把新元素从0放到9，第11次add的时候，就发现当前的元素已经满了。
（1）add真正写入元素之前，创建一个更大的数组，new String[20]。
（2）把旧数组里面的元素，拷贝到新的数组中。
（3）把新的元素添加到新数组里面。
（4）释放旧的数组。

ArrayList 扩容策略：
（1）如果调用不带参数的构造⽅法，第一次分配数组大小为10。
（2）每次扩容，容量变成之前的1.5倍。

四、 ArrayList 的具体使用

4.1 洗牌和发牌 算法

一副扑克牌 54张，去除2张大小王，剩下的52张 分为：
4种花色（黑桃、红桃、梅花、方块），13个点数（2-10+A+J+Q+K）。

（1）洗牌和发牌 代码实现：

package ArrayList;import java.util.ArrayList;
import java.util.Collections;
import java.util.Random;//1. 这个类的对象表示 一张牌
class Card{private String suit;//花色 suitprivate String rank;//点数 rankpublic Card(String suit, String rank) {//构造方法this.suit = suit;this.rank = rank;}//suit和rank的get / set 方法public String getSuit() {return suit;}public void setSuit(String suit) {this.suit = suit;}public String getRank() {return rank;}public void setRank(String rank) {this.rank = rank;}@Overridepublic String toString() {return this.suit + this.rank ;}
}
public class Demo1 {public static void main(String[] args) {//使用 ArrayList 表示一副扑克牌ArrayList<Card> deck = creatDeck();System.out.println("原始牌组：" + deck);//洗牌/*     //标准库自带的洗牌功能Collections.shuffle(deck);*/shuffle(deck);System.out.println("洗牌之后：" + deck);//4.发牌：假设有三个人，每个人发5张牌ArrayList<ArrayList<Card>> hands= new ArrayList<>();//相当于 3行5列 的二维数组//也是一个ArrayList，里面的每个元素都是一个ArrayList；//当前这个ArrayList的长度为0（空的盒子）；//现在需要 往里面添加三个元素，表示3个玩家的手牌//先创建 3个人手里的牌的 ArrayListfor (int i = 0; i < 3; i++) {ArrayList<Card> hand = new ArrayList<Card>();//每个人的手牌//此时这个二维数组，已经添加了3个元素进去了；但是每个元素，还是长度为0的ArrayListhands.add(hand);}//3个人，一人发五张牌for (int i = 0; i < 5; i++) {//一人发五张牌for (int j = 0; j < 3; j++) {//发牌是轮流的过程：先取第一张牌发给第1个人；再发给第2个人；再发给第3个人ArrayList<Card> currentHand = hands.get(j);Card card = deck.remove(0);currentHand.add(card);}}//打印每个人的手牌for (int i = 0; i < 3; i++) {System.out.println("第" + i + "个人的手牌" + hands.get(i));}}//3. 自定义的洗牌操作public static void shuffle(ArrayList<Card> deck){//（1）把整个 ArrayList 从后往前遍历//（2）针对每次取到一张牌，就生成一个随机下标。拿着当前位置的牌和随机下标位置的牌，进行交换。Random random = new Random();for (int i = deck.size() - 1; i > 0 ; i--) {int j = random.nextInt(deck.size());//确保当前生成的下标，是有效的//交换两张牌的位置Card tmp =  new Card(deck.get(i).getSuit(),deck.get(i).getRank());deck.set(i,deck.get(j));deck.set(j,tmp);}}public static ArrayList<Card> creatDeck(){//2. 创建一副扑克牌ArrayList<Card> deck = new ArrayList<Card>();String[] suits = {"♠","♥","♦","♣"};//花色for(String suit:suits){//在每个花色中，生成对应的点数 的牌for (int i = 2; i <= 10 ; i++) {Card card = new Card(suit,"" + i);deck.add(card);//2-10}Card cardJ = new Card(suit,"J");Card cardQ = new Card(suit,"Q");Card cardK = new Card(suit,"K");Card cardA = new Card(suit,"A");deck.add(cardJ);deck.add(cardQ);deck.add(cardK);deck.add(cardA);}return deck;}
}

（2）输出结果：

原始牌组：[♠2, ♠3, ♠4, ♠5, ♠6, ♠7, ♠8, ♠9, ♠10, ♠J, ♠Q, ♠K, ♠A, ♥2, ♥3, ♥4, ♥5, ♥6, ♥7, ♥8, ♥9, ♥10, ♥J, ♥Q, ♥K, ♥A, ♦2, ♦3, ♦4, ♦5, ♦6, ♦7, ♦8, ♦9, ♦10, ♦J, ♦Q, ♦K, ♦A, ♣2, ♣3, ♣4, ♣5, ♣6, ♣7, ♣8, ♣9, ♣10, ♣J, ♣Q, ♣K, ♣A]
洗牌之后：[♣8, ♦6, ♦7, ♥J, ♠4, ♣J, ♥A, ♦10, ♦9, ♣2, ♠3, ♥6, ♦J, ♠5, ♦2, ♠K, ♠10, ♠9, ♦K, ♦3, ♦5, ♥2, ♣6, ♥7, ♦Q, ♥Q, ♥5, ♠6, ♠7, ♦8, ♠A, ♥10, ♣9, ♥9, ♥8, ♥3, ♣4, ♠2, ♥4, ♣5, ♦A, ♠Q, ♣10, ♣3, ♣7, ♣K, ♣Q, ♠8, ♠J, ♣A, ♦4, ♥K]

4.2 杨辉三角

（1）力扣链接：LC118. 杨辉三角

（2）杨辉三角 规律图解

（3）杨辉三角 代码实现

package ArrayList;//ArrayList的具体使用2：杨辉三角import java.util.ArrayList;
import java.util.Date;
import java.util.List;public class Demo2 {public List<List<Integer>> generate (int numRows){List<List<Integer>> result = new ArrayList<List<Integer>>();//二维数组for (int i = 0; i < numRows; i++) {//构造 numRows 行List<Integer> row = new ArrayList<Integer>();//向上转型：ArrayList是具体实现的子类，List是更上层的父类（接口）for (int j = 0; j < i + 1; j++) {if(j == 0 || j == i){//杨辉三角的第一列和最后一列，都是1row.add(1);}else {//一般的列，值为：result[i-1][j-1] + result[i-1][j]int current = result.get(i-1).get(j-1) + result.get(i-1).get(j);row.add(current);}}//此处，已经把一行构造好了，只需要把这一行整体 添加到 result 中result.add(row);}return result;}public static void main(String[] args) {Demo2 demo = new Demo2();List<List<Integer>> result= demo.generate(5);System.out.println(result);}
}

输出结果：

五、 基于数组，自己实现 ArrayList

前面学习的 ArrayList，是Java中已经实现好的。那么如何基于数组，自己实现 ArrayList 呢？

package ArrayList;//自己实现一个简单的顺序表
//已知：标准库的顺序表,带有泛型参数
//此处，以 int 为例进行表示，就不写泛型了。
public class MyArrayList {//通过 arr数组 真正去存储数据，顺序表本身就是基于数组的封装。private int[] arr;//约定 arr 中前 size 个元素，表示有效元素。private int size = 0;//通过 size 标记 哪些有效，哪些无效。//此时，如果 arr 的new int[10] 是10，但是 size 仍然为0；//此时，ArrayList 也视为“空盒子”。//当后续 add 去添加元素的时候，就去变更 size：添加一个元素，size + 1;//size为几，就意味 有效元素有几个。//则[0,size) 就是整个 arr 中有效元素的部分；[size,arr.length) 就是无效元素的部分。 这是 MyarrayList 的正式代码  ///public MyArrayList(){//MyArrayList构造方法，无参数版//无参数版本，默认容量为10arr = new int[10];}public MyArrayList(int capacity) {arr = new int[capacity];//后续使用add操作，叫做添加有效元素。//而此处设定的new int[10]，只是创建了这么大的空间，这些空间上的元素都是“无效”的。//这里一new，顺序表只是个“空盒子”，并非长度为10。}//(1)获取元素个数public int size(){return size;}//（2）新增元素：尾插public void add(int val){//把新的元素放到最后一个位置上，下标为 size 的位置//[0,size) 区间//如果当前的size比较小，没有达到数组的容量，直接进行上述操作就行了；// 如果数组已经满了，就得先扩容if(size == arr.length){//数组满了，需要先扩容resize();}arr[size] = val;size++;}//扩容private void resize(){//1.先创建一个更长的数组，ArrayList的容量扩展到1.5倍int[] newArr = new int[(int)(arr.length * 1.5)];//ArrayList 标准库中扩容的实现：arr.length + (arr.length >> 1)// 右移1位 相当于 乘以0.5；也就是 arr.length * 1.5//2. 把原来数组的元素复制到新数组上for (int i = 0; i < size; i++) {newArr[i] = arr[i];}//3. 用新的数组 替代 旧数组//此时，旧的数组空间 就会被垃圾回收 给释放掉（Java中由JVM自行完成）arr = newArr;}//(3)任意位置，新增public void add(int index,int val){//1.把index及其往后的元素，都给往后依次挪一步,并且是从后往前挪// 2. 具体搬多少次，取决于i的位置;i越靠前，搬运的次数就会越多，时间复杂度为O（N）//3. 尾插，不需要搬运。所以尾插的时间复杂度通常 为O(1);// 但尾插若触发扩容，时间复杂度就不是O(1);一旦扩容,也会触发搬运(搬运整个数组)，时间复杂度为O(N).if(index < 0 || index > size){throw new IndexOutOfBoundsException("Index out of bounds");}//如果数组已经满了，继续添加元素，也是要先扩容if(size == arr.length){resize();}//搬运元素的操作，从后往前，依次把这个元素都往后搬运一个位置//如果元素本身的下标是 i，就把这个元素赋值到 i+1 的位置上//index 位置上的元素，也需要往后搬运一下，i >= indexfor (int i = size - 1; i >= index ; i--) {arr[i+1] = arr[i];}//此时，就相当于把 index 位置已经腾出来了。把新元素放到 index 位置上就好了arr[index] = val;//不要忘记更新sizesize++;}//      顺序表支持随机访问，get / set 的时间复杂度都是O(1)      ////(4)根据下标，获取元素public int get(int index){if(index < 0 || index >= size){throw new IndexOutOfBoundsException("下标越界：" + index);}return arr[index];}//(5)根据下标，设置元素public void set(int index,int val){if(index < 0 || index >= size){throw new IndexOutOfBoundsException("下标越界：" + index);}arr[index] = val;}//(6)按照下标，删除元素(希望 remove 返回被删除的元素 )public int remove(int index){//给定下标，进行删除 ：//对于尾删的情况，直接进行size--即可，不需要搬运if (index < 0 || index >= size){//在插入的时候，index 可以 == size（尾插）//而删除的时候，index ==  size，位置不合法throw new IndexOutOfBoundsException("下标越界：" + index);}int result = arr[index];//这个逻辑，已经涵盖到下面的一般情况了，无需单独列出
//            if(index == size -1){
//                //尾删
//                size--;
//                return result;
//            }//边界值，非常容易出错！一定要带入具体的数据，分析for (int i = index; i < size -1; i++) {//带入实际值，进行分析arr[i] = arr[i+1];}//不要忘记size--;size--;return result;}//(7)按照值，删除元素public void delete(int val){//这里的delete是 remove（的重载版本/* //1. 先找到这个值 所在的位置int index = 0;for (index = 0; index < size; index++) {if(arr[index] == val){//查找过程中的比较：//由于顺序表元素是int类型，所以可以直接使用 == 比较//如果是 其他类型(String 或者 对象)，就需要用 equals 来比较break;//找到了}}if(index == size){//没有找到，元素不存在//不必进行删除了return;}*/int index = indexOf(val);if(index == -1){return;}//2. 然后通过上述 remove 的过程进行搬运式的删除//index 就是要删除的元素位置/*            for (int i = index; i < size - 1; i++) {arr[i] = arr[i+1];}size--;*/remove(index);}//(8)判定元素是否存在public boolean contains(int val){for (int i = 0; i < size; i++) {if(arr[i] == val){return true;}}return false;}//(9)查找元素所在的位置public int indexOf(int val){for (int i = 0; i < size; i++) {if(arr[i] == val){return i;}}return -1;}public int lastIndexOf(int val){for (int i = size - 1; i >= 0;i--) {if(arr[i] == val){return i;}}return -1;}//(10)清空public void clear(){//删除所有元素，逻辑删除即可size = 0;//1. 不需要把 每个元素都设为0,/*         for (int i = 0; i < size; i++) {arr[i] = 0;}*///2.不需要将数组置空。clear清空元素，清空之后，这个顺序表还要接着用//arr = null;//3.也不需要缩容 。因为一般编程过程中，内存空间不足，不是主要矛盾。//arr = new int[10];}//(11)打印操作：利用toString方法，把 MyArrayList 转化为字符串@Overridepublic String toString(){//打印格式形如：[1,2,3,4]StringBuilder stringBuilder = new StringBuilder();stringBuilder.append("[");for (int i = 0; i < size; i++) {stringBuilder.append(arr[i]);if(i < size - 1){//i == size - 1时，就是最后一个元素，最后一个元素不添加 [stringBuilder.append(",");}}stringBuilder.append("]");return stringBuilder.toString();}//     下面是测试代码  //private static void test1(){//测试尾插功能MyArrayList list = new MyArrayList();//添加16个元素，触发两次扩容list.add(1);list.add(2);list.add(3);list.add(4);list.add(1);list.add(2);list.add(3);list.add(4);list.add(1);list.add(2);list.add(3);list.add(4);list.add(1);list.add(2);list.add(3);list.add(4);System.out.println(list.size);System.out.println(list);}public static void test2(){//测试中间位置插入功能MyArrayList list = new MyArrayList(10);list.add(1);list.add(2);list.add(3);list.add(0,100);list.add(1,200);list.add(2,300);System.out.println(list);}public static void test3(){MyArrayList list = new MyArrayList(10);list.add(1);list.add(2);list.add(3);list.add(4);list.add(5);list.add(6);list.add(7);list.remove(0);System.out.println(list);list.remove(2);System.out.println(list);list.remove(4);System.out.println(list);list.remove(100);System.out.println(list);}private static void test4(){MyArrayList list = new MyArrayList(10);list.add(1);list.add(2);list.add(3);list.add(4);list.add(5);list.add(6);list.add(7);list.delete(3);System.out.println(list);list.delete(5);System.out.println(list);list.delete(100);System.out.println(list);}private static void test5(){MyArrayList list = new MyArrayList(10);list.add(1);list.add(2);list.add(3);list.add(4);list.add(5);list.add(6);list.add(7);if(list.contains(3)){System.out.println("OK");}else{System.out.println("failed");}if(list.contains(100)){System.out.println("OK");}else{System.out.println("failed");}if(list.indexOf(3) == 2){System.out.println("OK");}else{System.out.println("failed");}if(list.indexOf(100) == -1){System.out.println("OK");}else{System.out.println("failed");}if(list.lastIndexOf(5) == 4){System.out.println("OK");}else{System.out.println("failed");}if(list.lastIndexOf(100) == -1){System.out.println("OK");}else{System.out.println("failed");}/* System.out.println(list.contains(3));System.out.println(list.contains(100));System.out.println(list.indexOf(5));System.out.println(list.indexOf(100));System.out.println(list.lastIndexOf(7));System.out.println(list.lastIndexOf(100));*/list.clear();  // 直接调用，不清空System.out.println("List cleared!");  // 打印提示信息}public static void main(String[] args) {//test1();//test2();//test3();//test4();test5();}
}

【总结】

1. 搬运是顺序表中核心的过程（插入 / 删除），因为数组本身不擅长中间位置的插入和删除。
2. 其他的 尾插、尾删、get、set 都是比较高效的操作，时间复杂度为O(1)。
3. contains、indexOf、lastIndexOf 操作，虽然时间复杂度为O(N)，但代码比较简单。
4. 扩容操作：
   （1）需要申请新空间，拷⻉数据，释放旧空间。会有不小的消耗。
   （2）⼀般是呈2倍的增⻓，势必会有⼀定的空间浪费。例如当前容量为100，满了以后增容到200，再继续插入了5个数据，后⾯没有数据插⼊了，那么就浪费了95个数据空间。

为了解决这些问题，引入了“链表”这样的结构；虽然链表能解决这些问题，但也引入了不少问题。
因此，实际开发中，还是以 顺序表 使用的情况更多。