Java中ArrayList與順序表怎麼定義與實現

1、線性表格

定義

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

常見的線性表：順序表、鍊錶、堆疊、佇列...

線性表在邏輯上是線性結構，也就說是連續的一條直線。線性表在實體上的儲存形式通常是陣列或鍊錶結構，但不一定是連續的。

特徵

• 集合中必存在唯一的一個「第一個元素」。

• 集合中必存在唯一的一個 「最後元素」 。

• 除最後一個元素之外，均有唯一的後繼(後件)。

• 除第一個元素之外，均有唯一的前驅(前件)。

2、順序表

定義

通常是用陣列形式儲存的線性結構叫做順序表，它將資料元素依序儲存在一片物理位址連續的儲存單元中。在數組上完成資料的增刪查改。

實作

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

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

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

列印數組

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

新增元素

在增加元素時，考慮數組是否已滿狀態是必要的，因此我們需要進行判斷，若數組空間已滿，則需要進行擴容。另外，我們還需要判斷在這個pos位置是否合法。

判斷空間是否已滿方法

這裡我們簡化程式碼為：

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

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

判斷是否包含某個元素

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

之後還是直接遍歷陣列的運算。

尋找元素

在這裡也需要一次判空運算。

取得pos位置的元素

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

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

更改pos位置的值

#刪除動作

刪除某個位置上的元素，可直接讓其後面的元素覆蓋掉它，實現刪除。

取得順序表長度

#已清除順序表

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

3、ArrayList

簡介：

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

[說明]

1. ArrayList實作了RandomAccess接口，表示ArrayList支援隨機存取。

2. ArrayList實作了Cloneable接口，顯示ArrayList是可以clone的。

3. ArrayList實作了Serializable接口，表示ArrayList是支援序列化的。

4. 和Vector不同，ArrayList不是線程安全的，在單線程下可以使用，在多線程中可以選擇Vector或CopyOnWriteArrayList。

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

 一些常見方法

## E set(int index, E element)將下標index 位置元素設定為elementvoid clear()boolean contains(Object o)int indexOf(Object o)int lastIndexOf(Object o)#List subList(int fromIndex, int toIndex) ArrayList的遍歷

方法	#解釋
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 位置元素
##清空順序表
判斷o 是否在線性表中
傳回第一個o 所在下標
傳回最後一個o 的下標
截取部分list

#循環遍歷

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與順序表怎麼定義與實現的詳細內容。更多資訊請關注PHP中文網其他相關文章！