数据结构(Java版)第四期：ArrayLIst和顺序表(上)
目录
一、顺序表
上一期我们讲到过，顺序表本质上和数组是差不多的，只不过数组只能访问或修改某个元素，而作为顺序表，需要实现更多的功能。
1.1. 接口的实现
//新增元素,默认在数组最后新增 public void add(int data) { } // 在pos位置新增元素 public void add(int pos, int data) { } //判定是否包含某个元素 public boolean contains(int toFind) { return true; } //查找某个元素对应的位置 public int indexOf(int toFind) { return -1; } //获取pos位置的元素 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简介
2.1. ArrayList的构造
import java.util.ArrayList; import java.util.List; public class Main { public static void main(String[] args) { //第一种方式，创建ArrayList对象，构造空的顺序表 ArrayList<String> arrayList1 = new ArrayList<>(); //第二种方式 List<String> list = new ArrayList<>(); } }其中ArrayList里面，也是实现了List的接口。也就是说，我们完全可以通过向上转型，把List引用指向ArrayList的实例。
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable我们来看下面两段代码的，两个都是构造空的顺序表，二者有什么区别呢？第一个是创建了一个盒子，盒子里面为空，而第二个却连盒子都没有。
ArrayList<String> arrayList1 = new ArrayList<>(); ArrayList<String> arrayList2 = null;//使用arrayList1复制一份，生成arrayList3 ArrayList<String> arrayList3 = new ArrayList<>(arrayList1);//构造的同时，可以去指定初始容量 ArrayList<String> arrayList4 = new ArrayList<>(10);当前构造出来的ArrayList初始容量为10，这里与数组的区别是：数组我们在一开始就规定好了它的容量，不能在进行修改了；而ArrayList的容量可以进行动态扩容，只要机器内存允许，就能一直扩容，把想要的元素容纳进去。
2.2. ArrayList的常见操作
（1）add尾插操作
import java.util.ArrayList; import java.util.List; public class Main { public static void main(String[] args) { List<String> list = new ArrayList<>(); list.add("aaa"); list.add("bbb"); list.add("ccc"); System.out.println(list); } }（2）获取元素个数
import java.util.ArrayList; import java.util.List; public class Main { public static void main(String[] args) { //获取元素个数，数组提供了.length属性获取到元素个数，集合类提供了size()方法获取元素个数 List<String> list = new ArrayList<>(); list.add("aaa"); list.add("bbb"); list.add("ccc"); System.out.println(list.size()); } }
事实上，不仅是List，只要是集合类，都可以通过.size来获取长度。
（3）ArrayList的访问和修改
import java.util.ArrayList; import java.util.List; public class Main { public static void main(String[] args) { //获取或者设置list中的元素 List<String> list = new ArrayList<>(); list.add("aaa"); list.add("bbb"); list.add("ccc"); list.add("ddd");//进行了自动扩容 System.out.println(list.get(0)); System.out.println(list.get(1)); System.out.println(list.get(2)); System.out.println(list.get(3)); System.out.println(list.get(4)); } }
如果我们运行一下，此时也会出现下标越界访问的异常。
import java.util.ArrayList; import java.util.List; public class Main { public static void main(String[] args) { //获取或者设置list中的元素 List<String> list = new ArrayList<>(); list.add("aaa"); list.add("bbb"); list.add("ccc"); list.add("ddd");//进行了自动扩容 list.set(0,"eee"); System.out.println(list); } }（4）ArrayList的遍历
import java.util.ArrayList; import java.util.List; public class Main { public static void main(String[] args) { List<String> list = new ArrayList<>(); list.add("aaa"); list.add("bbb"); list.add("ccc"); list.add("ddd"); //遍历是可能会进行各种操作的，不一定是打印 for (int i = 0; i < list.size(); i++) { System.out.print(list.get(i)+" "); } System.out.println(); //for-each写法 for (String s : list) { System.out.print(s+" "); } } }
并不是所有的类都能写进for-each里面，要求这个类必须能够实现Iterable接口。实现Iterable接口中的iterator方法，得到一个迭代器对象，进行近一步循环遍历。
public interface List<E> extends Collection<E>public interface Collection<E> extends Iterable<E> Iterator<E> iterator();迭代也是计算机中的专业术语，可以理解成“逐渐接近目标”。集合类中用到迭代。上面的for-each循环，我们可以看作是以下代码的简化。
Iterator<String> iterator = list.iterator(); while(iterator.hasNext()){ System.out.println(iterator.next()); }hasNext用于判断有没有下一个元素，iterator.next用于取出当前元素，并准备下一个元素。hasNext的工作机理可以如下图所示，按照箭头从上到下依次去遍历。
（5）其他的一些操作
import java.util.ArrayList; import java.util.List; public class Main { public static void main(String[] args) { //通过contains判读元素是否存在 List<String> list1 = new ArrayList<>(); list1.add("aaa"); list1.add("bbb"); list1.add("ccc"); list1.add("ccc"); list1.add("ccc"); list1.add("ddd"); System.out.println(list1.contains("aaa")); //通过indexOf获取元素第一次出现的位置 System.out.println(list1.indexOf("ccc")); //通过lastIndexOf获取元素最后一次出现的位置 list1.lastIndexOf("ccc"); main1(args); main2(args); main3(args); } public static void main3(String[] args) { List<String> list1 = new ArrayList<>(); list1.add("aaa"); list1.add("bbb"); list1.add("ccc"); list1.add("ddd"); //按照元素内删除 list1.remove("ddd"); System.out.println(list1); } public static void main2(String[] args) { List<String> list1 = new ArrayList<>(); list1.add("aaa"); list1.add("bbb"); list1.add("ccc"); list1.add("ddd"); //按照下标删除元素 list1.remove(2); System.out.println(list1); } public static void main1(String[] args) { List<String> list1 = new ArrayList<>(); list1.add("aaa"); list1.add("bbb"); list1.add("ccc"); list1.add("ddd"); //在任意位置添加元素 list1.add(1,"eee"); System.out.println(list1); } } 
2.3. ArrayList的扩容机制
当ArrayList内存不够时，就会自动申请额外的内存空间。ArrayList内部持有一个数组，设置的初始容量相当于数组的大小。比如说我们初始容量为10，当循环到第11次的时候，发现元素已经满了；add真正写进元素之前，就要创建一个更大的数组。新的数组要把旧的数组里的元素添加进来，新的元素也要添加进新的数组里面，原来旧的数组要进行释放。
三、ArrayList的具体使用
3.1. 洗牌算法
问题描述：现有一副扑克牌，对其进行洗牌。
我们先来定义一个Card类，用来表示一张扑克牌。
class Card { public String suit;//表示花色 public String rank;//表示点数 public Card(String suit, String rank) { this.suit = suit; this.rank = rank; } 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; } }接下来要先把Card这个对象实例化，并用ArrayList把所有的牌添加进去。
public class Main { public static void main(String[] args) { //使用ArrayList表示一副扑克牌 } public static ArrayList<Card> CreateDeck() { //创建一副扑克牌 ArrayList<Card> deck = new ArrayList<>(); String[] suits = {"♠","♦","♥","♣"}; //通过两层for循环，第一层先循环花色，第二层在循环点数 //每个花色中，生成对应的点数 for (String suit:suits){ for (int i = 2; i <= 10; i++) { Card cardNum = new Card(suit,""+i); deck.add(cardNum);//添加到扑克牌中 } 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; } }然后我们调用CreateDeck方法，对这副牌进行一个打印。
public class Main { public static void main(String[] args) { //使用ArrayList表示一副扑克牌 ArrayList<Card> deck = CreateDeck(); System.out.println(deck); } }
接下来是进行洗牌的操作，在Java标准库中，提供了进行洗牌的方法shuffle。
import java.util.Collections; public class Main { public static void main(String[] args) { //使用ArrayList表示一副扑克牌 ArrayList<Card> deck = CreateDeck(); System.out.println("原始牌组:"+deck); //洗牌 Collections.shuffle(deck); System.out.println("洗牌之后:"+deck); } }
我们也可以自己写一个方法，来进行洗牌。
public static void shuffle(ArrayList<Card> deck){ //把整个ArrayList从后往前遍历 //每次取一张牌，生成一个随机下标，用当前的拍和随机下标的牌进行交换 Random random = new Random(); for (int i = deck.size() - 1; i >0 ; i--) { int j = random.nextInt(deck.size());//生成随机下标[0,deck.size) //交换操作 Card tmp = new Card(deck.get(i).getSuit(), deck.get(i).getRank());//必须要确保tmp拿到i的下标，不能交换的时候发生修改 deck.set(i, deck.get(j)); deck.set(j, tmp); } }下面是发牌，一共有3个人，每个人发5张牌。我们可以看成一个3行5列的一个二维数组。
ArrayList<ArrayList<Card>> hands = new ArrayList<ArrayList<Card>>();//构成一个二维数组 //先创建 3 个人手里的牌 for (int i = 0; i < 3; i++) { ArrayList<Card> hand = new ArrayList<>();//每一个人的手牌 hands.add(hand);//发到每个人手里 //已经添加了3个元素进去，但还是长度为0的ArrayList }最后是发牌的过程。
for (int i = 0; i < 5; i++) { for (int j = 0; j < 3; j++) { //发牌是轮流的过程. ArrayList<Card> currentHand = hands.get(j); Card card = deck.remove(0); currentHand.add(card); //一次循环，相当于取出一张牌交给玩家 } }完整代码：
import java.util.ArrayList; import java.util.Collections; import java.util.Random; class Card { public String suit;//表示花色 public String rank;//表示点数 public Card(String suit, String rank) { this.suit = suit; this.rank = rank; } 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 Main { public static void main(String[] args) { //使用ArrayList表示一副扑克牌 ArrayList<Card> deck = CreateDeck(); System.out.println("原始牌组:"+deck); //洗牌 //Collections.shuffle(deck); System.out.println("洗牌之后:"+deck); ArrayList<ArrayList<Card>> hands = new ArrayList<ArrayList<Card>>();//构成一个二维数组 //先创建 3 个人手里的牌 for (int i = 0; i < 3; i++) { ArrayList<Card> hand = new ArrayList<>();//每一个人的手牌 hands.add(hand);//发到每个人手里 //已经添加了3个元素进去，但还是长度为0的ArrayList } for (int i = 0; i < 5; i++) { for (int j = 0; j < 3; j++) { //发牌是轮流的过程. 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)); } } public static void shuffle(ArrayList<Card> deck){ //把整个ArrayList从后往前遍历 //每次取一张牌，生成一个随机下标，用当前的拍和随机下标的牌进行交换 Random random = new Random(); for (int i = deck.size(); i >0 ; i--) { int j = random.nextInt(deck.size());//生成随机下标[0,deck.size) //交换操作 Card tmp = new Card(deck.get(i).getSuit(), deck.get(i).getRank());//必须要确保tmp拿到i的下标，不能交换的时候发生修改 deck.set(i, deck.get(j)); deck.set(j, tmp); } } public static ArrayList<Card> CreateDeck() { //创建一副扑克牌 ArrayList<Card> deck = new ArrayList<>(); String[] suits = {"♠","♦","♥","♣"}; //通过两层for循环，第一层先循环花色，第二层在循环点数 //每个花色中，生成对应的点数 for (String suit:suits){ for (int i = 2; i <= 10; i++) { Card cardNum = new Card(suit,""+i); deck.add(cardNum);//添加到扑克牌中 } 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; } } 
3.2. 杨辉三角
问题描述：给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。在「杨辉三角」中，每个数是它左上方和右上方的数的和。
示例 1: 输入: numRows = 5 输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
示例 2: 输入: numRows = 1 输出: [[1]]
通过上面的图，我们可以总结出以下规律：1.第i行有i+1个列(因为要用二维数组解决，所以把第一行定义第0行)；2.每一行的第一列和最后一列都是1；3.第i行第j列的元素 = 第i-1行第j-1列的元素 + 第i-1行第j列的元素。
完整代码：
import java.util.ArrayList; import java.util.List; import java.util.Scanner; public class Main { public List<List<Integer>> generate(int numRows) { //先写一个表示结果的二维数组 List<List<Integer>> result = new ArrayList<List<Integer>>(); //先来构造行 for (int i = 0; i < numRows; i++) { List<Integer> rows = new ArrayList<>();//用到了向上转型。需要往这一行里面里面添加元素 for (int j = 0; j < i+1; j++) { if (j==0 || j==i){ rows.add(1); } else { List<Integer> prevRow = result.get(i - 1); int current = prevRow.get(j - 1) + prevRow.get(j); rows.add(current); } } //一行构造好了之后，把这一行添加到result中 result.add(rows); } return result; } public static void main(String[] args) { Main m = new Main(); Scanner num = new Scanner(System.in); int b = num.nextInt(); List<List<Integer>> result = m.generate(b); System.out.println(result); } } 
