数据结构(一)顺序表-EW帮帮网

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] = null

1 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("已触发扩容，请重新调用");
        }
        //删除失败返回null
        return 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); 1
        array.add(2); 2
        array.add(3); 3
        array.add(4); 4
        array.add(0,8); 0
        array.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题

数据结构(一)顺序表

1.List接口

1.1基础操作

1.2元素操作