数据结构(一)顺序表
关于顺序表在前文中就出现了，顺序表的使用这次系统的讲解下
再讲之前先看一下，这篇文章要讲什么：
本篇文章主要讲解的就是这三个。先看第一个：
目录
1.List接口
1.1基础操作
1.2元素操作
1.3批量操作
1.4搜索与定位
1.5视图与迭代
1.6转换方法
1.7Java 8+ 新增默认方法
1.8Java 9+ 静态工厂方法
1.9继承自 Object 的方法
2.AbstractList抽象类
2.1AbstractList实现List接口的方法
2.2AbstractLis新增的关键方法
2.3AbstractList抽象类的子类责任
3. ArrayList 类
3.1ArrayList 类重写的方法
3.1.1ArrayList 类的变(常)量
3.1.2ArrayList 类的新增方法
1.1构造方法
看完这些下面再手动实现一下，ArrayList 类的基本逻辑
3.1ArrayList 类的实现
3.1.1添加方法
1.1有效元素长度问题
1.2默认容积与动态扩容问题
1.4尾插实现
1.5任意插入
3.1.2删除方法和获取元素、交换元素
1.1删除方法
1.2获取元素
1.3交换元素
1.List接口
List接口 是 Java 集合框架的核心，继承自 Collection 接口，定义了对有序集合的操作。以下是其
所有方法（按功能分类）：
1.1基础操作
| int size() | 返回元素数量 |
| boolean isEmpty() | 判断是否为空 |
| void clear() | 清空所有元素 |
1.2元素操作
| boolean add(E e) | 尾部添加元素 |
| void add(int index, E element) | 指定位置插入元素 |
| E set(int index, E element) | 替换指定位置元素 |
| E get(int index) | 获取指定位置元素 |
| E remove(int index) | 删除指定位置元素 |
| boolean remove(Object o) | 删除首次出现的指定元素 |
1.3批量操作
| boolean addAll(Collection<? extends E> c) | 添加整个集合 |
| boolean addAll(int index, Collection<? extends E> c) | 从指定位置插入集合(批量插入) |
| boolean removeAll(Collection<?> c) | 删除所有匹配元素 |
| boolean retainAll(Collection<?> c) | 仅保留匹配元素 |
| boolean containsAll(Collection<?> c) | 判断是否包含整个集合 |
1.4搜索与定位
| int indexOf(Object o) | 返回o首次出现位置 |
| int lastIndexOf(Object o) | 返回o最后一次出现位置(反向查找) |
| boolean contains(Object o) | 判断是否包含元素 |
1.5视图与迭代
| List<E> subList(int fromIndex, int toIndex) | 返回子列表视图 |
| ListIterator<E> listIterator() | 返回列表迭代器 |
| ListIterator<E> listIterator(int index) | 从指定位置开始的迭代器 |
| Iterator<E> iterator() | 返回迭代器（继承自 Collection） |
迭代即是打印
1.6转换方法
| Object[] toArray() | 转为对象数组 |
| <T> T[] toArray(T[] a) | 转为指定类型数组 |
1.7Java 8+ 新增默认方法
| default void replaceAll(UnaryOperator<E> operator) | 用操作结果替换所有元素 |
| default void sort(Comparator<? super E> c) | 根据比较器排序 |
| default Spliterator<E> spliterator() | 返回分割迭代器 |
1.8Java 9+ 静态工厂方法
| static <E> List<E> of() | 创建空不可变列表 |
| static <E> List<E> of(E e1) | 创建单元素不可变列表 |
| static <E> List<E> of(E... elements) | 创建多元素不可变列表 |
| static <E> List<E> copyOf(Collection<? extends E> coll) | 创建集合的不可变副本 |
1.9继承自 Object 的方法
| boolean equals(Object o) | 比较列表内容是否相等 |
| int hashCode() | 返回哈希值 |
这里只需要看下方法搞清 AbstractList 到底实现 List 的哪些方法(以上红色字体的都是被AbstractList 实现的)
2.AbstractList抽象类
AbstractList 是 Java 集合框架中的抽象类，java.util 包中。它提供了List接口的骨架实现，极大简
化了自定义列表的实现过程。
2.1AbstractList实现List接口的方法
| boolean addAll(int index, Collection<? extends E> c) | 批量插入 |
| void clear() | 清空列表 |
| boolean isEmpty() | 判断空列表 |
| int size() | 元素数量 |
| E remove(int index) | 删除元素 |
| E set(int index, E element) | 替换元素 |
| E get(int index) | 获取元素 |
| void add(int index, E element) | 插入元素 |
| boolean add(E e) | 添加元素到末尾 |
| Iterator<E> iterator() | 获取迭代器 |
| ListIterator<E> listIterator() | 列表迭代器 |
| ListIterator<E> listIterator(int index) | 从指定位置开始的迭代器 |
| int indexOf(Object o) | 查找元素位置 |
| int lastIndexOf(Object o) | 反向查找元素 |
| List<E> subList(int fromIndex, int toIndex) | 获取子列表 |
在这里 List 接口基本都在AbstractList 抽象类里面实现，这里只展示了3/2。
这些都是AbstractList抽象类 实现List接口的，下面看 AbstractLis 新增的方法
2.2AbstractLis新增的关键方法
| protected void removeRange(int fromIndex, int toIndex) | 删除范围元素 |
| protected transient int modCount | 修改计数器 |
| public boolean equals(Object o) | 列表相等性比较 |
| public int hashCode() | 哈希值计算 |
2.3AbstractList抽象类的子类责任
AbstractList的子类必须实现 get() 和 size() ，并根据需要覆盖add(),set(),remove(int) 等方法
(就是get()和 size()是AbstractLis的抽象方法)
可能有人就疑问了：在AbstractList中不是实现了这两个方法了吗？为什么还要实现
1.AbstractList只是提供了List接口的基本实现
2.是因为数据结构的不可知性 看图：
可以看到AbstractList的子类有三种且都是类，也就是说至少有三种数据结构，而获取元素(get())和
计算大小(size())的实现完全依赖具体数据结构,所以这是强制的。
前戏准备完毕，下面是本篇文章的重点 ArrayList 类 顺序表的实现
3. ArrayList 类
ArrayList 是 Java 中基于动态数组实现的顺序表，其核心原理是通过维护一个可扩容
的数组来实动态存储，接下来看一下ArrayList 类的关键方法和变(常)量
3.1ArrayList 类重写的方法
AbstractList提供了List接口的基本实现,而ArrayList 继承了AbstractList并重写了父类的关键方法：
| public E get(int index) | 返回指定位置的元素 |
| public E set(int index, E element) | 替换指定位置的元素 |
| public void add(int index, E element) | 在指定位置插入元素 |
| public E remove(int index) | 删除指定位置的元素 |
| public int size() | 返回元素数量 |
| public boolean isEmpty() | 判断空列表 |
| public void clear() | 清空所有元素 |
| public Iterator<E> iterator() | 返回迭代器 |
| public ListIterator<E> listIterator() | 返回列表迭代器 |
| public int indexOf(Object o) | 返回元素首次出现的索引 |
| public int lastIndexOf(Object o) | 返回元素最后一次出现的索引 |
| public boolean addAll(int index, Collection<? extends E> c) | 在指定位置插入集合 |
3.1.1ArrayList 类的变(常)量
| transient Object[] elementData | 存储元素的数组（数据容器） |
| private int size | 当前元素数量（非数组容量 ） |
| private static final int DEFAULT_CAPACITY = 10 | 默认初始容量（首次添加元素时使用） |
| private static final Object[] EMPTY_ELEMENTDATA = {} | 空数组实例（用于空构造） |
| private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {} | 默认空数组（区分扩容逻辑） |
transient 是一个关键字，在后续实现 ArrayList 类 时会将ta改为 private 而 transient 这个后续会说
3.1.2ArrayList 类的新增方法
| public void trimToSize() | 将数组容量缩减到当前元素数量 |
| public void ensureCapacity(int minCapacity) | 预扩容（避免频繁扩容） |
| private void grow(int minCapacity) | 内部扩容机制（通常扩容至原容量的1.5倍） |
| public Object clone() | 返回浅拷贝副本 |
| public <T> T[] toArray(T[] a) | 返回包含所有元素的数组（类型安全） |
| protected void removeRange(int fromIndex, int toIndex) | 移除指定索引范围内的元素 |
1.1构造方法
| public ArrayList() | 创建初始容量为10的空列表 |
| public ArrayList(int initialCapacity) | 指定初始容量 |
| public ArrayList(Collection<? extends E> c) | 用指定集合初始化 |
看完这些下面再手动实现一下，ArrayList 类的基本逻辑
3.1ArrayList 类的实现
ArrayList 是 Java 中基于动态数组实现的顺序表，其核心原理是通过维护一个可扩容
的数组来实动态存储
下面我创建一个 Array类 ，实现一下 ArrayList 类 的核心方法更进一步的了解顺序表：
public Class Array<E>{private E[] es; // 存储元素的数组 }
3.1.1添加方法
在写这个方法前先想问题：
1.添加方法是从头部添加还是尾部添加？
2.是否可以在任意位置添加？
3.如果顺序表满了或顺序表没空间怎么办？
先从第一个问题解决 添加方法是从头部添加还是尾部添加？
这是可能就有人说了：既然考虑到了,添加方法是从头部添加还是从尾部添加 那么不妨创建两个方
法。
但正确答案其实是尾部添加，这是因为头插法的效率太低，每次调用都需要移动所有元素而尾插只需要尾值就行了。
如果使用尾插法，就要解决：有效元素长度问题、扩容与默认容积问题及尾插如何实现：
1.1有效元素长度问题
//有效元素长度问题
public int size(){int count = 0;//计数器for(int i = 0; i < es.length;i++){//判断数组元素是否为空，为空返，不为空++if(es[i] != null){count++;}else if(es[i] == null){return count;}}//极限长度返回if(count == es.length){return count;}return -1;}
如果数组没有空间 返回-1，如果有返回count。1.2默认容积与动态扩容问题
//默认容积问题
private final int MAXIMUM_LENGTH = 10;//常量public Array() {//构造方法//由于泛型无法实例化(泛型类型不明确)，所以将Object强转成泛型数组this.es = (E[]) new Object[MAXIMUM_LENGTH];}//扩容问题public void grow() {//(E[])与上面代码同理E[] container = (E[])new Object[es.length];//接收旧数组元素for(int i = 0; i<size(); i++){container[i] = es[i];}//创建比之前大两倍的数组(这样做之前的元素会消失)es = (E[])new Object[es.length*2];//拿回旧数组的元素for(int i = 0; i<container.length; i++){es[i] = container[i];}}解决默认容积与扩容问题这两个问题后，连带这个问题也被解决了：如果顺序表满了或顺序表没空间怎么办？
1.4尾插实现
//尾插实现
public boolean add(E a){//判断有效元素长度是否等于极限值if(size() != es.length) {//不等于时尾插元素es[size()] = a;return true;} else if (size() == es.length) {//等于时扩容grow();//扩容后尾插元素es[size()] = a;return true;}return false;}现在解决了添加问题和扩容与默认容积问题，就剩下是否可以在任意位置插入 答案是可以的
1.5任意插入
先说一下解决此方法的思路，方法形式为 add(下标，值)：
//第一阶段:大纲整理
假设下标为 i = 0，值为 k = 8，数组es内容为{1，2，3，4};也就是将k的值，放在0下标这就意味着数组所有元素都要往后移一位同时之前放在0下标的旧元素也要被保存起来现在整理一下 设i为指向下表的指针，k为指向新值的指针，j为指向旧值的指针理清了大纲后就要考虑如何实现了
下标：i = 0;
j 做为存储旧元素，首先要做的是保存一份旧元素的副本，为元素交换做准备 即:j = es[i];j 拿到旧元素后，k 值就可以进行新老元素的交换 即：es[i] = k;现在数组情况：es{ 8 , 2 , 3 , 4 , null}下标 0 1 2 3 4
现在 0 坐标的值是：8，下一步就是将 j值 放到 1下标，这意味这指向下标的i要++ 但新的问题出现了
1下标的值也要被保存，所以 j值 不能立即放在1下标，这时可用 k 来存放 1下标的值到这里j k都成为了指向
值的指针(也可以用k来保存j值，j来保存 1下标的值)
即：
i++; i = 1;
k = es[i];
es[i] = j;交换完后继续 i++
i++; i = 2;然后循环就行了
这招我称之为“左右脚交替”（j k不停接收旧值）最后稍加改造，下面看完整代码：
public void add(int i, E k){E j;//解决尾插问题if(i == size()-1){add(k);return;}//保证es的容量，不等于有效元素的最大值if(size() != es.length|| i != es.length){//循环处理交换while(true){j = es[i];es[i] = k;i++;//奇数段判断if(size() % 2 != 0 && es[i] == null){es[i] = j;return;}k = es[i];es[i] = j;i++;//偶数段判断if(size() % 2 == 0 && es[i] == null){es[i] = k;return;}}//判断数组容量是否大于或等于有效元素最大值} else if (es.length >= size()) {//扩容方法grow();System.out.println("以扩容，请再次调用此方法");}}现在解释一下，偶数段和奇数段：
ta俩在段中是起到结束循环的作用下面看图：
由于 j k 两值是交替保存值的，这就会发生有效元素长度为奇数时正好轮到 j 来保存最后一个值，偶数时 k 轮为保存最后一个值。
看执行结果：
public static void main(String[] args) {Array<Integer> array = new Array<>();array.add(1);array.add(2);array.add(3);array.add(4);array.add(0,8);array.add(1,9);//打印数组元素方法array.iterate();}结果：8 9 1 2 3 4 3.1.2删除方法和获取元素、交换元素
1.1删除方法
比较简单 ：
es{ 1 , 2 , 3 , 4}
下标 0 1 2 3
假设要删除0下标的值:循环{
es[i] = es[i+1];
i++
}
es[size() - 1] = null1 2 3 4 -> 2 2 3 4 -> 2 3 3 4 -> 2 3 4 4 -> 2 3 4直接将想要删除的值覆盖掉，后面一个一个覆盖上，最后将尾值赋为null
public E remove(int index){//判断容量，防止数组越界if(size() != es.length) {int k = index;int size = size();E oldalue = es[index];//控制循环次数，假设index为0，数组长度为4//那么交换次数为 4 - 1(size - (k + 1))for (int i = 1; i <= size - (k + 1); i++) {//交换发生地es[index] = es[index + 1];index++;}//处理尾值es[size() - 1] = null;//返回被删除的值return oldalue;} else if (size() == es.length) {grow();System.out.println("已触发扩容，请重新调用");}//删除失败返回nullreturn null;}1.2获取元素
这个和幼儿园坐一桌
public E get(int index){return es[index];}1.3交换元素
这个也和幼儿园坐一桌
public E set(int index, E element){E oldalue = element;//直接交换es[index] = element;//返回被交换值return oldalue;}看结果：
public static void main(String[] args) {Array<Integer> array = new Array<>();array.add(1); 1array.add(2); 2array.add(3); 3array.add(4); 4array.add(0,8); 0array.add(1,9); 被删除array.remove(1); 删除1下标的值Integer i = array.get(1); 获取1下标的值array.set(2,10); 替换2下标的值array.iterate(); 打印数组元素的值System.out.println();System.out.println(i);}
结果：
8 1 10 3 4
1结束，下一篇的文章是顺序表的OJ题