1.顺序表的创建 2.常见操作 3.遍历 4.扩容机制 5.例子
1.顺序表的创建
在集合框架中,ArrayList是⼀个普通的类,实现了List接口,具体框架图如下:
2.常见操作
代码实现
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 是可以直接打印的. 不像数组, 还需要转成 Stringlist.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);//按照下标删除 但下标不能超出总长度范围 也可以同时记录一下被删除的元素 返回resultInteger result = list.remove(1);System.out.println(list);System.out.println(result);//按照值来删除 下标也不能超出指定的范围 如果 List 中不包含这个值, 就返回 falseboolean isRemoved = list.remove(Integer.valueOf(1));System.out.println(list);System.out.println(isRemoved);// 虽然是删除 2 这个值, 由于有多个, 实际上只删除了第一个.list.remove(Integer.valueOf(2));System.out.println(list);//但这样可以删除所有2List<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 修改, 也会影响到原始的 ListSystem.out.println(list);//获取元素个数 sizeSystem.out.println(list.size());list.add(8);System.out.println(list.size());}
}
3.遍历
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是⼀个动态类型的顺序表,即:在插入元素的过程中会自动扩容。
5.例子
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-10for (int i = 2; i <= 10; i++) {Card card = new Card("" + i, suit);deck.add(card);}//处理JQKAdeck.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++) {//针对第一列和最后一列 都是1if (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];} // 默认的初始容量为 10public MyArrayList(int capacity) {if(capacity <= 10) capacity = 10;data = new String[capacity];}@Overridepublic 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();}}