Unit 7 – ArrayList 动态数组
上个单元已经介绍过最简单的数组的使用方法。你可能已经发现，上个单元里学习的数组因为需要在定义的同时就确定存储位置的数量，且定义好后不可修改，在很多情况下并不方便。
因此，这一个单元就会介绍另一种特别的数组 —— ArrayList，这种数组的长度是动态的，所以你即使在程序运行中也可以增加、删减存储位置的数量以及修改各个位置里存储的数据。
U7.1 Introduction to ArrayList
创建 ArrayList 的语法和创建一般的 object 基本一致，是这样的：
ArrayList a = new ArrayList();用上面的这个语句就创建好了一个名字叫做 a 的 ArrayList。当然这个 a 现在还是空的，所以你可以使用「add( ) 」来给 a 添加数据。不需要在意是否有足够的存储空间，因为添加数据的同时 ArrayList 就会根据需要自动开设新的存储位置：
ArrayList a = new ArrayList();
a.add("test1");
a.add(123456);
a.add(6.666);你需要注意到，与前一个单元学习的数组不同的是，刚才在定义 ArrayList 的时候我们并没有明确数据的类型。因此在上面这段程序我每一次添加的数据并不需要符合数据类型的要求，比如这里的第一个数据可以是 String，第二个是 int，而第三个又是 double 类型的数据。
不过，不限制存入数据的类型虽然方便，有时候却导致无法及时发现程序的错误。比如我想使用一个全是 double 类型的数组进行计算，如果不限制存入数据的类型就很可能不小心混入整数类型的数据，从而在运算时产生诸如「1/3 = 0」这样的错误。
所以，ArrayList 也提供了解决这个问题的方法，即「限制存入 ArrayList 的数据类型」。你可以在创建 ArrayList 的同时只允许特定类型的数据存入，这样写（第 6 行）：
这样，当存入的数据不符合我们设定的限制时，程序就会像上面这样报错。一般的，建议在使用 ArrayList 的时候尽量指明存储数据的类型，除非你真的一定肯定必须要拿它存储不同类型混杂的数据。
U7.2 ArrayList Methods
ArrayList 还提供了一些预设好的 method 来快捷地完成数据操作。包括新增数据到数组的末尾、在某个位置上插入数据、删除某个位置上的数据、修改某个位置上的数据、访问某个位置上的数据、以及查询存储的数据的数量。
【新增数据】
上一段 U7.1 已经演示过，使用「add( ) 」来给 a 添加数据。 ArrayList 会自动为新的数据提供一个存储位置，这个存储位置就附在原来的数据后面。你可以借助下图理解，在图中 233 就是新加入的数据，它被自动赋予了一个存储位置，上一个存储位置是 3 号，所以 233 就被存在 4 号存储位置上了：
【插入数据】
假设有一个名为 a 的 ArrayList 现在存储了以下数据：
如果你不是像上面要把新增的数据接在程序的末尾，而是要在一组已有的数据之间插入新数据，就需要在使用「add( ) 」方法的时候在括号里先写上要插入数据的存储位置的编号，然后写上要插入的数据即可。两个数据之间用逗号隔开：
a.add(2, 123);这句话的意思就是把新数据 123 插入到第 2 号存储位置上。
插入了 123 之后，原本在 2 号存储位置和它之后的位置上的数据被向右依次移动一个位置。所以在完成插入后， 114、514、191 这三个数据都被向右移动了一个存储位置，他们的存储位置编号也因此增加 1 ，而腾出来的 2 号存储位置就用于放置 123。
理所当然的，2 号位置之前的存储位置不受这次数据插入的影响：
【删除数据】
你也可以把一个 ArrayList 的某个指定的存储位置移除。比如，如果我们想把刚才插入了 123 的数组 a 里面的第 3 号存储位置上的 114 移除，就这样写：
a.remove(3);「remove( ) 」是从 ArrayList 移除一个指定的存储位置的命令。它的括号里需要填写被移除的存储位置的编号。
上面的示例中，我在 remove( ) 括号里填上了 3，代表要移除第 3 号存储位置，也就是数据 114 所在的位置。
执行移除命令后，再输出数组 a 里所有的数据观察前后区别：
可以看到，此时已经没有原来存储在 3 号位置上的 114 这个数据了。而原本在 4 号和 5 号存储位置上的数据自动的向前移动一个存储位置进行补位，现在的数组 a 就成了这样：
【访问和修改数据】
无论是要修改还是要访问一个特定的数据，本质上都是通过存储位置的编号去查找到具体的数据然后对它进行操作。比如访问数据就要使用「get( ) 」，在括号里填入被访问数据的存储位置的编号，以上面这个数组为例，执行这个语句：
System.out.println(a.get(3));「a.get(3) 」访问到第 3 号存储位置上的数据，也就是41，然后通过输出语句完成输出。所以最后的输出值就是41。
同样的，你只需要换用「set( )」就可以修改指定的数据。「set( ) 」的括号里要填上两个参数，用逗号隔开，第一个参数是被修改数据的存储位置的编号，第二个参数是新填入的数据。比如我要把第三位的 41 换成 66:
a.set(3, 66);执行这句话就完成了修改：
在你的Eclipse 里定义一个 ArrayList，自己尝试一下。
【查询数据的个数】
你还可以使用「size( ) 」来查询整个 ArrayList 含有的数据的个数，仍然以上面的ArrayList a 为例：
System.out.println(a.size());因为 a 目前总共存有 5 个数据，因此执行「a.size( ) 」将会获取到 5，然后由输出语句完成输出。表示 ArrayList a 存储了五个数据。
注意，存储位置的编号（index）和存储数据的个数并不是对应的，因为存储位置的编号从 0 开始计数，往后数 5 个，最大的 index 也只有 4；但是存储数据的个数是正常的人类数数方式，所以从 1 开始数，数 5 个数据，数出来的结果是 5 。
U7.3 Traversing ArrayLists
对于 ArrayList ，你也可以使用 for 循环或者 while 循环来批量访问各个存储位置，这个操作和 U6 对于 Array 的操作是基本一致的，叫做「Traversing ArrayLists」（对U6 来说叫做Traversing Array，但区别不大因为重点是「Traversing 遍历」）。
比如：
ArrayList<Integer> a = new ArrayList();
a.add(12);
a.add(20);
a.add(13);
a.add(41);
a.add(233);
for (int i =0; i < a.size(); i++) {
System.out.println(a.get(i));
}我创建了一个包含五个数据的 ArrayList。然后使用了 for 循环来完成 Traversing 。观察上面这段程序可以看到，for 循环使用整数变量 i 进行循环计数；循环进行需要符合的条件是「 i < a.size( ) 」，这允许 i 从 0 开始计数（每次递增1）， 0、1、2、3、4，一共执行循环内的语句 5 次。当 i 的计数为 5 时，已经和「a.size( )」的数值相等，不符合「 i < a.size( ) 」的条件，因此不再继续执行循环内部的语句。
一定要注意控制好循环的圈数，因为 index 和数据个数总是差 1 ，所以很容易不小心多循环一圈或者少循环一圈。少循环一圈会导致忽略某个数据从而发生计算错误，而多循环一圈则会导致访问到一个不存在的存储位置进而发生「IndexOutOfBoundsException」错误。
不过使用 enhanced for 循环就不会存在以上问题，因为你不需要自己控制循环的圈数。具体的使用语法在第六单元也介绍过，是这样的：
ArrayList<Integer> a = new ArrayList();
a.add(12);
a.add(20);
a.add(13);
a.add(41);
a.add(233);//以上是输入 ArrayList 的值
for (int element:a) {
System.out.println(element);
}区别于普通的 for 循环，enhanced for 循环的 for 关键词后边的括号里只用填入两个数据。第一个数据是新声明的一个变量，在上面这段示例中我给它的变量名是 element，element 每一圈循环临时按顺序读入并存储一个 ArrayList 的数据；而第二个数据就是要访问的 ArrayList 的名称。
运行这段程序，变量 element 会自动在循环的每圈按数组的存储位置编号的顺序自动抓入一个数据。第一圈循环里 element 存储的就是 12；第二圈 element 存储的就是 20；以此类推；第五圈 element 存储的就是 233 了。
在示例程序里，我每圈都输出了当时 element 存储的数据，也就等同于所有存储在 ArrayList a 里面的数据都会被挨个输出，因此输出结果就是：
12
20
13
41
233但是，不要在 enhanced for 循环执行的过程中增加或者删除任何数据，否则程序会报ConcurrentModificationException错误。以及，就算是使用普通的循环语句遍历数组，如果要在循环过程中删除或增加数据，也要小心避免因为循环设置的问题而忽略或者重复访问某些数据进而导致的程序运算结果出错。
U7.4 Developing Algorithms Using ArrayLists
和 U6 学习数组的时候相同，你也可以通过编写程序算法来获知一个 ArrayList 里面的最大数、最小数、总和、平均数、是否有重复的数据等等。因为算法并无差别，所以这里就不再挨个提供示例。只需要记得在访问数据的时候对于 ArrayList 来说应该使用「ArrayList名称.get(存储位置编号)」而不是「数组名[存储位置编号 ]」。
比如，仍然以上面使用过的 ArrayList a ，对于 ArrayList 来说求平均数的写法就变成了：
ArrayList<Integer> a = new ArrayList();
a.add(12);
a.add(20);
a.add(13);
a.add(41);
a.add(233);
//以上是 ArrayList 输入数据的过程
int sum = 0; //声明一个变量，用来存储累加求和的数据
for (int i = 0; i < a.size() ; i++) {
sum += a.get(i);//累加求和，注意Array和ArrayList访问数据的命令有区别
}
double avr = (double) sum / a.size(); //计算平均数，注意 ArrayList 使用「.size()」获得数据的总个数而Array使用的是「.length」
System.out.println("和是："+ sum);
System.out.println("平均数是"+ avr);记得对比一下 U6.4 的示例代码和这里的示例代码，就可以理解 Array 和 ArrayList 在操作语法上的区别。在你的 Eclipse 里面尝试编写程序求 ArrayList 的最值、调换两个数据的位置、判断一组 ArrayList 里面是否存在重复的数据。
U7.5 Searching
搜索，字面意思，即找到符合特定特征的数据。最经典的搜索就是在一组整数中找到特定的某个数，比如在上面的 ArrayList a 里面找到 233，要求：如果可以找到 233 就返回它所在存储位置的编号（index）,否则就返回 -1 ：
class Main {
public static void main (String[] args) {
ArrayList<Integer> a = new ArrayList();
a.add(12);
a.add(20);
a.add(13);
a.add(41);
a.add(233);
//以上是 ArrayList 输入数据的过程
System.out.print(searchInt(a, 233));//在 a 中查询233
}
public static int searchInt (ArrayList readin, int target) {
for(int i = 0; i < readin.size() ; i++) {
if(readin.get(i).equals(target)) {//每次循环判断一下当前访问的 ArrayList值是否符合要查询的目标
return i; //如果相同，代表当前的数据就是要查询的目标，则返回当前 i 值
}
}
return -1;//如果对比了 ArrayList 里面所有的数据都没有找到任何一个和目标相同，则代表 ArrayList 不含查询目标，返回 -1
}
}观察这段程序，它包含了两个 method。除了 main method 之外还有一个 method 的名称叫做 searchInt，非常明显这个 method 就是用来在一组存储整数的 ArraryList 里面找到被查询的目标。
searchInt 的 parameter list 包含两个数据，第一个是搜索目标所在的 ArrayList，第二个是要搜索的目标（这里就是 233）。
searchInt 的返回值数据类型被定义为 int，因此必须在 method 运行完毕时返回一个整数，是用来返回在 ArrayList a 里面查询到被搜索目标的存储位置编号的；或者如果没查到任何对应搜索目标的数据就直接返回 -1 。
在 searchInt 里，我使用了一个 for 循环，计数器变量 i 从 0 开始计数，设置循环条件「 i < readin.size( ) 」让循环次数刚好和 ArrayList a 包含的数据个数相同。
循环开始后，我们就可以在每圈循环内部挨个判断当前 i 值对应的存储位置上是否有要查询的目标，使用 「.equals( ) 」就可以知道当前位置上存放的数据是否和目标一致。
一旦查询得到当前 i 值对应的存储位置上的数据和目标数据是「相同」的结果，就代表当前位置上的数据就是我们在查找的目标，返回当前 i 值即可，因为当前的 i 值代表的就是符合查询目标的这个数据所在的存储位置的编号。
但如果直到循环结束都没有查询到和查询目标相符的数据，就代表这个 ArrayList 并不包含我们想找的数据，那么就应该返回 -1 。
因此，如果示例中 ArrayList a 输入的数据被用来查询 「233」的所在位置，则得到返回结果「4」。因为第五个数据位置存储着查询目标 233，而第五个存储位置的编号是 4 。
尝试在你的 Eclipse 里面写一段针对存储字符串数据的 ArrayList 进行查询的程序。
U7.6 Sorting
不论对于 ArrayList 还是 Array 来说，存储大量的数据时常会面临数据混乱的情况。因此我们需要了解如何把一组数据按顺序重新排列。
Sorting，即排序，就是通过程序算法的手段来达到排序的目的。这里我们用对于 ArrayList 的操作做示例，但是你也需要能够在自己的 Eclipse 里面写出针对 Array 的排序程序。
在 AP 考试中，需要会书写的排序语法有两种：「Selection Sort」和「Insertion Sort」：
「Selection Sort」
Selection Sort 直译为选择排序。非常直观的，在升序排布时，这种排序方式是利用循环语句反复把较小的数据「选择」并替换到数组的前部，这样较大的数据就都自然的靠近数组的尾部了。
比如，在下图中最原始的数据顺序是「21、30、37、18、7」。首先读入第一个数据 21，然后开始在 21 之后找出所有小于 21 的最小的数据，在这里就是 7 。随后交换 21 和 7 的存储位置，把 7 临时存入「min」变量、把 21 存入「temp」变量做中转。然后把位于「min」的 7 赋值给原来 21 所在的存储位置，也就是 0 号存储位置；再把存在「temp」的 21 赋值给原来 7 所在的存储位置，也就是 4 号存储位置。
随后把 21 后面的数据依次按上述方式处理，待所有的数据都被这样处理一遍过后，就完成了 Selection Sort 。
注意，对于数据 21 来说，其后的所有数据都要和 21 逐一对比才能得到小于 21 的最小的数据。但是在此之后，对于 30 来说，就不需要再和 30 所在的存储位置之前的数据进行对比了。这是因为我们刚刚交换到前方存储位置的数据已经是数组后段能找到的最小的数据，不可能大于 30 本身。
比如，这里小于 21 最小能找到的数据是 7，则 7 被交换到数组前方。这样数组中越小的数据就会越优先地被排列到数组前端。
此时，7 作为首次循环中被发现的最小的数据已经被排到数组最前端，其后在寻找小于第二个数据的最小的数据时就不用再担心后续有比 7 更小的数据，因为可能出现的更小的数据已经被「选择」到数组前端了。
或许这个动态图片可以方便你理解选择排序的过程中发生的事情：
一般的，使用两层循环来完成 Selection Sort，这样写：
public static void main (String[] args) {
ArrayList<Integer> a = new ArrayList();
a.add(21);
a.add(30);
a.add(37);
a.add(18);
a.add(7);//以上是 ArrayList 的输入
int temp;//开两个变量用来在交换数据的时候做中转
int min;
for(int i = 0; i < a.size() ; i++) {//外圈循环
min = i;
for (int j = i + 1; j < a.size(); j++ ) {//内圈循环
if (a.get(min) > a.get(j)) {
min = j;
}
}
temp = a.get(i);
a.set(i, a.get(min));
a.set(min, temp);
}
for(int out:a) { //输出，检查
System.out.println(out);
}
}例如，上面动态图展示的例子中，数组最初的顺序是「21｜30｜37｜18｜7」。在循环的第一圈中假设 21 是最小的数值，然后内层循环从第二个数据（30）开始往后寻找比 21 小的最小数。很快就发现 18 比 21 小，但 7 又比 18 小，所以 7 是比 21 小的最小数。然后调换 7 和 21 所在的存储位置，结束第一圈循环。
数组此时的构成变成了「7｜30｜37｜18｜21」。接着，第二圈循环，计数器变量 i 递增，最初被假设存储着最小值的存储位置也从第一个存储位置来到了第二个存储位置，现在第二个存储位置上的数值为 30。所以这次内层循环则是从 30 的后一个数据，也就是 37，开始搜寻比 30 小的最小数。经过对比发现，18是比 30 小的最小数，那么就调换 18 和 30 所在的存储位置，结束第二圈循环。
数组这时变化成为「7｜18｜37｜30｜21」。外层循环来到第三圈，假设第三个存储位置上的 37 是最小数，然后内层循环从 37 后方的存储位置开始查找 比 37 小的最小数。查得 21，然后调换 21 和 37 的位置。得到 「7｜18｜21｜30｜37」，进入外层循环第四圈。
第四圈中，外层循环计数器的数值指代数组第四个存储空间上的数值，这时我们假设的最小数为 30，然后从 30 后的一个存储空间（也就是存储 37 的位置）开始查找 比 30 小的最小数，发现并不存在这个数，所以等到内层循环结束直接进入下一圈外层循环而毋须做出任何数据调换。
最后，当外层循环来到最后一圈，发现后方已经没有数据需要对比，则排序完成，经过排序的数组是「7｜18｜21｜30｜37」。
而要倒序排布只需要更改内层循环中判断语句条件的大于符号为小于符号。试图使用以上逻辑过程解释、理解为什么这一修改可以达到倒序排布的目的。
「Insertion Sort」
这是另一种AP考试要求的排序算法，称为「Insertion Sort 插入排序」。这种方法也要用到内外层循环来实现排序，但它的内层循环是倒序（即计数器变量递减）而外层循环为正序（计数器变量递增）。
外层循环用于遍历数组的第二个到最后一个数据，也就是从 1 号存储位置开始循环到最后一个存储位置结束。在每圈的最开始，使用 temp 变量来存储循环计数器变量当前对应的存储位置上的数据，方便在排序过程中调换数据之间的存储位置。
每次内层循环总是开始于外层循环的前一个存储位置，然后判断内层循环计数器变量数值对应的存储位置上的数据是否比 temp 存储的数据大。如果是，则交换两者的位置。这样一来，越大的数据就越靠右侧，实现了排序的目的。
class Main {
public static void main (String[] args) {
ArrayList<Integer> a = new ArrayList();
a.add(5);
a.add(2);
a.add(1);
a.add(3);
a.add(4);
insertionSort(a);
}
public static void insertionSort (ArrayList<Integer> pass) {
for(int i = 1; i < pass.size() ; i++) {
int temp = pass.get(i);
int j = i - 1;
while (j >= 0 && pass.get(j) > temp) {
pass.set(j + 1, pass.get(j));
pass.set(j, temp);
j--;
}
}
for(int read : pass) {
System.out.println(read);
}
}
}例如，现在有一个 ArrayList a，其中存有 5 个数据。初始的数据顺序依次是「5、2、1、3、4」。第一圈循环中，外层循环将第二个存储位置上的数据「2」存入 temp。然后内层循环把「2」和前一个存储位置上的数据进行对比，发现前一个位置上存储的「5」比「2」大，所以调换这两个存储位置上的数据。随后内层循环计数器递减，0减1等于负1，此时不再满足循环条件，内层循环结束。第一圈外层循环也随之结束。ArrayList a 此时已被更新为「2、5、1、3、4」。
然后，外层循环进入第二圈，temp 变量存入第三个存储位置上的数据「1」。然后内层循环开始向左对比，发现「5」比「1」大，遂调换两者的存储位置。ArrayList更新为「2、1、5、3、4」。第一圈内层循环结束，内层循环计数器变量 j 递减。但此时 j 仍大于等于 0 且发现ArrayList的左侧仍有比 1 大的数据，所以要把 1 和第一个存储位置上的「2」再进行调换。得到「1、2、5、3、4」，第二圈内层循环结束，j 再次递减，此时 j 小于 0 导致循环条件不再被满足，循环结束。随后第二圈外层循环也结束。
之后是第三圈和第四圈外层循环，可以按照以上的逻辑计算。在所有循环结束后就完成了排序。尝试在自己的 eclipse 里面分别使用已经介绍的两种排序算法将「1828、2791、2819、1662、2818、1828、2004、2771」排序。
U7.7 Ethical Issues Around Data Collection
不要使用程序写作来完成不合理的行为，包括但不限于未经许可的处理他人隐私数据等等。
练习
- 2009-4
- 2015-40
7.4
U7.4示例程序第14行注释的描述有一个问题（计算平均数，注意 ArrayList 使用「.size()」获得数据的总个数而Array使用的是「.length()」）
这里原来的表述 Array使用的是「.length()」 是错误的。这里的「.length()」不应该有括号，所以正确的写法是「.length」。
用于 ArrayList 的「.size()」有括号是没有问题的，只是用于 Array 的「.length」不应该有括号
已经修改了