顺序表
顺序表是一种线性数据结构，使用一段物理地址(内存)连续的存储单元（通常为数组），依次存储数据元素，并在此基础上封装了增、删、改、查等操作；而普通数组只提供下标访问和长度属性。
在Java中，顺序表可以通过实例化 ArrayList 类来实现；ArrayList 内部封装了一个数组，并提供了丰富的方法来操作元素。
所有集合类（如 ArrayList）都位于java.util 包中，支持泛型以指定存储的元素类型。
1.ArrayList的构造
ArrayList是基于动态扩容数组实现的顺序表，支持泛型并实现了 RandomAccess、Cloneable、Serializable 接口，可进行随机访问、克隆与序列化。
推荐用List接口类型声明变量（向上转型），使代码依赖抽象接口而非具体实现，以降低耦合且便于替换实现（只需修改 new 后的类名）；若能预估元素数量，通过构造方法指定初始容量（即数组的初始大小）可减少扩容开销。
它不是线程安全的，适用于单线程，多线程环境可选用 Vector 或 CopyOnWriteArrayList。
2.ArrayList的常见操作
代码实现
import java.util.ArrayList; import java.util.List; public class Test1 { public static void main(String[] args) { //ArrayList<Integer> arrayList1 = new ArrayList<>(); List<Integer> list = new ArrayList<>(); //尾插 List 是可以直接打印的. 不像数组, 还需要转成 String list.add(1); list.add(2); list.add(3); list.add(4); list.add(2); System.out.println(list); // add 也可以指定位置来插入. 往下标 2 这个元素之前插入 100. 插入成功之后, 100 元素的下标就是 2 . list.add(2,100); System.out.println(list); // 头插 list.add(0, 200); System.out.println(list); // list.add(100, 300); 显然不行. 100 下标太大了.下标越界了；但是可以往 6 这个位置插入. 就相当于尾插. list.add(6, 300); System.out.println(list); //插入一组元素 List<Integer> list1 = new ArrayList<>(); list1.addAll(list); System.out.println(list1); //按照下标删除 但下标不能超出总长度范围 也可以同时记录一下被删除的元素 返回result Integer result = list.remove(1); System.out.println(list); System.out.println(result); //按照值来删除 下标也不能超出指定的范围 如果 List 中不包含这个值, 就返回 false boolean isRemoved = list.remove(Integer.valueOf(1)); System.out.println(list); System.out.println(isRemoved); // 虽然是删除 2 这个值, 由于有多个, 实际上只删除了第一个. list.remove(Integer.valueOf(2)); System.out.println(list); //但这样可以删除所有2 List<Integer> toRemove = new ArrayList<>(); toRemove.add(2); list.removeAll(toRemove); System.out.println(list); //获取元素 System.out.println(list.get(1)); //修改元素 list.set(0,100); System.out.println(list); //清空 list1.clear(); System.out.println(list1); //判断某元素是否存在 System.out.println(list.contains(3)); //返回第一个元素所在的下标 System.out.println(list.indexOf(100)); //返回最后一个元素所在的下标 System.out.println(list.lastIndexOf(100)); //截取部分list subList [1,3) 前闭后开 System.out.println(list.subList(1,3)); System.out.println(list); //subList 操作, 并不是创建一个 "副本" (拷贝一份), 而是得到原始 List 的片段. //注：此处 subList 方法的返回值类型是 List<E>，而不是 ArrayList<E> List<Integer> subList = list.subList(1,3); subList.set(0,1); System.out.println(subList); //针对 subList 修改, 也会影响到原始的 List System.out.println(list); //获取元素个数 size System.out.println(list.size()); list.add(8); System.out.println(list.size()); } }3.ArrayList的遍历
ArrayList可以使用三种方式遍历：for循环+下标、foreach、使用迭代器
import java.util.ArrayList; import java.util.Iterator; public class Test3 { public static void main(String[] args) { ArrayList<Integer> list = new ArrayList<>(); list.add(1); list.add(2); list.add(3); list.add(4); for(int i = 0; i < list.size(); i++){ System.out.println(list.get(i)); // list[i] 这样的写法是不行的. } //通过 foreach 遍历. num 就会依次被赋值成 list 中的每个元素 //这里的 num 只能用来 "读" 不能用来 "写" foreach 本质上就是迭代器写法的简化写法. // 此处 num 是一个临时变量. 不会影响到 List 中的元素的. for(Integer num: list){ System.out.println(num); } //数组不具备的方式, 通过 "迭代器" 来遍历. 典型的 Java 风格的迭代器写法. 不仅仅是在集合类里. Iterator<Integer> iterator = list.iterator(); while (iterator.hasNext()){ //通过 next 获取到 list 中的每个元素. 通过 hasNext 判定是否遍历结束. System.out.println(iterator.next()); } } }4.ArrayList的扩容机制
ArrayList是⼀个动态类型的顺序表，即：在插入元素的过程中会自动扩容。
5.ArrayList的使用
5.1模拟扑克牌
import java.util.ArrayList; import java.util.Collections; // 通过一个类, 表示 "一张牌" class Card{ private String rank; //点数 private String suit; //花色 public Card(String rank, String suit){ this.rank = rank; this.suit = suit; } // 搞一个 toString, 方便后续打印牌的内容 public String toString(){ return "(" + suit + rank + ")"; } } public class shi_xian_pukepai { // 通过这个方法创建一副扑克牌. 通过 ArrayList 表示了. deck--一副牌 private static ArrayList<Card> creatDeck() { ArrayList<Card> deck = new ArrayList<>(); // 把 4 种花色, 每个花色 13 个牌都创建进去. 不包含大小王 String[] suits = {"♠", "♥", "♣", "♦"}; for (String suit : suits) { //处理2-10 for (int i = 2; i <= 10; i++) { Card card = new Card("" + i, suit); deck.add(card); } //处理JQKA deck.add(new Card("J", suit)); deck.add(new Card("Q", suit)); deck.add(new Card("K", suit)); deck.add(new Card("A", suit)); } return deck; } public static void main(String[] args) { //Card card = new Card("A", "♦"); //System.out.println(card); ArrayList<Card> deck = creatDeck(); System.out.println(deck); // 洗牌, 标准库有一个现成的方法, shuffle, 就可以完成洗牌. 打乱 ArrayList 中的顺序. // 修改原有的 ArrayList. Collections.shuffle(deck); System.out.println("洗牌后: " + deck); // 发牌, 假设有 3 个玩家, 每个玩家发 5 张牌. (梭哈) 使用三个 ArrayList 表示三个玩家. // ArrayList<Card> player1 = new ArrayList<>(); // ArrayList<Card> player2 = new ArrayList<>(); // ArrayList<Card> player3 = new ArrayList<>(); // 通过类似于 "二维数组" 的方式, 构造二维的 ArrayList. ArrayList<ArrayList<Card>> players = new ArrayList<>(); for(int i = 0; i < 3; i++){ players.add(new ArrayList<>()); } // 发牌, 取出牌堆中的第一张牌, 放到第一个玩家的 ArrayList 中. // 再取出牌堆中的第二张牌, 放到第二个玩家的 ArrayList 中. 以此类推. 发 5 个轮次 for(int round = 0; round < 5; round++){ for(int i = 0; i < 3; i++){ // 取出牌堆中的第一张牌 Card card = deck.remove(0); // 放到对应玩家的 ArrayList 中 ArrayList<Card> player = players.get(i); player.add(card); } } // 打印每个玩家的牌 for(int i = 0; i < 3; i++){ ArrayList<Card> player = players.get(i); System.out.println("玩家" + (i+1) + "的牌" + player); } } }5.2杨辉三角
import java.util.ArrayList; import java.util.List; public class yang_hui_san_jiao { public List<List<Integer>> generate(int numRows) { List<List<Integer>> result = new ArrayList<>(); //每次循环，构造一行数据 for (int i = 0; i < numRows; i++) { //构造ArrayList 表示当前行 List<Integer> row = new ArrayList<>(); //填写若干列 for (int j = 0; j <= i; j++) { //针对第一列和最后一列 都是1 if (j == 0 || j == i) { row.add(1); } //其他情况 先取出上一行 再找到两数相加 else { List<Integer> lastRow = result.get(i - 1); int curValue = lastRow.get(j - 1) + lastRow.get(j); row.add(curValue); } } //此时这一行构造完 把这一行都添加到 result 中 result.add(row); } return result; } }6.ArrayList的模拟实现
代码实现
// 不写成泛型的方式. 只是保存 String 类型的数据~~ // 泛型方式, 写起来更麻烦一些. 未来面试的时候, 一般也都不要写泛型版本的. public class MyArrayList { private String[] data = null; // 通过这个数组, 来表示顺序表中的元素 private int size = 0; // 表示有效元素的个数. public MyArrayList() { data = new String[10]; } // 默认的初始容量为 10 public MyArrayList(int capacity) { if(capacity <= 10) capacity = 10; data = new String[capacity]; } @Override public String toString() { // 把有效元素转为字符串, 并拼接到一起. StringBuilder stringBuilder = new StringBuilder(); stringBuilder.append("["); for (int i = 0; i < size; i++) { stringBuilder.append(data[i]); // 如果 i 是 size - 1, 说明是最后一个元素, 不需要加 , 了. if (i < size - 1) stringBuilder.append(", "); } stringBuilder.append("]"); return stringBuilder.toString(); } // 实现扩容操作. private void resize() { // 1. 创建更长的数组, 新的数组容量是之前的 1.5 倍. String[] newData = new String[data.length + (data.length >> 1)]; // 2. 把旧数组的元素, 复制到新数组上. for (int i = 0; i < size; i++) { newData[i] = data[i]; } // 3. 使用新数组代替旧数组. data = newData; } // 实现尾插操作. 把新的元素添加到顺序表末尾. elem 就是 element(元素) 的缩写. 时间复杂度 O(1) // 虽然可能触发扩容 O(N), 但是认为在使用的时候通过设置良好的初始容量, 降低扩容的次数. public void add(String elem) { // 把 elem 放到 data 的最后一个位置上. 也就是下标为 size 的位置. // [0, size) 区间是有效元素. 需要实现扩容逻辑. if (size >= data.length) resize(); // 扩容操作. data[size] = elem; size++; } // 往中间位置插入. 往 index 元素之前插入, 确保新元素的下标就是 index. 时间复杂度 O(N) public void add(int index, String elem) { // 判定 index 是否合法. 此处是否要写作 index <= 0 或者 index >= size?? 边界值都需要重点讨论. // 如果 index 为 0, 意思是插入完毕后, 元素就处于 0 号位置. 就相当于 "头插" // 如果 index 为 size, 意思是插入完毕后, 元素处于 size 号位置. 就相当于 "尾插" if (index < 0 || index > size) throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size); if (size >= data.length) resize(); // 扩容操作. // 把元素放到 index 位置上. 进行搬运, 把 index 之后的元素, 都往后移动一个位置. // 需要从后往前遍历, 代入 size 为 6 的时候, 最后一个元素下标就是 5; 初始的搬运就是把 data[5] 放到 data[6] 上去 // 最终的代码就是 data[i+1] = data[i]是写作 i >= index 还是 i > index?? for (int i = size - 1; i >= index; i--) { data[i + 1] = data[i]; } // 把新元素放到 index 位置上 data[index] = elem; size++; } // 按照下标删除 返回被删除的元素的值 时间复杂度 O(N) public String remove(int index){ if(index < 0 || index >= size) throw new IndexOutOfBoundsException("Index: " + index + ", size: " + size); // 提前把删除的元素的值保存一份. 否则后面搬运的时候就会覆盖. String elem = data[index]; for(int i = index; i < size-1; i++) data[i] = data[i+1]; size--; return elem; } // 按照元素值来删除 如果删除成功, 返回 true. 否则, 返回 false. 如果 elem 本身不存在, 就认为是删除失败. 时间复杂度 O(N) public boolean remove(String elem) { // 先找到 elem 对应的位置在哪里 int removePos = 0; // 找到了. i 这个下标就是要删除的元素的位置. for (; removePos < size; removePos++) { if (data[removePos].equals(elem)) break; } // 上述循环结束, 有两种可能: 1. 没找到 elem, i 和 size 相等了. if (removePos == size) return false; //2. 找到了elem 拿着 removePos 进行删除 进行搬运操作. for (int i = removePos; i < size - 1; i++) { data[i] = data[i + 1]; } size--; //第二点也可以直接服用上一个删除用法 即 remove(removePos) return true; } //获取下标index的元素 时间复杂度 O(1) public String get(int index){ if (index < 0 || index >= size) throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size); return data[index]; } //将下标index位置元素设置为element 时间复杂度 O(1) public void set(int index, String element){ if (index < 0 || index >= size) throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size); data[index] = element; } // 删除所有元素. 时间复杂度 O(1) 不需要把数组中的每个元素都设为 null 之类的 public void clear() { size = 0; } //遍历, 看 elem 元素是否存在. 存在就返回 true 时间复杂度 O(N) public boolean contains(String elem) { for (int i = 0; i < size; i++) { if(data[i].equals(elem)) return true; } return false; } // 从前往后遍历, 看 elem 元素是否存在. 存在就返回它的第一个下标. 时间复杂度 O(N) public int indexOf(String elem){ for(int i = 0; i < size; i++) { if(data[i].equals(elem)) return i; } return -1; } // 从后往前遍历, 看 elem 元素是否存在. 存在就返回它的最后一个下标. 时间复杂度 O(N) public int lastIndexOf(String elem){ for(int i = size - 1; i >= 0; i--) { if(data[i].equals(elem)) return i; } return -1; } // 截取[fromIndex, toIndex) 区间的元素. 时间复杂度 O(N) // 创建一个新的 MyArrayList 对象. 把上述区间的元素, 添加到新的对象中即可. public MyArrayList subList(int fromIndex, int toIndex){ // 注意边界值. fromIndex 如果为 0, 是合法的情况. toIndex 如果是 size, 也是合法的情况 // fromIndex == toIndex 的时候, 也是合法, 得到空的区间. if(fromIndex < 0 || toIndex > size || fromIndex > toIndex) throw new IndexOutOfBoundsException("fromIndex: " + fromIndex + ", toIndex: " + toIndex); MyArrayList subList = new MyArrayList(toIndex-fromIndex); for(int i = fromIndex; i < toIndex; i++){ String elem = this.get(i); subList.add(elem); } return subList; } // 测试尾插 // 测试代码也很关键. 把每个功能点的测试代码单独拎出来, 作为一个测试方法. // 这种测试的思路称为 "单元测试" private static void text1(){ MyArrayList list = new MyArrayList(); list.add("Hello"); list.add("word"); list.add("word"); list.add("word"); list.add("word"); list.add("word"); list.add("word"); list.add("word"); list.add("word"); list.add("word"); System.out.println(list); // 还有办法, 不通过打印, 也能看到 list 中的内容. 借助调试器 } // 测试中间位置插入 private static void text2(){ MyArrayList list = new MyArrayList(); list.add(0,"a"); list.add(0,"b"); list.add(0,"c"); list.add(0,"d"); list.add(2,"x"); System.out.println(list); } // 测试删除操作 private static void test3(){ MyArrayList list = new MyArrayList(); list.add("aa"); list.add("bb"); list.add("cc"); String elem = list.remove(1); System.out.println(elem); System.out.println(list); } private static void test4(){ MyArrayList list = new MyArrayList(); list.add("aa"); list.add("bb"); list.add("cc"); boolean ret = list.remove("dd"); System.out.println(ret); System.out.println(list); } private static void test5(){ MyArrayList list = new MyArrayList(); list.add("aa"); list.add("bb"); list.add("cc"); System.out.println(list.contains("bb")); } private static void test6(){ MyArrayList list = new MyArrayList(); list.add("aa"); list.add("bb"); list.add("cc"); System.out.println(list.indexOf("bb")); } private static void test7(){ MyArrayList list = new MyArrayList(); list.add("aa"); list.add("bb"); list.add("cc"); list.add("dd"); System.out.println(list.subList(1,3)); } public static void main(String[] args) { test7(); } }
)
