【数据结构】线性表（ List）和 顺序表（ArrayList）
- 一、线性表 List
- 二、List 接口的常用方法
- 三、ArrayList与顺序表
-
- 3.1 引入顺序表的原因？
- 3.2 ArrayList 的使用
-
- 3.2.1 ArrayList 的创建
- 3.2.2 添加元素：list.add( )
- 3.2.3 获取List元素个数：list.size()
- 3.2.4 获取List 中的元素 / 设置 List 中的元素：list.get()
- 3.2.4 修改 List 中的元素：list.set()
- 3.2.5 遍历 List 中的元素：下标 + for each / 迭代器
- 3.2.6 在指定位置，添加元素：list.add(1,"111")
- 3.2.7 删除元素： list.remove( )
- 3.2.8 判断元素是否存在：contains
- 3.2.9 查询元素的位置：indexOf / lastIndexOf
- 3.2.10 获取顺序表中的 “子列表” ： sublist
- 3.2.11 清空整个顺序表： clear
- 3.2.12 ArrayList 的扩容机制
- 四、 ArrayList 的具体使用
- 五、 基于数组，自己实现 ArrayList
一、线性表 List
- 线性表定义：具有多个元素，且元素之间为一个挨着一个。
- 线性表特点：每个元素，都只有一个前驱，一个后继。
3. 线性表再往下细分，又分为两种实现方式：
- 顺序表 ==> 数组（经过封装后的数组，就称为顺序表）
- 链表
顺序表和链表 最本质的区别：
（1） 顺序表上的元素 在连续的内存空间上（物理上和逻辑上都是线性的）
（2） 链表上的元素，则不要求连续。通过一些其他的方式，来把前驱和后继联系起来。
（逻辑上是线性的，有前有后；物理上，放在离散的空间也可以）
- 在集合框架中，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对象，方式1
ArrayList<String> arrayList= new ArrayList<>();//空盒子，盒子里没有东西，盒子本体还在
//ArrayList就是带有泛型参数的类
//创建ArrayList对象，就根据泛型的语法创建
ArrayList<String> arrayList2 = null;//（3）连盒子都没有
//（2）创建ArrayList对象，方式2
List<String> list= new ArrayList<>();//向上转型
//ArrayList类定义的时候，实现了List 接口
//完全可以使用 List引用 指向 ArrayList 实例，这就是向上转型
//(4)使用 arrayList 复制一份，生成 arrayList3
ArrayList<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));//aaa
System.out.println(list.get(1));//bbb
System.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);
/* aaa
bbb
ccc*/
}
}
}
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;//花色 suit
private String rank;//点数 rank
public 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;
}
@Override
public 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个人手里的牌的 ArrayList
for (int i = 0; i < 3; i++) {
ArrayList<Card> hand = new ArrayList<Card>();//每个人的手牌
//此时这个二维数组，已经添加了3个元素进去了；但是每个元素，还是长度为0的ArrayList
hands.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){//杨辉三角的第一列和最后一列，都是1
row.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构造方法，无参数版
//无参数版本，默认容量为10
arr = 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 >= index
for (int i = size - 1; i >= index ; i--) {
arr[i+1] = arr[i];
}
//此时，就相当于把 index 位置已经腾出来了。把新元素放到 index 位置上就好了
arr[index] = val;
//不要忘记更新size
size++;
}
// 顺序表支持随机访问，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 转化为字符串
@Override
public 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();
}
}
【总结】
- 搬运是顺序表中核心的过程（插入 / 删除），因为数组本身不擅长中间位置的插入和删除。
- 其他的 尾插、尾删、get、set 都是比较高效的操作，时间复杂度为O(1)。
- contains、indexOf、lastIndexOf 操作，虽然时间复杂度为O(N)，但代码比较简单。
- 扩容操作：
（1）需要申请新空间，拷⻉数据，释放旧空间。会有不小的消耗。
（2）⼀般是呈2倍的增⻓，势必会有⼀定的空间浪费。例如当前容量为100，满了以后增容到200，再继续插入了5个数据，后⾯没有数据插⼊了，那么就浪费了95个数据空间。
为了解决这些问题，引入了“链表”这样的结构；虽然链表能解决这些问题，但也引入了不少问题。
因此，实际开发中，还是以 顺序表 使用的情况更多。