Java線性表的順序表示及實現方法

本篇內容介紹了“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));
    }

}

“Java線性表的順序表示及實現方法”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業相關的知識可以關注億速云網站，小編將為大家輸出更多高質量的實用文章！