Java中ArrayList與順序表的定義與實現方法

2022-07-26 14:02:33

1、線性表

定義

線性表是最基本、最簡單、也是最常用的一種資料結構。線性表（linear list）是資料結構的一種，一個線性表是n個具有相同特性的資料元素的有限序列。

常見的線性表：順序表、連結串列、棧、佇列...

線性表在邏輯上是線性結構，也就說是連續的一條直線。但是在物理結構上並不一定是連續的，線性表在物理上儲存時，通常以陣列和鏈式結構的形式儲存。

特徵

集合中必存在唯一的一個“第一元素”。
集合中必存在唯一的一個 “最後元素” 。
除最後一個元素之外，均有唯一的後繼(後件)。
除第一個元素之外，均有唯一的前驅(前件)。

2、順序表

定義

順序表是用一段實體地址連續的儲存單元依次儲存資料元素的線性結構，一般情況下采用陣列儲存。在陣列上完成資料的增刪查改。

實現

首先我們需要建立一個陣列來存放資料。

備註：因為我為了方便就先建立的整形陣列，為了能更好的適應各種型別，大家可以建立泛型的陣列，我這裡就沒寫了。

接下來就是對順序表的各種操作。例如：基本的CURD，列印順序表，獲取順序表長度，清空順序表等等。

列印陣列

因為是陣列，所以直接遍歷陣列列印就好了

新增元素

增加元素的時候需要考慮到陣列是否滿狀態的問題，所以我們需要判斷，要死陣列空間已滿，我們還需要進行擴容。另外，我們還需要判斷在這個pos位置是否合法。

判斷空間是否已滿方法

這裡我們簡化程式碼為：

如果要擴容的話，在擴容完成之後，因為順序表是連續的結構，所以在pos位置新增元素的話，那麼pos位置之後的元素就要依次往後挪。這樣才能把元素新增進去。

注意：在擴容之後我們需要更改CAPACITY和usedSize的大小。

判斷是否包含某個元素

在這我們需要考慮到此時陣列是否為空的情況。

之後還是直接遍歷陣列的操作。

查詢元素

在這裡也需要一次判空操作。

獲取pos位置的元素

這裡可能會出現陣列為空的情況和pos不合法的情況，所以需要判斷。

我這裡是手動丟擲的異常，沒有另外寫了。

更改pos位置的值

刪除操作

刪除某個位置上的元素，這裡是直接從這個元素開始，讓其後面的元素覆蓋掉他前一個元素，以達到刪除的目的。

獲取順序表長度

清空順序表

後面這幾個操作比較簡單就不多敘述了。

3、ArrayList

簡介：

在集合框架中，ArrayList是一個普通的類，實現了List介面，具體框架圖如下：

[說明]

ArrayList實現了RandomAccess介面，表明ArrayList支援隨機存取。
ArrayList實現了Cloneable介面，表明ArrayList是可以clone的。
ArrayList實現了Serializable介面，表明ArrayList是支援序列化的。
和Vector不同，ArrayList不是執行緒安全的，在單執行緒下可以使用，在多執行緒中可以選擇Vector或者CopyOnWriteArrayList。
ArrayList底層是一段連續的空間，並且可以動態擴容，是一個動態型別的順序表。

使用

 public static void main(String[] args) {
        // ArrayList建立，推薦寫法
        // 構造一個空的列表
        List<Integer> list1 = new ArrayList<>();
 
        // 構造一個具有10個容量的列表
        List<Integer> list2 = new ArrayList<>(10);
        list2.add(1);
        list2.add(2);
        list2.add(3);
 
        // list2.add("hello"); // 編譯失敗，List<Integer>已經限定了，list2中只能儲存整形元素
        // list3構造好之後，與list中的元素一致
        ArrayList<Integer> list3 = new ArrayList<>(list2);
 
        // 避免省略型別，否則：任意型別的元素都可以存放，使用時將是一場災難
        List list4 = new ArrayList();
        list4.add("111");
        list4.add(100);
    }

一些常見方法

方法	解釋
boolean add(E e)	尾插e
void add(int index, E element)	將 e 插入到 index 位置
boolean addAll(Collection<? extends E> c)	將集合 c 中的元素尾插到該集合中
E remove(int index)	刪除 index 位置元素並返回
boolean remove(Object o)	刪除遇到的第一個 o
E get(int index)	獲取下標 index 位置元素
E set(int index, E element)	將下標 index 位置元素設定為 element
void clear()	清空順序表
boolean contains(Object o)	判斷 o 是否線上性表中
int indexOf(Object o)	返回第一個 o 所在下標
int lastIndexOf(Object o)	返回最後一個 o 的下標
List< E > subList(int fromIndex, int toIndex)	擷取部分 list

ArrayList的遍歷

迴圈遍歷

foreach遍歷

迭代器

        System.out.println("======迭代器1=========");
 
        ElementObservableListDecorator<Object> list;
        Iterator<String> it =  list.iterator();
        while (it.hasNext()) {
            System.out.println(it.next());
        }
        System.out.println("======迭代器2=========");
        ListIterator<String> it2 =  list.listIterator();
        while (it2.hasNext()) {
            System.out.println(it2.next());
        }

順序表和陣列的區別：

上面說，順序表的底層可以理解為一個陣列，但是相比於陣列，更加的高階。

順序表可以自己擴容；

順序表嚴格區分陣列容量和元素的個數。

所以陣列其實就是一種不完備的順序表。

順序表中的注意點：

我們需要區分順序表中的兩個概念：容量（capacity）和元素個數（size）。
容量可以理解為陣列的大小（長度），元素個數是size中記錄的有效元素個數。
順序表中，資料的儲存是需要連續的，不可以元素和元素之間存在“空隙”，當進行插入、刪除等操作時，操作完成後，也要保證順序表的連續。

總結

到此這篇關於Java中ArrayList與順序表的定義與實現的文章就介紹到這了,更多相關Java ArrayList與順序表內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！