一周一个数据结构 第一周 --- 顺序表（下）

文章目录

• 一、ArrayList的构造
• 二、ArrayList常见操作
• 三、ArrayList的遍历
• 四、ArrayList练习
• • 1.【小练习】
  • 2.杨辉三角
  • 3.简单的洗牌算法
• 五、ArrayList小结

在上一章节中，我们通过代码示例以及画图的方式详细了解了顺序表，并模拟实现了它。那么，是不是以后每次需要用到顺序表这种数据结构时，我们都需要先模拟实现顺序表之后才能使用呢？答案是否定的。
在Java中，提供了ArrayList类来帮助我们实现顺序表这种数据结构。ArrayList是一个普通的类，实现了List接口：

接下来，我们就来学习在Java中ArrayList类的具体用法。

一、ArrayList的构造

常见的ArrayList的构造有三种方式：

public static void main(String[] args) {
//构造
ArrayList<Integer> arrayList = new ArrayList<>(); //无参构造
List<Integer> list = new ArrayList<>(2); //指定顺序表容量
List<Integer> list1 = new ArrayList<>(list); //参数为 顺序表
}

分别是：无参构造、指定容量、参数为顺序表。因为ArrayList类实现了List接口，所以在进行构造时，等号左边既可以是ArrayList也可以是List。在使用第三种构造方法时，需注意：list中元素的类型必须与list1中元素的类型相同才行，否则会编译报错。

二、ArrayList常见操作

ArrayList类中提供了非常多的方法，使用频率最高的为以下这些： 这些方法绝大部分我们已经自己模拟实现过了，用法和我们模拟实现的一样，不过有一些特殊的方法需要特殊记忆：

public static void main(String[] args) {
//方法测试
List<Integer> list = new ArrayList<>(); //无参构造
list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.add(5);
System.out.println(list); //[1, 2, 3, 4, 5]

//addAll:添加一个顺序表中的所有元素
list.addAll(list);
System.out.println(list); //[1, 2, 3, 4, 5, 1, 2, 3, 4, 5]

//使用remove进行删除时，如果想要删除值，需要通过new关键字
list.remove(2);
System.out.println(list); //[1, 2, 4, 5, 1, 2, 3, 4, 5]
list.remove(new Integer(2));
System.out.println(list); //[1, 4, 5, 1, 2, 3, 4, 5]

//使用subList对顺序表进行截取
List<Integer> list1 = list.subList(1, 3); //左闭右开区间
System.out.println(list1); //[4, 5]
//当修改截取到的顺序表中的值时，原顺序表对应位置的值也会被修改
list1.set(1, 666);
System.out.println(list1); //[4, 666]
System.out.println(list); //[1, 4, 666, 1, 2, 3, 4, 5]
}

在上面这段代码中，我们还需注意一点：当调用无参的构造方法时，不会分配内存；默认是在第一次调用add方法时，分配大小为10的内存空间；当空间不够需要扩容时，默认以1.5倍大小进行扩容。

三、ArrayList的遍历

ArrayList的遍历有很多种方式：直接输出、for循环遍历以及迭代器：

public static void main(String[] args) {
//遍历
List<Integer> list = new ArrayList<>(); //无参构造
list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.add(5);

//方式一：sout
System.out.println(list); //源码中重写了toString方法
System.out.println("===========================");

//方式二：for循环
for (int i = 0; i < list.size(); i++) {
System.out.print(list.get(i) + " ");
}
System.out.println();

for (Integer x : list) {
System.out.print(x + " ");
}
System.out.println();
System.out.println("===========================");

/**
* 方式三：迭代器
* Iterator 和 ListIterator都可以遍历顺序表，ListIterator还可以逆序遍历
*/
Iterator<Integer> iterator = list.iterator();
while (iterator.hasNext()) {
System.out.print(iterator.next() + " ");
}
System.out.println();

ListIterator<Integer> listIterator = list.listIterator();
while (listIterator.hasNext()) {
System.out.print(listIterator.next() + " ");
}
System.out.println();

//使用ListIterator逆序输出
ListIterator<Integer> listIterator1 = list.listIterator(list.size());
while (listIterator1.hasPrevious()) {
System.out.print(listIterator1.previous() + " ");
}
System.out.println();
}

在这些方式中，最常使用的是for-i循环以及for-each循环。

四、ArrayList练习

1.【小练习】

题目： 已知两个字符串s1、s2，现在要求：删除第一个字符串中出现的 所有的 第二个字符串中的字符：

根据题意，我们需要删除s1中出现的所有的s2中的字符，那么，我们就可以遍历s1，获取s1中所有的字符，看这个字符是否为s2中的字符，如果不是，我们就将此字符添加到顺序表中，最后返回一个顺序表即可。

//编写一个方法实现主要操作
public static ArrayList<Character> del(String s1, String s2) {
//创建一个顺序表，接收s1中与s2中不重复的字符
ArrayList<Character> arrayList = new ArrayList<>();
//遍历s1
for (int i = 0; i < s1.length(); i++) {
//获取对应下标位置的字符
char ch = s1.charAt(i);
if (!s2.contains(ch + "")){
arrayList.add(ch);
}
}
return arrayList;
}
public static void main(String[] args) {
//小练习
String s1 = "welcome to victim";
String s2 = "come";
ArrayList<Character> ret = del(s1, s2); //接收返回值
for (Character x : ret) {
System.out.print(x);
}
}

2.杨辉三角

杨辉三角 在解决这道在线编程题时，我们需要注意理解代码模板中给出的返回值的含义：我们已经知道顺序表的底层其实是一个数组，那么对于本题中给出的返回值，我们就可以理解为其本质是一个二维数组： 我们为杨辉三角的每一行都创建一个顺序表，存储对应行中的数据元素，最后再将这些顺序表都存储到一个新的顺序表中，在这个新的顺序表中的每个元素都是一个顺序表。

我们再回归到这个数学问题本身，可以观察到，每一行的第一个元素和最后一个元素的值都为1，我们再将杨辉三角变换为直角三角形的形式进行观察，那么，每一个元素都是其上方元素和其上方元素的前一个元素的和。

class Solution {
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> list = new ArrayList<>(); //定义二维顺序表
List<Integer> row = new ArrayList<>(); //定义每一行的顺序表

//因为第一行只有一个元素，对第一行单独处理
row.add(1);
list.add(row);
//代码运行至此，杨辉三角第一行处理完毕

//以下代码，对第二行及以后行数 进行处理
for(int i = 1; i < numRows; i++) {
List<Integer> curRow = new ArrayList<>(); //每一行一个顺序表
curRow.add(1); //顺序表的第一个元素

List<Integer> preRow = list.get(i – 1); //获取上一行
for(int j = 1; j < i; j++) {
int x = preRow.get(j) + preRow.get(j – 1);
curRow.add(x);
}

curRow.add(1); //顺序表的最后一个元素

list.add(curRow); //添加到二维顺序表中
}
return list;
}
}

3.简单的洗牌算法

现在有这样一个场景：有一副新的扑克牌（排除大小王），三个人玩，先开始洗牌，然后一人抓一张，抓五轮，看每个人都抓到的是什么牌： 我们先对牌进行定义：

public class Card {
public String suit; //花色
public int rank; //数字
public Card(String suit, int rank) {
this.suit = suit;
this.rank = rank;
}
@Override
public String toString() {
// return "Card{" +
// "suit='" + suit + '\\'' +
// ", rank=" + rank +
// '}';
return suit + rank;
}
}

接下来，我们依次完成定义一副新的牌、洗牌、发牌操作：

public class CardList {
public static final String[] SUITS = {"♠", "♥", "♦", "♣"}; //定义四种花色

//定义一副新的牌
public static List<Card> newCard() {
//用顺序表存放牌
List<Card> list = new ArrayList<>();
for (int i = 0; i < SUITS.length; i++) {
for (int j = 1; j <=13 ; j++) {
Card card = new Card(SUITS[i], j);
list.add(card);
}
}
return list;
}

//洗牌
public static void washCard(List<Card> list) {
//生成随机数交换牌，达到洗牌的目的
Random random = new Random();
for (int i = list.size() – 1; i > 0; i—) {
int index = random.nextInt(i);
swap(list, i, index);
}
}
//交换牌
private static void swap(List<Card> list, int i, int j) {
Card tmp = list.get(i);
list.set(i, list.get(j));
list.set(j, tmp);
}

public static void main(String[] args) {
List<Card> list = newCard();
System.out.println(list);

washCard(list);
System.out.println(list);

//用来存放三个人各自的牌
List<Card> p1 = new ArrayList<>();
List<Card> p2 = new ArrayList<>();
List<Card> p3 = new ArrayList<>();

//存放三个人
List<List<Card>> p = new ArrayList<>();

p.add(p1);
p.add(p2);
p.add(p3);

//发牌
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 3; j++) {
Card card = list.remove(0);
p.get(j).add(card);
}
}

System.out.println("A的牌：" + p.get(0));
System.out.println("B的牌：" + p.get(1));
System.out.println("C的牌：" + p.get(2));
System.out.println("剩的牌：" + list);
}
}

一个简单的洗牌算法就完成啦。

五、ArrayList小结

ArrayList底层是数组实现的，所以在进行有关查找的操作时，速度很快；但也是因为底层是数组实现的，这也导致了在进行增加或者删除操作时，需要逐个移动元素，效率很低，速度慢；在进行扩容操作时，1.5倍的扩容大小也可能会导致很多空间的浪费。

Ending。