顺序表顺序表是一种线性数据结构使用一段物理地址(内存)连续的存储单元通常为数组依次存储数据元素并在此基础上封装了增、删、改、查等操作而普通数组只提供下标访问和长度属性。在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) { //ArrayListInteger arrayList1 new ArrayList(); ListInteger 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); //插入一组元素 ListInteger 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 ListInteger 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 方法的返回值类型是 ListE而不是 ArrayListE ListInteger 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) { ArrayListInteger 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 风格的迭代器写法. 不仅仅是在集合类里. IteratorInteger 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 ArrayListCard creatDeck() { ArrayListCard 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); ArrayListCard deck creatDeck(); System.out.println(deck); // 洗牌, 标准库有一个现成的方法, shuffle, 就可以完成洗牌. 打乱 ArrayList 中的顺序. // 修改原有的 ArrayList. Collections.shuffle(deck); System.out.println(洗牌后: deck); // 发牌, 假设有 3 个玩家, 每个玩家发 5 张牌. (梭哈) 使用三个 ArrayList 表示三个玩家. // ArrayListCard player1 new ArrayList(); // ArrayListCard player2 new ArrayList(); // ArrayListCard player3 new ArrayList(); // 通过类似于 二维数组 的方式, 构造二维的 ArrayList. ArrayListArrayListCard 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 中 ArrayListCard player players.get(i); player.add(card); } } // 打印每个玩家的牌 for(int i 0; i 3; i){ ArrayListCard player players.get(i); System.out.println(玩家 (i1) 的牌 player); } } }5.2杨辉三角import java.util.ArrayList; import java.util.List; public class yang_hui_san_jiao { public ListListInteger generate(int numRows) { ListListInteger result new ArrayList(); //每次循环构造一行数据 for (int i 0; i numRows; i) { //构造ArrayList 表示当前行 ListInteger row new ArrayList(); //填写若干列 for (int j 0; j i; j) { //针对第一列和最后一列 都是1 if (j 0 || j i) { row.add(1); } //其他情况 先取出上一行 再找到两数相加 else { ListInteger 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[i1] 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[i1]; 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(); } }