1. 顺序表概念

什么是顺序表？

顺序表是一种新的数据类型，它使用一段物理地址连续的存储单元依次存储数据元素(数组实现)，并具有操作(增删查改)这个数组的方法

数组也是使用连续的地址空间存储数据，那么数组和顺序表有什么区别 ?

数组是一个连续地址依次存储数据的简单结构, 而顺序表只是使用数组这个结构存储数据顺序表本身还具备操作这个数组的功能

2. 顺序表结构及实现

elem数组引用指向存储数据的内存空间

size 记录当前顺序表中数据的个数

顺序表的实现:

https://github.com/znxcmakhsd/DS/tree/main/12-12/ArrayList

3. 认识ArrayList

3.1 三种构造方法

ArrayList是Java提供的一个泛型类，它和我们自己实现的顺序表在基本逻辑上没有区别

使用ArrayList实例化顺序表对象:

public class Main {
    public static void main(String[] args) {
        ArrayList<Integer> arrayList1 = new ArrayList<>();
        List<Integer> arrayList2 = new ArrayList<>();
    }
}

由于ArrayList实现了List接口，所以也可以使用List引用引用顺序表对象

ArrayList中的三种构造方法：

有参数的构造

无参构造

如图使用无参构造构造对象时不会给数组分配大小

那么为什么可以插入数据？

这里就得看add方法的实现

第三个构造方法:

3.2 ArrayList的6种遍历

import jdk.internal.org.objectweb.asm.tree.LineNumberNode;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;

public class Main {
    public static void main(String[] args) {
        ArrayList<Integer> arrayList1 = new ArrayList<>();
        arrayList1.add(1);
        arrayList1.add(2);
        arrayList1.add(3);

        // 第一种遍历:
        System.out.println(arrayList1);

        // 第二种遍历: for
        for (int i = 0;i < arrayList1.size();i++) {
            System.out.print(arrayList1.get(i) + " ");
        }
        System.out.println();

        // 第三种遍历: for-each
        for (Integer x:arrayList1) {
            System.out.print(x+" ");
        }
        System.out.println();

        // 第4种遍历: 迭代器 Iterator
        Iterator<Integer> it = arrayList1.iterator();
        while (it.hasNext()) {
            System.out.print(it.next()+" ");
        }
        System.out.println();

        // 第5种遍历: 迭代器 ListIterator
        ListIterator<Integer> it2 = arrayList1.listIterator();
        while (it2.hasNext()) {
            System.out.print(it2.next()+" ");
        }
        System.out.println();

        // 第6种遍历: 迭代器 ListIterator 从后->前
        ListIterator<Integer> it3 = arrayList1.listIterator(arrayList1.size());
        while (it3.hasPrevious()) {
            System.out.print(it3.previous()+" ");
        }
        System.out.println();
    }
}

3.3 ArrayList的应用

1. 一道cvte面试题:

str1: "welcome to cvte"

str2: "come"

删除str1中所有出现在str2中的字符 要求使用ArrayList——》结果: w, l, , t, , v, t

方法1:

思路: 将str1中的每个字符遍历判断该字符有没有在str2中，如果没有放入arrayList

public static List<Character> func1(String str1,String str2) {
        ArrayList<Character> arrayList = new ArrayList<>();
        for (int i = 0;i < str1.length();i++) {
            char ch = str1.charAt(i);
            if (!str2.contains(ch+"")) {
                arrayList.add(ch);
            }
        }
        return arrayList;
    }

这里需要注意: contains方法判断一个字符串是否有另一个字符串，字符ch需要加""转为字符串

方法2:

思路和方法1一样只是没有使用contains方法

public static List<Character> func2(String str1,String str2) {
        ArrayList<Character> arrayList = new ArrayList<>();
        for (int i = 0;i < str1.length();i++) {
            char ch = str1.charAt(i);
            int j = 0;
            for (;j < str2.length();j++) {
                if (str2.charAt(j) == ch) {
                    break;
                }
            }
            if (j == str2.length()) {
                arrayList.add(ch);
            }
        }
        return arrayList;
    }

2. 杨辉三角

题目链接:

https://leetcode.cn/problems/pascals-triangle/description/

先说明下返回值的含义

在这道题中 List引用的是ArrayList对象, 所以List<List<Interger>>表示顺序表中每个元素类型是存储整形的顺序表对象类似于二维数组, 如下图

解题思路:

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> retArray = new ArrayList<>();
        
        // 提前插入第一行
        List<Integer> firstRow = new ArrayList<>(); 
        firstRow.add(1);
        retArray.add(firstRow);

        for (int i = 1;i < numRows;i++) {            
            List<Integer> array = new ArrayList<>(); 
            // 处理头
            array.add(1);
            // 处理中间
            for (int j = 1;j < i;j++) {
                List<Integer> lastRow = retArray.get(i-1);// 得到上一行
                array.add(lastRow.get(j-1)+lastRow.get(j));                
            }
            // 处理尾
            array.add(1);
            retArray.add(i,array);
        }
        return retArray;
    }
}