一、基础知识

1.1 数据结构类的继承图

1.2 List 介绍

1.3 线性表

1. 概念：n个具有相同特性的数据元素的有限序列
   • 常见的线性表：顺序表、链表、栈、队列…
     • 二叉树是棵树，不是线性表
   • 线性表的结构：
     • 逻辑结构：在逻辑上是线性结构，在物理结构（内存）上并不一定是连续的
       • 对于顺序表来说，逻辑上和物理上都是连续的，其底层是数组
       • 对于链表来说，逻辑上是连续的，物理上则是不连续的
     • 存储形式：线性表在物理上存储时，通常以数组和链式结构的形式存储

二、数据结构 – 顺序表

2.1 什么是顺序表以及优缺点

1. 概念：用一段物理地址连续的存储单元依次存储数据元素的线性结构，是个数据结构
2. 实现方式：一般采用数组存储，链表也能实现
3. 优缺点：
   • 优点：查找和更新元素效率很高，为O(1)
   • 缺点：
     • 每次【插入/删除】数据，都需要移动元素，极端情况下，如果插入到0下标，那么元素复杂度为O(n)
     • 当数组满了之后，会进行1.5倍扩容，但如果只是新增一个元素，这意味着会浪费大量空间
   • 缺点的解决方法：使用链表
4. 使用场景： 适用于经常进行查找元素或者更新元素的场景下

2.2 用数组实现顺序表

细节解析

代码

public class SeqList {private int[] elem;private int usedSize;private static final int DEFAULT_CAPACITY = 5;public SeqList() {this.elem = new int[DEFAULT_CAPACITY];}// 打印顺序表，注意：该方法并不是顺序表中的方法，而是为了方便看测试结果给出的public void display() {for (int i = 0; i < this.usedSize; i++) {System.out.print(this.elem[i] +" ");}System.out.println();}// 新增元素,默认在数据 最后新增public void add(int data) {//首先得判断满的情况if(isFull()) {resize();}this.elem[usedSize] = data;usedSize++;}public boolean isFull() {return usedSize == elem.length;}// 判定是否包含某个元素public boolean contains(int toFind) {for (int i = 0; i < this.usedSize; i++) {if(elem[i] == toFind) {return true;}}return false;}// 查找某个元素对应的位置 下标public int indexOf(int toFind) {for (int i = 0; i < this.usedSize; i++) {if(elem[i] == toFind) {return i;}}return -1;}// 获取 pos 位置的元素public int get(int pos) {if(!checkPos(pos)) {//这个是自定义异常//此处不返回整型int，因为如果是一个数，可能会误认为pos位置的元素是该数throw new PosOutBoundsException("get 获取数据时，位置不合法！");}return elem[pos];}// 获取顺序表长度public int size() {return this.usedSize;}// 给 pos 位置的元素设为 value【更新的意思 】public void set(int pos, int value) {if(!checkPos(pos)) {//这个是自定义异常throw new PosOutBoundsException("set 数据时，位置不合法！");}this.elem[pos] = value;}private boolean checkPos(int pos) {if(pos < 0 || pos >= usedSize) {return false;}return true;}// 在 pos 位置新增元素public void add(int pos, int data) {if(pos < 0 || pos > this.usedSize) {//这个是自定义异常throw new PosOutBoundsException("add 元素的时候，pos位置不合法！");}if(isFull()) {resize();}//挪数据for (int i = this.usedSize-1; i >= pos ; i--) {this.elem[i+1] = this.elem[i];}//存数据this.elem[pos] = data;this.usedSize++;}private void resize() {elem = Arrays.copyOf(elem,2*elem.length);}//删除第一次出现的关键字keypublic void remove(int toRemove) {if(isEmpty()) {return;}int index = indexOf(toRemove);if(index == -1) {return;//没有你要删除的数字}for (int i = index; i < usedSize-1; i++) {this.elem[i] = this.elem[i+1];}usedSize--;//elem[us] = null;}public boolean isEmpty() {return usedSize == 0;}// 清空顺序表public void clear() {//方式一/*for (int i = 0; i < usedSize; i++) {this.elem[i] = null;}*/usedSize = 0;}}

三、ArrayList

3.1 Java中如何使用ArrayList

3.2 ArrayList源码

无参构造方法

add方法

扩容方法

指定初始容量构造

利用其他 Collection 构建 ArrayList

3.3 ArrayList方法介绍

3.4 ArrayList的遍历