Java线性表的顺序表示及实现

目录

• 前言
• 一、什么是顺序表？
• 二、顺序表的实现
• 1. 准备工作
• 2. 获取顺序表的元素个数
• 3. 获取顺序表当前的容量
• 4. 顺序表是否为空
• 5. 在指定索引位置添加元素
• 6. 在顺序表末尾添加元素
• 7. 在顺序表头部添加元素
• 8. 获取指定索引位置的元素
• 9. 获取顺序表第一个元素
• 10. 获取顺序表最后一个元素
• 11. 修改指定索引位置的元素
• 12. 判断顺序表中是否包含指定元素
• 13. 获取顺序表中指定元素的索引
• 14. 删除指定索引位置的元素
• 15. 删除并返回顺序表第一个元素
• 16. 删除并返回顺序表最后一个元素
• 17. 删除顺序表中的指定元素
• 18. 对顺序表进行动态的扩容和缩容
• 三、运行结果
• 四、总结
• 源码
• 1. Array类源代码
• 2. 测试类源代码

前言

在之前对顺序表使用C语言进行了简单的实现：C语言线性表顺序表示及实现

当时使用C语言进行实现是因为学校的教材使用的是C语言来进行实现，在后来的学习中，Java成为了我的主语言，使用不同的语言对顺序表来进行实现也可以加深我对语言的理解和应用。

一、什么是顺序表？

顺序表是在计算机内存中以数组的形式保存的线性表，线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素、使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系，采用顺序存储结构的线性表通常称为顺序表。顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。

二、顺序表的实现

在顺序表的定义中可以看到，顺序表是一组地址连续的存储单元，本质上是一种增加了一些基本操作功能的数组

在本文中要实现的功能有：

• 获取顺序表中的元素个数
• 获取顺序表当前的容量
• 顺序表是否为空
• 在指定索引位置添加元素
• 在顺序表末尾添加元素
• 在顺序表头部添加元素
• 获取指定索引位置的元素
• 获取顺序表第一个元素
• 获取顺序表最后一个元素
• 修改指定索引位置的元素
• 判断顺序表中是否包含指定元素
• 获取顺序表中指定元素的索引
• 删除指定索引位置的元素
• 删除并返回顺序表第一个元素
• 删除并返回顺序表最后一个元素
• 删除顺序表中的指定元素
• 对顺序表进行动态的扩容和缩容

1. 准备工作

在 IntelliJ IDEA 中新建普通的Java项目即可

 在新建好Java工程后，我们创建自己的顺序表类，在这里我对当前类命名为Array，在这里实现泛型，同时Array类中需要有两个成员属性：

• 存放数据的数组：data，类型为泛型数组
• 当前顺序表中元素的数量：size，类型为int

两个成员属性的访问权限都应该为private，用户不能够直接进行修改，只能通过对应的getter方法进行获取。 在成员属性中我们将存放数据的数组和顺序表中的元素数量只是进行了声明，但是并未进行初始化，因此==初始化的过程就需要在构造方法中进行==

• 有参构造：在进行有参构造时，我们只需要指定传入的参数为一个int类型的数据capacity，代表顺序表的初始容量，因此对data进行初始化泛型数组即可。同时当前顺序表中是没有元素的，代表顺序表中的元素个数size的初始值为0。
• 无参构造：在用户没有指定了顺序表的初始容量时我们可以自定义初始容量为10，仅需要通过this(10)进行有参构造的调用即可。

注意： 在Java中不能直接初始化泛型数组，需要先声明Object类型的数组后通过强制类型转换的方式将Object类型的数组转换为泛型数组

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);
    }
}

使用泛型的原因：使用泛型后可以将当前顺序表中存储对象，如果不使用泛型的话只能使用自己指定类型的数据，扩展性不强。因此使用泛型后可以将当前顺序表的使用扩展到所有类对象，只需要在创建时指定相应的对象即可。

2. 获取顺序表的元素个数

    /**
     * 获取数组中的元素个数
     *
     * @return 数组当前的元素个数
     */
    public int getSize() {
        return size;
    }

对于获取当前顺序表中的元素个数来说，因为我们定义的初始成员变量size代表的含义就是当前顺序表的元素个数，但是size变量的本质为当前顺序表的指针，指向顺序表最后一个元素的下一个位置 （元素的索引从0开始，最后一个元素的索引值比元素个数值小 1），不能直接进行修改，因此要想获取需要通过size元素的getter方法

同样地，对于获取顺序表的元素个数只需要将size返回即可

3. 获取顺序表当前的容量

    /**
     * 获取数组当前容量
     *
     * @return 数组当前容量
     */
    public int getCapacity() {
        return data.length;
    }

在对顺序表进行声明的时候，就已经将用户传来的或者默认的初始容量capacity作为数组的大小对data泛型数组进行了初始化，因此当前data的length属性就是传来的capacity，（或者在后面进行动态扩容或缩容时，data.length是一直不会改变的，改变的只有size） 因此获取顺序表当前的容量将data.length返回即可

4. 顺序表是否为空

    /**
     * 判断数组是否为空
     *
     * @return 数组是否为空
     */
    public boolean isEmpty() {
        return size == 0;
    }

我们知道size代表的是顺序表中的元素个数，因此要判断当前顺序表是否为空仅需要将size是否等于0进行返回即可

5. 在指定索引位置添加元素

    /**
     * 向数组中索引为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++;
    }

当向顺序表中指定索引位置添加元素时要考虑以下几个问题：

• 当前顺序表中是否还有容量？
• 添加的元素索引值是否越界？

对于第一个问题来说，当顺序表已满没有容量时，再进行添加元素时需要进行动态的扩容，resize方法的作用就是对数组进行动态的扩容以及缩容，对于resize方法的实现我们放到后面进行具体的讲解，在这里我们知道如果当前顺序表容量已满，将顺序表容量扩大为当前顺序表容量的二倍

第二个问题的出现情况只有两种，索引小于0或索引超过了当前顺序表中的元素个数时，抛出运行时异常即可

在索引没有问题后，添加元素的过程如下图所示： 

 要先将要添加的索引位置后的所有元素依次向后移动一位，在移动完成后将当前索引位置的元素使用要进行添加的元素对当前位置的元素进行覆盖即可，同时添加完元素后将size++，维护指针变量

6. 在顺序表末尾添加元素

    /**
     * 在数组末尾添加一个元素
     *
     * @param e 要添加的元素
     */
    public void addLast(E e) {
        add(size, e);
    }

在末尾添加元素可以对之前写好的向指定索引位置添加元素的代码进行复用，同时在add方法中进行了校验，因此对于扩容以及索引都问题都无需我们进行考虑，将 索引位置的参数赋值为当前最后一个元素的下一个位置size 后直接调用即可。

7. 在顺序表头部添加元素

    /**
     * 在数组的头部添加元素e
     *
     * @param e 要添加的元素
     */
    public void addFirst(E e) {
        add(0, e);
    }

在顺序表的头部添加元素也是同样的道理，对指定索引位置插入元素进行复用即可，在此不进行赘述。

8. 获取指定索引位置的元素

    /**
     * 获取索引为index位置的元素
     *
     * @param index 索引位置
     * @return 索引为index位置的元素
     */
    public E get(int index) {
        if (index < 0 || index >= size) {
            throw new ArrayIndexOutOfBoundsException();
        }
        return data[index];
    }

获取指定索引位置的元素与之前在指定索引位置插入元素的思路大体一致，但是要更简单一些，无需考虑顺序表扩容以及缩容的问题，仅需要考虑传入的索引值是否合法，如果传入的索引值合法则直接将对应位置的元素进行返回即可。

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;
    }

在之前向顺序表中添加元素以及删除顺序表中的元素都涉及到了扩容以及缩容的过程，其实对于扩容以及缩容来说区别只体现在了传递来的参数与原数组容量大小的差别，扩容与缩容的思路都是声明一个新的数组，初始容量的大小为传递来的参数，接着遍历原来的数组，将每一个元素依次填充到新的数组中，之后再将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));
    }

}