9. 获取顺序表第一个元素

    /**
     * 获取数组中第一个元素
     *
     * @return 数组中第一个元素
     */
    public E getFirst() {
        return get(0);
    }

在实现了获取指定索引位置的元素后，获取顺序表的第一个元素同样是对get方法的复用，将0做为索引值进行参数传递即可。

10. 获取顺序表最后一个元素

    /**
     * 获取数组中最后一个元素
     *
     * @return 数组中最后一个元素
     */
    public E getLast() {
        return get(size - 1);
    }

获取顺序表最后一个元素也是对get方法的复用，在此不进行赘述

11. 修改指定索引位置的元素

    /**
     * 设置索引为index位置的元素值为e
     *
     * @param index 索引位置
     * @param e 要进行替换的元素值
     */
    public void set(int index, E e) {
        if (index < 0 || index >= size) {
            throw new ArrayIndexOutOfBoundsException();
        }
        data[index] = e;
    }

在之前获取指定索引位置的元素时，先判断索引是否合法，如果合法将对应位置的元素进行返回。同理，先判断索引位置是否合法，如果合法就将当前位置的元素使用我们接收到的元素e进行替换。

12. 判断顺序表中是否包含指定元素

    /**
     * 判断数组中是否存在元素e
     *
     * @param e 元素e
     * @return 是否存在元素e
     */
    public boolean contains(E e) {
        for (int i = 0; i < size; i++) {
            if (data[i].equals(e)) {
                return true;
            }
        }
        return false;
    }

对于判断顺序表中是否存在指定元素来说，对顺序表进行线性查找，如果找到了相应的数据，就返回true，如果在对顺序表遍历结束后仍然没有找到指定元素，说明当前顺序表中不存在指定元素，返回false

注意：在这里因为是对象的比较，使用equals方法进行比较，如果是基本数据类型（如int，double等）的比较就要使用==来进行比较

13. 获取顺序表中指定元素的索引

    /**
     * 查找数组中元素e的索引，如果不存在返回 -1
     *
     * @param e 元素e
     * @return 元素e在数组中的索引
     */
    public int find(E e) {
        for (int i = 0; i < size; i++) {
            if (data[i].equals(e)) {
                return i;
            }
        }
        return -1;
    }

获取指定元素的索引同样使用线性查找法，使用equals进行比较，如果找到相同的元素则返回对应的索引值，如果遍历完顺序表后仍然没有找到指定元素则返回-1，说明当前元素不存在。

14. 删除指定索引位置的元素

    /**
     * 删除索引位置为 index 的元素并返回被删除的元素
     *
     * @param index 删除元素的索引
     * @return 被删除的元素
     */
    public E remove(int index) {
        if (index < 0 || index >= size) {
            throw new ArrayIndexOutOfBoundsException();
        }
        // 先将返回值进行存储
        E res = data[index];
        for (int i = index + 1; i < size; i++) {
            data[i - 1] = data[i];
        }
        size--;
        data[size] = null;
        // 如果当前数组中的元素不足数组容量的一半
        if (size < data.length / 2) {
            // 重新分配空间
            resize(data.length / 2);
        }
        return res;
    }

在之前进行元素的添加时要考虑顺序表是否还有容量，在删除元素时不需要考虑是否还有容量，但是也要考虑相应的有关于数组缩容问题。因此要考虑以下问题：

删除当前元素后，顺序表中的元素个数是否不足数组容量的一半？
删除指定索引的元素时，传来的索引值是否合法？

对于第一个问题的解决方法为在删除元素后，对当前顺序表的元素个数与数组的容量的一半进行比较，如果发现当前元素个数小于数组容量的一半时，我们可以继续调用resize方法重新分配数组的容量（resize方法在之后会详细解释），当前的实现结果就是将数组的容量缩容至原数组都一半，对于内存的节省来说更有好处。

第二个问题解决方式与之前处理一样，查看索引值是否小于0以及是否大于等于当前顺序表都元素个数

删除元素的本质也是将当前索引值的后一个元素开始，依次向前移动，覆盖掉前一个元素，最后再将size--，维护指针，删除结束后将临时存储的被删除的元素返回即可。

删除元素过程如下图所示：

注意：顺序表的删除本质上是用后一个元素将前一个元素依次覆盖，移动了size指针后此时指针指向的元素仍然为原本顺序表中的最后一个元素，因为在用户的实际操作中，size指向的元素无法被访问到，所以并没有什么影响。但是我们在这里使用了泛型，在Java的GC（垃圾回收机制）中因为此时顺序表的最后一个元素仍然被size指向引用，无法被回收，因此在这里手动执行data[size] = null;将当前的引用回收。

15. 删除并返回顺序表第一个元素

    /**
     * 删除并返回数组的第一个元素
     *
     * @return 数组的第一个元素
     */
    public E removeFirst() {
        return remove(0);
    }

与之前的思路一致，在有了删除指定索引位置的元素方法后，删除并返回顺序表第一个元素也是对刚才实现的remove方法进行复用，在此不做赘述。

16. 删除并返回顺序表最后一个元素

    /**
     * 删除并返回数组中的最后一个元素
     *
     * @return 数组中的最后一个元素
     */
    public E removeLast() {
        return  remove(size - 1);
    }

删除顺序表中最后一个元素同样是对remove方法的复用，在此也不多做赘述。

17. 删除顺序表中的指定元素

    /**
     * 从数组中删除元素e
     *
     * @param e 数组中被删除的元素
     * @return 是否删除成功
     */
    public boolean removeElement(E e) {
       int index = find(e);
       if (index == -1) {
           return false;
       }
       remove(index);
       return true;
    }

删除顺序表中指定的元素本质上是对之前实现的获取顺序表中指定元素的索引方法和删除指定索引位置元素方法的复用，首先通过find方法获取到要删除元素的索引，接着对索引进行判断，查看当前元素是否存在，如果当前元素存在则将获取到的索引值作为remove方法的参数传递，将当前索引位置的元素删除即可。

18. 对顺序表进行动态的扩容和缩容

    /**
     * 对数组进行扩容
     *
     * @param newCapacity 扩容后数组的容量
     */
    private void resize(int newCapacity) {
        E[] newData = (E[]) new Object[newCapacity];
        for (int i = 0; i < size; i++) {
            newData[i] = data[i];
        }
        data = newData;
    }

三、运行结果

在进行结果测试前，为了方便于观察，在这里我重写了Array类的toString方法

@Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        builder.append(String.format("Array: size = %d, capacity = %d\n", size, data.length));
        builder.append("[");
        for (int i = 0; i < size; i++) {
            builder.append(data[i]);
            if (i != size - 1) {
                builder.append(", ");
            }
        }
        builder.append("]");
        return builder.toString();
    }

四、总结

以上便是Java语言对线性表的顺序表示和实现，和以前使用C语言来写顺序表最大的感受就是曾经觉得很难写、很费脑的代码再次实现时感觉变得很容易了，同时对于很多的方法也有了复用的思想，对线性表的理解更加深刻。高兴于自己成长的同时也更加深刻意识到以后的路会更加的艰难，希望自己可以在未来的道路上戒骄戒躁、稳扎稳打，哪怕再困难，也不会放弃！

源码

以下是源代码

1. Array类源代码

package net.csdn.array;
/**
 * @author zhangrongkang
 * @date 2022/6/26
 */
public class Array<E> {
    private E[] data;
    /**
     * 数组中元素的数量
     */
    private int size;
    /**
     * 构造函数，传入数组的容量capacity构造数组
     *
     * @param capacity 初始数组大小
     */
    public Array(int capacity) {
        data = (E[]) new Object[capacity];
        size = 0;
    }
    /**
     * 无参构造函数，默认数组大小为0
     */
    public Array() {
        this(10);
    }
    /**
     * 获取数组中的元素个数
     *
     * @return 数组当前的元素个数
     */
    public int getSize() {
        return size;
    }
    /**
     * 获取数组当前容量
     *
     * @return 数组当前容量
     */
    public int getCapacity() {
        return data.length;
    }
    /**
     * 判断数组是否为空
     *
     * @return 数组是否为空
     */
    public boolean isEmpty() {
        return size == 0;
    }
    /**
     * 在数组末尾添加一个元素
     *
     * @param e 要添加的元素
     */
    public void addLast(E e) {
        add(size, e);
    }
    /**
     * 在数组的头部添加元素e
     *
     * @param e 要添加的元素
     */
    public void addFirst(E e) {
        add(0, e);
    }
    /**
     * 向数组中索引为index位置添加元素e
     *
     * @param index 索引位置
     * @param e 元素e
     */
    public void add(int index, E e) {
        // 判断数组空间是否已满
        if (size == data.length) {
            // 对数组进行扩容
            resize(2 * data.length);
        }
        // 越界判断
        if (index < 0 || index > size) {
            throw new ArrayIndexOutOfBoundsException();
        }
        for (int i = size - 1; i >= index; i--) {
            data[i + 1] = data[i];
        }
        data[index] = e;
        size++;
    }
    /**
     * 获取索引为index位置的元素
     *
     * @param index 索引位置
     * @return 索引为index位置的元素
     */
    public E get(int index) {
        if (index < 0 || index >= size) {
            throw new ArrayIndexOutOfBoundsException();
        }
        return data[index];
    }
    /**
     * 获取数组中第一个元素
     *
     * @return 数组中第一个元素
     */
    public E getFirst() {
        return get(0);
    }
    /**
     * 获取数组中最后一个元素
     *
     * @return 数组中最后一个元素
     */
    public E getLast() {
        return get(size - 1);
    }
    /**
     * 设置索引为index位置的元素值为e
     *
     * @param index 索引位置
     * @param e 要进行替换的元素值
     */
    public void set(int index, E e) {
        if (index < 0 || index >= size) {
            throw new ArrayIndexOutOfBoundsException();
        }
        data[index] = e;
    }
    /**
     * 判断数组中是否存在元素e
     *
     * @param e 元素e
     * @return 是否存在元素e
     */
    public boolean contains(E e) {
        for (int i = 0; i < size; i++) {
            if (data[i].equals(e)) {
                return true;
            }
        }
        return false;
    }
    /**
     * 查找数组中元素e的索引，如果不存在返回 -1
     *
     * @param e 元素e
     * @return 元素e在数组中的索引
     */
    public int find(E e) {
        for (int i = 0; i < size; i++) {
            if (data[i].equals(e)) {
                return i;
            }
        }
        return -1;
    }
    /**
     * 删除索引位置为 index 的元素并返回被删除的元素
     *
     * @param index 删除元素的索引
     * @return 被删除的元素
     */
    public E remove(int index) {
        if (index < 0 || index >= size) {
            throw new ArrayIndexOutOfBoundsException();
        }
        // 先将返回值进行存储
        E res = data[index];
        for (int i = index + 1; i < size; i++) {
            data[i - 1] = data[i];
        }
        size--;
        data[size] = null;
        // 如果当前数组中的元素不足数组容量的一半
        if (size < data.length / 2) {
            // 重新分配空间
            resize(data.length / 2);
        }
        return res;
    }
    /**
     * 删除并返回数组的第一个元素
     *
     * @return 数组的第一个元素
     */
    public E removeFirst() {
        return remove(0);
    }
    /**
     * 删除并返回数组中的最后一个元素
     *
     * @return 数组中的最后一个元素
     */
    public E removeLast() {
        return  remove(size - 1);
    }
    /**
     * 从数组中删除元素e
     *
     * @param e 数组中被删除的元素
     * @return 是否删除成功
     */
    public boolean removeElement(E e) {
       int index = find(e);
       if (index == -1) {
           return false;
       }
       remove(index);
       return true;
    }
    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        builder.append(String.format("Array: size = %d, capacity = %d\n", size, data.length));
        builder.append("[");
        for (int i = 0; i < size; i++) {
            builder.append(data[i]);
            if (i != size - 1) {
                builder.append(", ");
            }
        }
        builder.append("]");
        return builder.toString();
    }
    /**
     * 对数组进行扩容
     *
     * @param newCapacity 扩容后数组的容量
     */
    private void resize(int newCapacity) {
        E[] newData = (E[]) new Object[newCapacity];
        for (int i = 0; i < size; i++) {
            newData[i] = data[i];
        }
        data = newData;
    }
}

2. 测试类源代码

package net.csdn.array;
/**
 * @author zhangrongkang
 * @date 2022/6/26
 */
public class ArrayMain {
    public static void main(String[] args) {
        System.out.println("声明新的顺序表，初始容量为10：");
        Array<Integer> array = new Array<>(10);
        for (int i = 0; i < 10; i++) {
            array.addLast(i);
        }
        System.out.println(array + "\n");
        System.out.println("向索引为 1 的位置添加元素 100：");
        array.add(1, 100);
        System.out.println(array + "\n");
        System.out.println("在顺序表的头部添加 -1：");
        array.addFirst(-1);
        System.out.println(array + "\n");
        System.out.println("在顺序表的尾部添加 101：");
        array.addLast(101);
        System.out.println(array + "\n");
        System.out.println("移除索引位置为 2 的元素：");
        array.remove(2);
        System.out.println(array + "\n");
        System.out.println("移除顺序表中的元素 4：");
        array.removeElement(4);
        System.out.println(array + "\n");
        System.out.println("移除顺序表中的第一个元素：");
        array.removeFirst();
        System.out.println(array + "\n");
        System.out.println("移除顺序表中的最后一个元素：");
        array.removeLast();
        System.out.println(array + "\n");
        System.out.println("元素7的索引位置为：" + array.find(7));
        System.out.println("数组中是否包含元素4：" + array.contains(4));
    }
}

写在本文的最后：

回顾大学三年的经历，深刻的认识到了计算机基础知识的重要性。在实习的过程中，更加深刻的认识到了团队的重要性，曾经很天真的认为一个人就能拿下一整个大的项目，但是真的在见识到了大型的项目后，才明白曾经的自己是多么的幼稚和无知，大型的项目不是写出来、能跑就行的项目，对性能的要求更高、对技术的选型也更为严谨…完成大型项目需要团队中每个人的全力以赴，更需要大家每个人的互补，齐心协力才能所向披靡。

在这里我也希望自己能和各位前辈、各位同学、大佬们一些学习交流，欢迎大家加入到技术交流群中，我们一起分享技术知识、一起进步！

线性表的顺序表示和实现（Java）（二）