Sequential representation and implementation method of Java linear table

1. What is a sequence table?

A sequential table is a linear table saved in the form of an array in computer memory. The sequential storage of a linear table means thatuses a set of storage units with consecutive addresses to store each element in the linear table in sequence, so that Logically adjacent data elements in a linear table are stored in adjacent physical storage units, that is, the logical adjacent relationship between data elements is reflected through the adjacent relationship of physical storage of data elements, using the order A linear list of storage structures is often called a sequential list. A sequence table stores the nodes in the table sequentially in a set of storage units with consecutive addresses in the computer memory .

2. Implementation of the sequence table

As you can see from the definition of the sequence table, the sequence table is a

group of storage units with consecutive addresses, which is essentially a Added some basic operation functions to the array

The functions to be implemented in this article are:

• Get the number of elements in the sequence table

• Get the current capacity of the sequence table

• Whether the sequence table is empty

• At the specified index position Add elements

• Add elements to the end of the sequence list

• Add elements to the head of the sequence list

• Get the element at the specified index position

• Get the first element of the sequence table

• Get the last element of the sequence table

• Modify the element at the specified index position

• Determine whether the sequence table contains the specified element

• Get the specified element in the sequence table Index

• Delete the element at the specified index position

• Delete and return the first element of the sequence table

• Delete and return the last element of the sequence table

• Delete the specified element in the sequence table

• Perform dynamic expansion and expansion of the sequence table Shrinking

1. Preparation

Implementation ToolVersionIntelliJ IDEA2021.3JDK1.8

Create a new ordinary Java project in IntelliJ IDEA

After creating a new Java project , we create our own sequence table class. Here I name the current class Array, and implement generics here. At the same time, the Array class needs to have two member attributes:

• Array to store data:data, type is generic array

• currently The number of elements in the sequence table : size, type is int

The access rights of both member attributes should be private, users cannot modify it directly and can only obtain it through the corresponding getter method. In the member attributes, we will store the number of elements in the array and sequence table of the data. is just declared, but not initialized, so the == initialization process needs to be carried out in the constructor==

• Construction with parameters: When performing construction with parameters, we only need to specify that the incoming parameter is a data of type intcapacity represents the initial capacity of the sequence table, so just initialize the generic array for data. At the same time, there are no elements in the current sequence table, which means the initial value of size is 0, which means the number of elements in the sequence table.

• No-parameter construction: When the user does not specify the initial capacity of the sequence table, we can customize the initial capacity to 10, just pass this( 10) Just make a call with parameter construction.

Note: You cannot directly initialize a generic array in Java. You need to declare an array of type Object first and then force the type through Conversion method converts an array of type Object into a generic array

package net.csdn.array;
/**
 * @author zhangrongkang
 * @date 2022/6/26
 */
public class Array {
	/**
	 * 存放数据的数组
	 */
	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);
    }
}

Reason for using generics: After using generics, the current sequence can be tabled Objects are stored in the object. If you do not use generics, you can only use data of your own specified type, and the scalability is not strong. Therefore, after using generics, you can extend the use of the current sequence table to all class objects , and you only need to specify the corresponding object when creating it.

2. Get the number of elements in the sequence table

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

For getting the number of elements in the current sequence table, because the initial member variable we defined size represents The meaning is The number of elements in the current sequence table, but the essence of the size variable is The pointer of the current sequence table, pointing to the next position of the last element in the sequence table (The index of the element starts from 0, and the index value of the last element is 1 less than the element value). It cannot be modified directly, so to get the size element, you need to pass the getter Method

Similarly, to obtain the number of elements in the sequence table, you only need to return size

3. Get the current capacity of the sequence table

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

When declaring the sequence table, the initial capacity capacity passed by the user or the default has been used as the size of the array to initialize the data generic array, so The length attribute of the current data is the passed capacity, (or when dynamically expanding or shrinking the capacity later, data.length It will never change, only size changes) Therefore, to obtain the current capacity of the sequence table, just return data.length

4. Is the sequence table Empty

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

We know that size represents the number of elements in the sequence table, so to determine whether the current sequence table is empty, you only need to check whether size is equal to 0 Just return it

5. Add an element at the specified index position

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

When adding elements to the specified index position in the sequence table, you should consider the following issues:

• Is there still capacity in the current sequence table?

• #Is the index value of the added element out of bounds?

Regarding the first question, when the sequence table is full and has no capacity, dynamic expansion is required when adding elements, resize The function of the method is to dynamically expand and shrink the array . We will explain the implementation of the resize method in detail later. Here we know that if the current sequence table capacity has been Full, expand the capacity of the sequence table to twice the capacity of the current sequence table

There are only two situations for the second problem, The index is less than 0 or the index exceeds the number of elements in the current sequence table , just throw a runtime exception

After there is no problem with the index, the process of adding elements is as shown below:

 要先将要添加的索引位置后的所有元素依次向后移动一位，在移动完成后将当前索引位置的元素使用要进行添加的元素对当前位置的元素进行覆盖即可，同时添加完元素后将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 {
    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 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));
    }

}

The above is the detailed content of Sequential representation and implementation method of Java linear table. For more information, please follow other related articles on the PHP Chinese website!