一.顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构一般情况下采用数组存储。在数组上完成数据的增删查改。顺序表接口的实现(手动实现仅为方便初学理解实际开发中都用java自带的不用手写):public class SeqList { // 底层存储数组 private int[] array; // 顺序表中实际元素个数 private int size; // 默认初始容量 private static final int DEFAULT_CAPACITY 10; // 默认构造方法初始化默认容量的数组 SeqList() { this.array new int[DEFAULT_CAPACITY]; this.size 0; } // 将顺序表的底层容量设置为initcapacity SeqList(int initcapacity) { // 校验初始容量合法性 if (initcapacity 0) { throw new IllegalArgumentException(初始容量不能小于等于0: initcapacity); } this.array new int[initcapacity]; this.size 0; } // 新增元素,默认在数组最后新增 public void add(int data) { // 先检查容量不足则扩容 ensureCapacity(size 1); // 把元素放到size位置然后size自增 array[size] data; } // 在 pos 位置新增元素 public void add(int pos, int data) { // 1. 校验pos的合法性pos必须在[0, size]范围内 checkPositionForAdd(pos); // 2. 检查容量不足则扩容 ensureCapacity(size 1); // 3. 将pos及之后的元素向后移动一位从后往前移避免覆盖 // System.arraycopy(源数组, 源起始位置, 目标数组, 目标起始位置, 移动长度) System.arraycopy(array, pos, array, pos 1, size - pos); // 4. 放入新元素 array[pos] data; // 5. 实际元素个数1 size; } // 判定是否包含某个元素 public boolean contains(int toFind) { // 遍历数组找到则返回true for (int i 0; i size; i) { if (array[i] toFind) { return true; } } return false; } // 查找某个元素对应的位置返回第一个匹配的索引找不到返回-1 public int indexOf(int toFind) { for (int i 0; i size; i) { if (array[i] toFind) { return i; } } return -1; } // 获取 pos 位置的元素 public int get(int pos) { // 校验pos合法性pos必须在[0, size-1]范围内 checkPosition(pos); return array[pos]; } // 给 pos 位置的元素设为 value public void set(int pos, int value) { // 校验pos合法性 checkPosition(pos); array[pos] value; } // 删除第一次出现的关键字key public void remove(int toRemove) { // 1. 找到要删除元素的索引 int index indexOf(toRemove); // 2. 找不到则直接返回 if (index -1) { return; } // 3. 找到则移动元素将index1到size-1的元素向前移动一位 int numMoved size - index - 1; if (numMoved 0) { System.arraycopy(array, index 1, array, index, numMoved); } // 4. 最后一个元素置为0可选帮助理解不影响逻辑size-1 array[--size] 0; } // 获取顺序表长度实际元素个数 public int size() { return this.size; } // 清空顺序表 public void clear() { // 方式1直接重置size简单高效底层数组保留下次添加会覆盖 this.size 0; // 方式2可选遍历置空帮助GCint是基本类型无GC此处仅演示 // for (int i 0; i size; i) { // array[i] 0; // } // this.size 0; } // 打印顺序表 public void display() { if (size 0) { System.out.println(顺序表为空); return; } // 拼接元素格式[1, 2, 3] StringBuilder sb new StringBuilder(); sb.append([); for (int i 0; i size; i) { sb.append(array[i]); if (i ! size - 1) { sb.append(, ); } } sb.append(]); System.out.println(顺序表内容 sb); } // -------------- 私有辅助方法 -------------- // 检查容量如果当前容量不足进行扩容扩容为原容量的1.5倍 private void ensureCapacity(int minCapacity) { int oldCapacity array.length; // 如果需要的最小容量 当前数组长度触发扩容 if (minCapacity oldCapacity) { // 新容量 旧容量 旧容量/2右移1位等价于除以2 int newCapacity oldCapacity (oldCapacity 1); // 防止扩容后仍不足比如minCapacity特别大 if (newCapacity minCapacity) { newCapacity minCapacity; } // 数组拷贝生成新数组 int[] newArray new int[newCapacity]; System.arraycopy(array, 0, newArray, 0, size); this.array newArray; } } // 校验pos是否合法用于添加操作pos范围 [0, size] private void checkPositionForAdd(int pos) { if (pos 0 || pos size) { throw new IndexOutOfBoundsException(添加位置非法: pos pos , 合法范围: [0, size ]); } } // 校验pos是否合法用于查询/修改/删除pos范围 [0, size-1] private void checkPosition(int pos) { if (pos 0 || pos size) { throw new IndexOutOfBoundsException(位置非法: pos pos , 合法范围: [0, (size - 1) ]); } } // 测试方法 public static void main(String[] args) { SeqList seqList new SeqList(5); // 测试尾部添加 seqList.add(10); seqList.add(20); seqList.add(30); seqList.display(); // 输出顺序表内容[10, 20, 30] // 测试指定位置添加 seqList.add(1, 15); seqList.display(); // 输出顺序表内容[10, 15, 20, 30] // 测试包含、索引查找 System.out.println(是否包含20 seqList.contains(20)); // true System.out.println(20的索引 seqList.indexOf(20)); // 2 // 测试获取、修改 System.out.println(索引1的元素 seqList.get(1)); // 15 seqList.set(1, 16); seqList.display(); // 输出顺序表内容[10, 16, 20, 30] // 测试删除 seqList.remove(20); seqList.display(); // 输出顺序表内容[10, 16, 30] // 测试大小、清空 System.out.println(顺序表大小 seqList.size()); // 3 seqList.clear(); seqList.display(); // 输出顺序表为空 } }二.ArrayList简介【说明】1. ArrayList是以泛型方式实现的使用时必须要先实例化2. ArrayList实现了RandomAccess接口表明ArrayList支持随机访问3. ArrayList实现了Cloneable接口表明ArrayList是可以clone的4. ArrayList实现了Serializable接口表明ArrayList是支持序列化的5. 和Vector不同ArrayList不是线程安全的在单线程下可以使用在多线程中可以选择Vector或者CopyOnWriteArrayList6. ArrayList底层是一段连续的空间并且可以动态扩容是一个动态类型的顺序表三.ArrayList使用①ArrayList的构造方法解释ArrayList()无参构造ArrayList(Collection? extends E c)利用其他 Collection 构建 ArrayListArrayList(int initialCapacity)指定顺序表初始容量总结上面一堆介绍不用管记住一般用List参数类型(包装类)/自定义类 arrnew ArrayList();这个就类似于C里的Vector动态数组而且类型里需要填对象的包装类比如int 就填Integer char就填Characterpublic static void main(String[] args) { // ArrayList创建推荐写法 // 构造一个空的列表 ListInteger list1 new ArrayList(); // 构造一个具有10个容量的列表 ListInteger list2 new ArrayList(10); list2.add(1); list2.add(2); list2.add(3); // list2.add(hello); // 编译失败ListInteger已经限定了list2中只能存储整形元素 // list3构造好之后与list中的元素一致 ArrayListInteger list3 new ArrayList(list2); // 避免省略类型否则任意类型的元素都可以存放使用时将是一场灾难 List list4 new ArrayList(); list4.add(111); list4.add(100); }②ArrayList常见操作提取后的表格方法解释boolean add(E e)尾插 evoid add(int index, E element)将 e 插入到 index 位置boolean addAll(Collection? extends E c)尾插 c 中的元素E remove(int index)删除 index 位置元素boolean remove(Object o)删除遇到的第一个 oE get(int index)获取下标 index 位置元素E set(int index, E element)将下标 index 位置元素设置为 elementvoid clear()清空boolean contains(Object o)判断 o 是否在线性表中int indexOf(Object o)返回第一个 o 所在下标int lastIndexOf(Object o)返回最后一个 o 的下标ListE subList(int fromIndex, int toIndex)截取部分 list这里的方法想调用都要用 实例化名字.方法名(...) 这种格式最大的区别是获取元素的时候用 .get(i)而且想删除元素有两个方法按储存Integer举例如果你直接 arr.remove(index) 这是按下标删除。如果你是arr.remove((Integer)key)就是找到最近的key元素删除而不是全部删除public static void main(String[] args) { ListString list new ArrayList(); list.add(JavaSE); list.add(JavaWeb); list.add(JavaEE); list.add(JVM); list.add(测试课程); System.out.println(list); // 获取list中有效元素个数 System.out.println(list.size()); // 获取和设置index位置上的元素注意index必须介于[0, size)间 System.out.println(list.get(1)); list.set(1, JavaWEB); System.out.println(list.get(1)); // 在list的index位置插入指定元素index及后续的元素统一往后搬移一个位置 list.add(1, Java数据结构); System.out.println(list); // 删除指定元素找到了就删除该元素之后的元素统一往前搬移一个位置 list.remove(JVM); System.out.println(list); // 删除list中index位置上的元素注意index不要超过list中有效元素个数,否则会抛出下标越界异常 list.remove(list.size()-1); System.out.println(list); // 检测list中是否包含指定元素包含返回true否则返回false if(list.contains(测试课程)){ list.add(测试课程); } // 查找指定元素第一次出现的位置indexOf从前往后找lastIndexOf从后往前找 list.add(JavaSE); System.out.println(list.indexOf(JavaSE)); System.out.println(list.lastIndexOf(JavaSE)); // 使用list中[0, 4)之间的元素构成一个新的SubList返回,但是和ArrayList共用一个elementData数组 ListString ret list.subList(0, 4); System.out.println(ret); list.clear(); System.out.println(list.size()); }③ArrayList的遍历ArrayList 可以使用三种方法遍历for循环、foreach、迭代器(1)for循环ListInteger arr new ArrayList(); arr.add(10); arr.add(20); arr.add(30); arr.add(40); arr.add(50); // 1. for 循环 下标遍历适合支持随机访问的集合如 ArrayList System.out.println( 方式1for循环 下标 ); for (int i 0; i arr.size(); i) { System.out.println(arr.get(i)); }(2)foreachListInteger arr new ArrayList(); arr.add(10); arr.add(20); arr.add(30); arr.add(40); arr.add(50); // 2. foreach 遍历简化写法底层也是迭代器 System.out.println(\n 方式2foreach ); for (Integer num : arr) { System.out.println(num); }(3)迭代器ListInteger arr new ArrayList(); arr.add(10); arr.add(20); arr.add(30); arr.add(40); arr.add(50); // 3. 使用迭代器遍历通用遍历方式适合所有 List 实现类 System.out.println(\n 方式3迭代器 ); IteratorInteger iterator arr.iterator(); while (iterator.hasNext()) { System.out.println(iterator.next());④ArrayList的扩容机制ArrayList是一个动态类型的顺序表即在插入元素的过程中会自动扩容⑤ArrayList储存自定义类ArrayList可以储存自定义类就比如储存一个Car类类里有private的成员变量brand,wheel等等想单独输出或者比较/修改这几个成员变量那就需要再Car类里写get方法和set方法