当前位置：首页 > news >正文

List、ArrayList 与顺序表

news 2025/8/7 5:42:58

一、List 介绍

二、线性表

三、自己实现 ArrayList

3.1 显示元素

3.2 增

3.2.1 默认在数组后面新增元素

3.2.2 在指定位置中新增元素

3.3 查

3.4 取值

3.5 改

3.5.1 把 pos 位置的元素修改成 value

3.5.2 删除某个元素

3.5.3 清空

四、认识 ArrayList

4.0 说明

4.1 成员变量

4.2 构造方法

4.2.1 指定顺序表的初始容量

4.2.2 无参构造方法

4.2.3 利用其他 Collection 构建 ArrayList

4.3 常用方法

4.4 ArrayList 的遍历

4.4.1 for 循环 + get()方法

4.4.2 foreach

4.4.3 迭代器

五、练习

5.1 删除

5.2 杨辉三角

5.3 综合练习——洗牌

六、二维表

七、ArrayList 的问题与思考

一、List 介绍

在 java.util 包下一些重要的接口和类中，我们本次讲到的是红色线框的部分。

在集合框架中，List 是一个接口，继承自 Collection 接口，而 Collection 接口又继承自 Iterable 接口。而他们之间的关系是“extends 扩展”的关系，即 List 扩展了 Collection 的功能，如 List 接口的方法比 Collection 的要多：

此外因为 List 是一个接口，因此不能直接被用来实例化；如果要使用，必须实例化 List 的实现类，即 ArrayList 和 LinkedList。

二、线性表

一般顺序表如下图（此外还有栈和队列这2个受限线性表）

站在数据结构的角度上来看，List 是一个线性表，即 n 个具有相同类型元素的有限序列，在该序列上可以执行增删改查以及变量等操作。

线性表在逻辑上是线性结构，也可以说是连续的一条直线；但是在物理结构上并不一定是连续的，现象表在物理上存储时，通常以数组和链式结构的形式存储。

三、自己实现 ArrayList

自己实现对数组进行增删查改的操作。新建一个 MyArrayList 类文件，存放整型数组和有效数据长度两个字段（有效数据长度与图书管理系统的用法一致）。

定义一个名为 IList 的总接口，该接口可实现对数组进行增删查改等的操作。MyArrayList 类实现该接口并重写增删查改等方法。

3.1 显示元素

package test;public interface IList{// 新增元素,默认在数组最后新增void add(int data);// 在 pos 位置新增元素void add(int pos, int data);// 判定是否包含某个元素boolean contains(int toFind);// 查找某个元素对应的位置int indexOf(int toFind);// 获取 pos 位置的元素int get(int pos);// 给 pos 位置的元素设为 valuevoid set(int pos, int value);//删除第一次出现的关键字keyvoid remove(int toRemove);// 获取顺序表长度int size();// 清空顺序表void clear();// 打印顺序表，注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的void display();
}

package test;import java.util.Arrays;public class MyArrayList implements IList{private int[] arr;private int usedSize;private static final int DEFAULT_CAPACITY = 10; // 定义一个常量，表示数组的容量public MyArrayList(){arr = arr[DEFAULT_CAPACITY];  // 实例化 MyArrayList 同时调用构造方法给数组进行初始化}@Overridepublic void add(int data) {}@Overridepublic void add(int pos, int data) {}@Overridepublic boolean contains(int toFind) {return false;}@Overridepublic int indexOf(int toFind) {}@Overridepublic int get(int pos) {}@Overridepublic void set(int pos, int value) {}@Overridepublic void remove(int toRemove) {}@Overridepublic int size() {return this.usedSize;}@Overridepublic void clear() {}@Overridepublic void display() {for (int i = 0; i < this.usedSize; i++) {System.out.print(arr[i] + " ");}// 不能使用 foreach 遍历数组，因为我们只需要显示usedSize范围内的元素}
}

测试类先测试能否将数组元素遍历显示：

package test;public class Test{public staic void main(String[] args){MyArrayList myArrayList = new MyArrayList();IList iList = new MyArrayList();  // 向上转型System.out.println(myArrayList.size());System.out.println(iList.size());System.out.println("----------------------");myArrayList.display();iList.display();}
}

上面代码的输出结果是：
0
0
----------------------

Process finished with exit code 0

因为此时 usedSize 为0，无法显示任何数组中的元素。

实例化可以有两种方法：
如果用接口引用当前对象，只要实现这个接口的对象都能引用，意味着可以向上转型并发生动态绑定和多态；但缺点在于通过这个接口，只能调用这个接口当中包含的方法，不能调用对象中特有的方法。
而如果用当前对象引用当前对象，可以调用对象中的所有方法。

获取当前顺序表的长度用 .size() 方法。

3.2 增

3.2.1 默认在数组后面新增元素

实现条件：
1、在新增之前，数组是否已经满了？
2、如果数组满了，如何对数组进行扩容？

思路：

1、在接口中编写一个判断数组是否已满的方法，并在 MyArrayList 中重写该方法。

public interface IList{// 在新增元素之前，需要对数组判断是否已满boolean isFull();// 其余方法（略）
}

public class MyArrayList{// 新增判满方法public boolean isFull(){return this.usedSize == this.arr.length;}}

2、使用 Arrays 的复制数组的方法将数组原来的内容复制到新定义长度的数组中。

public class MyArrayList{// 新增判满方法public boolean isFull(){return this.usedSize == this.arr.length;}private void grow(){this.arr = Arrays.copyOf(this.arr, 2*this.arr.length);}}

3、实现：如果满了，扩容 --> 将 data 赋值给 usedSize 为下标的元素 --> 有效数组长度+1

public class MyArrayList{// 新增判满方法public boolean isFull(){return this.usedSize == this.arr.length;}private void grow(){this.arr = Arrays.copyOf(this.arr, 2*this.arr.length);}@Overridepublic void add(int data) {if (isFull()){// 如果满了，需要扩容grow();}this.arr[this.usedSize] = data;this.usedSize++;}
}

public class Test{public static void main(String[] args){MyArrayList myArrayList = new MyArrayList();myArrayList.add(1);myArrayList.add(2);myArrayList.add(3);myArrayList.display();}
}

3.2.2 在指定位置中新增元素

实现条件：
1、指定的位置不能是负数，且指定的位置前一个元素必须不能为空。
（顺序表中的除第1个元素外，每个元素必须有唯一一个直接前驱）
2、数组已经满了的话，也是需要扩容的。

思路：

1、对于指定位置不合法，我们可以编写一个类，使得这个类继承于运行时的异常接口，并重载构造方法：

package test;public class PosIllegalException extends RuntimeException{public PosIllegalException(){}public PosIllegalException(String mes){super(mes)}
}

2、在 MyArrayList 中新增一个检查 pos 的方法，如果 pos 不合法，则 抛出异常

public class MyArrayList implements IList{private void checkPos(int pos) throws PosIllegalException {if (pos < 0 || pos > this.usedSize){throw new PosIllegalException("Pos位置不合法！！！")}}
}

3、实现插入新元素：

public class MyArrayList implements IList{private void checkPos(int pos) throws PosIllegalException {if (pos < 0 || pos > this.usedSize){throw new PosIllegalException("Pos位置不合法！！！")}}@Overridepublic void add(int pos, int data){try {// 检查pos是否合法checkPos(pos);// 扩容if (isFull()){grow();}// 挪动元素for (int i = usedSize - 1; i >= pos; i--){arr[i + 1] = arr[i];}arr[pos] = data;this.usedSize++;}catch (PosIllegalException e){System.out.println("插入pos元素的位置不合法！！");e.printStackTrace();}}
}

public class Test{public static void main(String[] args) {MyArrayList myArrayList = new MyArrayList();myArrayList.add(1);myArrayList.add(2);myArrayList.add(3);myArrayList.add(4);myArrayList.add(5);myArrayList.add(2,66);myArrayList.add(7,4);myArrayList.display();}
}

输出结果：
插入pos元素的位置不合法！！
1 2 66 3 4 5 test.PosIllegal: Pos位置不合法！！！
   at test.MyArrayList.checkPos(MyArrayList.java:34)
   at test.MyArrayList.add(MyArrayList.java:40)
   at test.test.main(test.java:24)

3.3 查

判断是否包含每个元素 contains 和查找某个元素对应的位置 indexOf 方法：

public class MyArrayList implements IList{@Overridepublic boolean contains(int toFind) {for (int i = 0; i < this.usedSize; i++) {if (arr[i] == toFind){return true;}}return false;}@Overridepublic int indexOf(int toFind) {for (int i = 0; i < this.usedSize; i++) {if (arr[i] == toFind){return i;}}return -1;}
}

3.4 取值

实现条件：
1、pos 超出合法范围，pos 不能小于0，不能大于 usedSize，也不能等于 usedSize，下标为 usedSize 的位置没有元素。
2、如果下标为 pos 的元素为空？

思路：

1、因为上面写的 checkPos 方法在 pos 等于 usedSize 的时候不会抛出异常，因此我们需要重写一个 checkPos2 方法：

public class MyArrayList implements IList {private void checkPos2(int pos) throws PosIllegalException{if (pos < 0 || pos >= usedSize){throw new PosIllegalException("Pos位置不合法！！！");}}
}

2、编写一个元素为空异常的类

package test;public class EmptyException extends RuntimeException{public EmptyException(){}public EmptyException(String msg){super(msg);}
}

3、判断元素是否为空

public class MyArrayList implements IList{public boolean isEmpty(){return this.usedSize == 0;}private void checkEmpty(){if (isEmpty()){throw new EmptyException("顺序表为空！！！");}}
}

4、实现取值

public class MyArrayList implements IList{public boolean isEmpty(){return this.usedSize == 0;}private void checkEmpty(){if (isEmpty()){throw new EmptyException("顺序表为空！！！");}}@Overridepublic int get(int pos) {try{checkEmpty();checkPos2(pos);return arr[pos];}catch (EmptyException e){e.printStackTrace();}catch (PosIllegalException e){e.printStackTrace();}return -1;}
}

public class Test {public static void main(String[] args) {MyArrayList myArrayList = new MyArrayList();myArrayList.add(1);myArrayList.add(2);System.out.println(myArrayList.get(2));}
}

输出结果：
test.PosIllegalException: Pos位置不合法！！！
   at test.MyArrayList.checkPos2(MyArrayList.java:78)
   at test.MyArrayList.get(MyArrayList.java:94)
   at test.test.main(test.java:9)
-1

3.5 改

3.5.1 把 pos 位置的元素修改成 value

实现条件：
1、如果为空就不能修改；
2、检查 pos 位置的合法性。

public class MyArrayList implements IList {@Overridepublic void set(int pos, int value) {try{checkEmpty();checkPos2(pos);arr[pos] = value;}catch (EmptyException e){e.printStackTrace();}catch (PosIllegalException e){e.printStackTrace();}}
}

3.5.2 删除某个元素

实现条件：
1、判断是否为空，本来就是空的不用删除；
2、从 pos 位置到最后一个下标，将最后一个元素覆盖到前面一个元素。

public class Test {public static void main(String[] args) {MyArrayList myArrayList = new MyArrayList();myArrayList.add(1);myArrayList.add(2);myArrayList.add(3);myArrayList.add(4);myArrayList.add(5);myArrayList.remove(3);myArrayList.display();}
}

3.5.3 清空

对于基本数据类型的数组，直接将有效数组长度赋值为0，对后续操作并无影响。比如清空之后再新增元素，即调用 add(int data)，那么会将 data 的值覆盖到 arr[0] 上，即使原本内存中已经在 arr[0] 上存放了值也会被覆盖掉。

但是对于引用类型，存放的是引用，如果没有及时将引用变量置空，那么那份被引用的空间将一直无法被内存回收，因此容易造成内存泄漏。

public class MyArrayList implements IList{@Overridepublic void clear() {this.usedSize = 0; // 对于基本数据类型，该方法不会造成内存泄漏// 但是对于引用类型，存放的是引用，因为没有被置为空，其引用的对象不能被内存回收，也就一直占用着那份内存，容易造成内存泄漏// 所以如果是引用类型，需要以下操作：/*for (int i = 0; i < usedSize; i++) {arr[i] = null;}this.usedSize = 0;*/}
}

到这里所有的操作都已实现，下面是 MyArrayList 的完整代码

package test_8_5;import java.util.Arrays;public class MyArrayList implements IList{private int[] arr;private int usedSize;private static final int DEFAULT_CAPACITY = 10;public MyArrayList(){arr = new int[this.DEFAULT_CAPACITY];}public boolean isFull(){return this.usedSize == this.arr.length;}@Overridepublic void add(int data) {if (isFull()){// 如果满了，需要扩容grow();}this.arr[this.usedSize] = data;this.usedSize++;}private void grow(){this.arr = Arrays.copyOf(this.arr,2*this.arr.length);}private void checkPos(int pos) throws PosIllegalException {if (pos < 0 || pos > usedSize){throw new PosIllegalException("Pos位置不合法！！！");}}@Overridepublic void add(int pos, int data) {try{checkPos(pos);if (isFull()){grow();}usedSize += 1;for (int i = usedSize-1; i > pos; i--) {arr[i] = arr[i-1];}arr[pos] = data;}catch (PosIllegalException e){System.out.println("插入pos元素的位置不合法！！");e.printStackTrace();}}@Overridepublic boolean contains(int toFind) {for (int i = 0; i < this.usedSize; i++) {if (arr[i] == toFind){return true;}}return false;}@Overridepublic int indexOf(int toFind) {for (int i = 0; i < this.usedSize; i++) {if (arr[i] == toFind){return i;}}return -1;}private void checkPos2(int pos) throws PosIllegalException{if (pos < 0 || pos >= usedSize){throw new PosIllegalException("Pos位置不合法！！！");}}public boolean isEmpty(){return this.usedSize == 0;}private void checkEmpty(){if (isEmpty()){throw new EmptyException("顺序表为空！！！");}}@Overridepublic int get(int pos) {try{checkEmpty();checkPos2(pos);return arr[pos];}catch (EmptyException e){e.printStackTrace();}catch (PosIllegalException e){e.printStackTrace();}return -1;}@Overridepublic void set(int pos, int value) {try{checkEmpty();checkPos2(pos);arr[pos] = value;}catch (EmptyException e){e.printStackTrace();}catch (PosIllegalException e){e.printStackTrace();}}@Overridepublic void remove(int toRemove) {try{checkEmpty();int pos = indexOf(toRemove);if (pos == -1){return;}for (int i = pos; i < usedSize -1; i++) {  // -1是为了防止arr[i+1]的时候越界arr[i] = arr[i+1];}usedSize--;}catch (EmptyException e){e.printStackTrace();}}@Overridepublic int size() {return this.usedSize;}@Overridepublic void clear() {this.usedSize = 0; // 对于基本数据类型，该方法不会造成内存泄漏// 但是对于引用类型，存放的是引用，因为没有被置为空，其引用的对象不能被内存回收，也就一直占用着那份内存，容易造成内存泄漏// 所以如果是引用类型，需要以下操作：/*for (int i = 0; i < usedSize; i++) {arr[i] = null;}this.usedSize = 0;*/}@Overridepublic void display() {for (int i = 0; i < this.usedSize; i++) {System.out.print(arr[i] + " ");}// 不能使用 foreach 遍历数组，因为我们只需要显示usedSize范围内的元素}
}

四、认识 ArrayList

4.0 说明

1. ArrayList 是以泛型方式实现的，使用时必须要先实例化；

2. ArrayList 实现了 RandomAccess 接口，表明 ArrayList 支持随机访问；

3. ArrayList 实现了 Cloneable 接口，表明 ArrayList 是可以 clone 的；

4. ArrayList 实现了 Serializable 接口，表明 ArrayList 是支持序列化的；

5. 和 Vector 不同，ArrayList 不是线程安全的，在单线程下可以使用，在多线程中可以选择Vector 或者 CopyOnWriteArrayList；

6. ArrayList 底层是一段连续的空间，并且可以动态扩容，是一个动态类型的顺序表。

4.1 成员变量

public class ArrayList<E> extends AbstractList<E>implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{private static final int DEFAULT_CAPACITY = 10;private static final Object[] EMPTY_ELEMENTDATA = {};private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};transient Object[] elementData; // non-private to simplify nested class accessprivate int size;// ……
}

上面的成员变量中与我们刚刚编写的 MyArrayList 中的具有相似性：

4.2 构造方法

public class ArrayList<E> extends AbstractList<E>implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{public ArrayList(int initialCapacity) {if (initialCapacity > 0) {this.elementData = new Object[initialCapacity];} else if (initialCapacity == 0) {this.elementData = EMPTY_ELEMENTDATA;} else {throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);}}public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}public ArrayList(Collection<? extends E> c) {elementData = c.toArray();if ((size = elementData.length) != 0) {// c.toArray might (incorrectly) not return Object[] (see 6260652)if (elementData.getClass() != Object[].class)elementData = Arrays.copyOf(elementData, size, Object[].class);} else {// replace with empty array.this.elementData = EMPTY_ELEMENTDATA;}}
}

4.2.1 指定顺序表的初始容量

如果在实例化顺序表时传入一个整数作为参数，那么会调用第一个构造方法。根据传入参数的大小决定顺序表的容量：如果大于0，创建与参数大小一样的数组；如果等于0，给空数组；再否则抛出初始容量不合法的异常。

如：ArrayList<Integer> list = new ArrayList<>(12); 构造一个具有12个容量的列表。

4.2.2 无参构造方法

如：ArrayList<Integer> list = new ArrayList<>(); 构造一个空的列表，推荐写法。

❔这个构造方法，其实并没有给分配内存，为什么还可以进行 add 的操作？

分析源码得到的结论是，第一次使用 add 方法的时候分配内存大小为 10，如果后面再操作发现容量满了，那么就是 1.5 倍进行扩容。理解为，初始容量为10，若满了，将扩容为15。

1. 检测是否真正需要扩容，如果是调用grow准备扩容

2. 预估需要库容的大小

        初步预估按照1.5倍大小扩容

        如果用户所需大小超过预估1.5倍大小，则按照用户所需大小扩容

        真正扩容之前检测是否能扩容成功，防止太大导致扩容失败

3. 使用copyOf进行扩容

4.2.3 利用其他 Collection 构建 ArrayList

4.3 常用方法

方法	解释
size()	获取有效元素个数
boolean add(E e)	尾插 e
void add(int index, E element)	将 e 插入到 index 位置
boolean addAll(Collection<? extends E> c)	尾插 c 中的元素
E remove(int index)	删除 index 位置元素，该元素之后的元素统一往前搬移一个位
boolean remove(Object o)	删除遇到的第一个 o
E get(int index)	获取下标 index 位置元素
E set(int index, E element)	将下标 index 位置元素设置为 element
void clear()	清空
boolean contains(Object o)	判断 o 是否在线性表中
int indexOf(Object o)	返回第一个 o 所在下标
int lastIndexOf(Object o)	返回最后一个 o 的下标
List subList(int fromIndex, int toIndex)	截取部分 list

与上面自己实现的 myArrayList 中的方法大相径庭，此处需要留意的是 addAll()、remove()、subList()、set() 方法。

public class test {public static void main(String[] args) {ArrayList<Integer> list = new ArrayList<>();  // 第2个构造方法。list.add(4);list.add(9);list.add(0);list.add(1);list.add(1,0);System.out.println(list);   // [4, 0, 9, 0, 1]ArrayList<Integer> list1 = new ArrayList<>();list1.add(2);list1.addAll(list);System.out.println(list1);  // [2, 4, 0, 9, 0, 1]list1.remove(0);System.out.println(list1);  // [4, 0, 9, 0, 1]list1.remove(new Integer(0));System.out.println(list1);  // [4, 9, 0, 1]}
}

public class test {public static void main(String[] args) {// 截取部分 listArrayList<Integer> list = new ArrayList<>();  // 第2个构造方法。list.add(1);list.add(2);list.add(3);list.add(4);list.add(5);list.add(6);System.out.println(list);   // [1, 2, 3, 4, 5, 6]List<Integer> list1 = list.subList(1,3);System.out.println(list1);  // [2, 3]System.out.println("-----------------");list1.set(0,666);System.out.println(list1);  // 预期输出 [666, 3]，运行之后达到预期System.out.println(list);  // 预期没有变化 [1, 2, 3, 4, 5, 6]，运行结果得到 [1, 666, 3, 4, 5, 6]}
}

由上一个代码运行结果可见，使用 subList 截取本质上是将下标为 1 的引用给了 list1，而不是复制了一份。因此使用 set 修改 list1 本质上是修改 list。

4.4 ArrayList 的遍历

上面举的例子可以直接输出表的内容是因为 ArrayList 中重写了 toString 方法。下面将通过3种遍历方法来访问顺序表的数据。

4.4.1 for 循环 + get()方法

public class test {public static void main(String[] args) {ArrayList<Integer> list = new ArrayList<>();list.add(1);list.add(2);list.add(3);list.add(4);list.add(5);list.add(6);for (int i = 0; i < list.size(); i++) {System.out.print(list.get(i) + " ");  // 1 2 3 4 5 6 }}
}

4.4.2 foreach

public class test {public static void main(String[] args) {ArrayList<Integer> list = new ArrayList<>();list.add(1);list.add(2);list.add(3);list.add(4);list.add(5);list.add(6);// for (int x: list)  // 拆箱操作for (Integer x: list) {System.out.print(x + " ");}}
}

4.4.3 迭代器

有两种迭代器，一种是 interator，另一种是 listInterator （两者首字母都是小写），其不同在于后者拓展了前者的功能。

public class test {public static void main(String[] args) {System.out.println("------迭代器 iterator 循环------");Iterator<Integer> it = list.iterator();while (it.hasNext()){System.out.print(it.next() + " ");}System.out.println();System.out.println("------迭代器 listIterator 循环------");ListIterator<Integer> it2 = list.listIterator();while (it2.hasNext()){System.out.print(it2.next() + " ");}System.out.println();System.out.println("------迭代器 listIterator 循环------");System.out.println("      ·拓展功能，指定位置倒着输出");ListIterator<Integer> it3 = list.listIterator(list.size());while (it3.hasPrevious()){System.out.print(it3.previous() + " ");}   // 6 5 4 3 2 1}
}

五、练习

5.1 删除

输入两行字符串，从 str1 中删除所有包含 str2 的字符，得到新的字符串。（大小写敏感）

要求：使用 ArrayList，相比使用 StringBuilder 的方法，性能有所提高。

示例1：
输入：
str1 : Welcome to China!
str2 : come
输出：Wl t China!
示例2：
输入：
str1 : Today is Tuesday.
str2 : days
输出：To i Tue.

public class test {public static void main(String[] args) {Scanner in = new Scanner(System.in);String str1 = in.nextLine();String str2 = in.nextLine();ArrayList<Character> list = new ArrayList<>();for (int i = 0; i < str1.length(); i++) {char ch = str1.charAt(i);if (!str2.contains(ch + "")){list.add(ch);}}for (int i = 0; i < list.size(); i++) {System.out.print(list.get(i));}}
}

一个小技巧：str2.contains(ch+"");
在不改变原来的意义前提下，将字符变字符串
contains() 方法的参数需要是字符串类型的数据，但是 ch 是字符类型的，那么加一个 ""，就使得 ch 变成了字符串，且没有新增任何不该存在的值。

5.2 杨辉三角

给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。

在 leetcode 上给出的模板中，返回类型要求是 List<List<Integer>> （？！这是个什么东东）

【那么，我们这里插入一个知识点（六、二维表），为了排版好看，请跳转到相应位置。】

public List<List<Integer>> generate(int numRows) {List<List<Integer>> ret = new ArrayList<>();// 处理杨辉三角第一行List<Integer> startRow = new ArrayList<>();startRow.add(1);ret.add(startRow);// 从第2行开始循环新增一维数组for (int i = 1; i < numRows; i++) {List<Integer> curRow = new ArrayList<>(); // 当前行// 第一列的元素肯定是1curRow.add(1);// 处理中间List<Integer> preRow = ret.get(i-1);  // 当前行的上一行for (int j = 1; j < i; j++) {  // 也是从第2列开始，列数要小于行数，因为对角线右边没有值int val1 = preRow.get(j);int val2 = preRow.get(j-1);curRow.add(val1 + val2);}// 最后一列也是1curRow.add(1);ret.add(curRow);  // 最后将当前行给二维数组}return ret;
}

测试：

5.3 综合练习——洗牌

描述：
新买的一副扑克牌，去掉大小王剩52张牌，总共有花色4种：♠ ♥ ♣ ♦，每种花色共13张牌；
洗牌；
3位玩家随机抽取5张牌。

步骤：

1、自定义类型：Card
属性：花色、牌号

package playCard;public class Card {private String suit;private int rank;public Card(String suit, int rank) {this.suit = suit;this.rank = rank;}@Overridepublic String toString() {/*return "Card{" +"suit='" + suit + '\'' +", rank=" + rank +'}';*/return "{" + suit + rank + "} ";}
}

2、设置牌号和花色对应，生成按顺序的52张牌

package playCard;import java.util.ArrayList;
import java.util.List;public class CardDemo {private static final String[] suits = {"♠","♥","♣","♦"};public List<Card> buyCards(){List<Card> cardList = new ArrayList<>(); // 相当于纸牌盒，用于存放for(int i = 1; i <= 13; i++){    // 1~13号牌for(int j = 0; j < 4; j++){  // 4种花色String suit = suits[j];int rank = i;Card card = new Card(suit, rank);  // 花色对应牌号生成一张牌cardList.add(card); // 将生成的牌放到纸牌盒}}return cardList;}
}

package playCard;import java.util.List;public class Play {public static void main(String[] args) {CardDemo cardDemo = new CardDemo();List<Card> cardList = cardDemo.buyCards();System.out.println(cardList);}
}

输出结果：
[{♠1} , {♥1} , {♣1} , {♦1} , {♠2} , {♥2} , {♣2} , {♦2} , {♠3} , {♥3} , {♣3} , {♦3} , {♠4} , {♥4} , {♣4} , {♦4} , {♠5} , {♥5} , {♣5} , {♦5} , {♠6} , {♥6} , {♣6} , {♦6} , {♠7} , {♥7} , {♣7} , {♦7} , {♠8} , {♥8} , {♣8} , {♦8} , {♠9} , {♥9} , {♣9} , {♦9} , {♠10} , {♥10} , {♣10} , {♦10} , {♠11} , {♥11} , {♣11} , {♦11} , {♠12} , {♥12} , {♣12} , {♦12} , {♠13} , {♥13} , {♣13} , {♦13} ]

3、洗牌

原理：从最后一张牌（下标为51）开始，与前面下标为 0~50的随机一张牌进行交换，交换完之后到下一张（下标为50）；也可以从第一张牌开始与后面的牌进行交换，但因为生成随机数下标一般是从0开始，所以采用第一种方法。

package playCard;import java.util.ArrayList;
import java.util.List;
import java.util.Random;public class CardDemo {// 略public void shuffle(List<Card> cardList){Random random = new Random();for (int i = cardList.size() -1; i > 0; i--) {int j = random.nextInt(i);  // 生成0~i-1范围的随机数swap(cardList,i,j);}}private void swap(List<Card> cardList, int i, int j){/*料想的交换：Card tmp = cardList[i];cardList[i] = cardList[j];cardList[j] = tmp;但因为 cardList 不是数组，因此无法进行上面的操作*/Card tmp = cardList.get(i);cardList.set(i,cardList.get(j));cardList.set(j,tmp);}
}

package playCard;import java.util.List;public class Play {public static void main(String[] args) {CardDemo cardDemo = new CardDemo();// 买52张牌，展示List<Card> cardList = cardDemo.buyCards();System.out.println(cardList);System.out.println("洗牌后：");// 洗牌cardDemo.shuffle(cardList);System.out.println(cardList);}
}

4、发牌

原理：每个玩家相当于一张表，整个牌桌就相当于存了三张表的二维表。

package playCard;import java.util.ArrayList;
import java.util.List;
import java.util.Random;public class CardDemo {// ......public List<List<Card>> play(List<Card> cardList){List<Card> player1 = new ArraysList<>();  // 每个玩家手里的牌List<Card> player2 = new ArraysList<>();List<Card> player3 = new ArraysList<>();List<List<Card>> desk = new ArraysList<>();  // 牌桌desk.add(player1);desk.add(player2);desk.add(player3);for(int i = 0; i < 5; i++){for(int j = 0; j < 3; j++){Card card = cardList.remove(i);// 把对应的牌放到玩家的手上，那纸牌盒上的牌就少了desk.get(j).add(card);}}return desk;}
}

package playCard;import java.util.List;public class Play{public static void main(String[] args){// ......List<List<Card>> desk = cardDemo.play(cardList);for(int i = 0; i < desk.size(); i++){System.out.println("第" + (i+1) + "个玩家的牌：" + desk.get(i));}System.out.println("剩余的牌：");System.out.println(cardList);}
}

输出示例：
[{♠1} , {♥1} , {♣1} , {♦1} , {♠2} , {♥2} , {♣2} , {♦2} , {♠3} , {♥3} , {♣3} , {♦3} , {♠4} , {♥4} , {♣4} , {♦4} , {♠5} , {♥5} , {♣5} , {♦5} , {♠6} , {♥6} , {♣6} , {♦6} , {♠7} , {♥7} , {♣7} , {♦7} , {♠8} , {♥8} , {♣8} , {♦8} , {♠9} , {♥9} , {♣9} , {♦9} , {♠10} , {♥10} , {♣10} , {♦10} , {♠11} , {♥11} , {♣11} , {♦11} , {♠12} , {♥12} , {♣12} , {♦12} , {♠13} , {♥13} , {♣13} , {♦13} ]
洗牌后：
[{♠11} , {♥2} , {♠2} , {♥12} , {♥1} , {♥4} , {♦8} , {♠5} , {♥9} , {♦13} , {♣8} , {♣7} , {♠3} , {♥7} , {♠13} , {♦1} , {♠1} , {♥6} , {♣4} , {♠9} , {♠7} , {♦7} , {♣5} , {♥3} , {♠8} , {♥8} , {♣11} , {♣12} , {♦10} , {♥5} , {♠4} , {♣9} , {♦9} , {♣10} , {♠10} , {♥13} , {♣6} , {♣3} , {♣13} , {♣2} , {♥10} , {♦12} , {♥11} , {♦5} , {♠6} , {♣1} , {♦6} , {♠12} , {♦4} , {♦2} , {♦3} , {♦11} ]
第1个玩家的牌：[{♠11} , {♥1} , {♥9} , {♠3} , {♠1} ]
第2个玩家的牌：[{♥2} , {♥4} , {♦13} , {♥7} , {♥6} ]
第3个玩家的牌：[{♠2} , {♦8} , {♣8} , {♠13} , {♣4} ]
剩下的牌：
[{♥12} , {♠5} , {♣7} , {♦1} , {♠9} , {♠7} , {♦7} , {♣5} , {♥3} , {♠8} , {♥8} , {♣11} , {♣12} , {♦10} , {♥5} , {♠4} , {♣9} , {♦9} , {♣10} , {♠10} , {♥13} , {♣6} , {♣3} , {♣13} , {♣2} , {♥10} , {♦12} , {♥11} , {♦5} , {♠6} , {♣1} , {♦6} , {♠12} , {♦4} , {♦2} , {♦3} , {♦11} ]

六、二维表

List<List<Integer>> 类似于二维数组，其初始化方法如下：

七、ArrayList 的问题与思考

对于顺序表，其优点是查找速度快。但它有以下的缺点：

1. ArrayList 底层使用连续的空间，任意位置插入或删除元素时，需要将该位置后序元素整体往前或者往后搬移，故时间复杂度为 O(N)

2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。

3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。

为了解决上面的问题，产生了链表。

查看全文

http://www.lryc.cn/news/611485.html