1、線性表

定義

線性表是最基本、最簡(jiǎn)單、也是最常用的一種數(shù)據(jù)結(jié)構(gòu)。線性表（linear list）是數(shù)據(jù)結(jié)構(gòu)的一種，一個(gè)線性表是n個(gè)具有相同特性的數(shù)據(jù)元素的有限序列。

常見的線性表：順序表、鏈表、棧、隊(duì)列...

線性表在邏輯上是線性結(jié)構(gòu)，也就說(shuō)是連續(xù)的一條直線。但是在物理結(jié)構(gòu)上并不一定是連續(xù)的，線性表在物理上存儲(chǔ)時(shí)，通常以數(shù)組和鏈?zhǔn)浇Y(jié)構(gòu)的形式存儲(chǔ)。

特征

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

2、順序表

定義

順序表是用一段物理地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)數(shù)據(jù)元素的線性結(jié)構(gòu)，一般情況下采用數(shù)組存儲(chǔ)。在數(shù)組上完成數(shù)據(jù)的增刪查改。

實(shí)現(xiàn)

首先我們需要?jiǎng)?chuàng)建一個(gè)數(shù)組來(lái)存放數(shù)據(jù)。

備注：因?yàn)槲覟榱朔奖憔拖葎?chuàng)建的整形數(shù)組，為了能更好的適應(yīng)各種類型，大家可以創(chuàng)建泛型的數(shù)組，我這里就沒(méi)寫了。

接下來(lái)就是對(duì)順序表的各種操作。例如：基本的CURD，打印順序表，獲取順序表長(zhǎng)度，清空順序表等等。

打印數(shù)組

因?yàn)槭菙?shù)組，所以直接遍歷數(shù)組打印就好了

新增元素

增加元素的時(shí)候需要考慮到數(shù)組是否滿狀態(tài)的問(wèn)題，所以我們需要判斷，要死數(shù)組空間已滿，我們還需要進(jìn)行擴(kuò)容。另外，我們還需要判斷在這個(gè)pos位置是否合法。

判斷空間是否已滿方法

這里我們簡(jiǎn)化代碼為：

如果要擴(kuò)容的話，在擴(kuò)容完成之后，因?yàn)轫樞虮硎沁B續(xù)的結(jié)構(gòu)，所以在pos位置新增元素的話，那么pos位置之后的元素就要依次往后挪。這樣才能把元素新增進(jìn)去。

 注意：在擴(kuò)容之后我們需要更改CAPACITY和usedSize的大小。

判斷是否包含某個(gè)元素

在這我們需要考慮到此時(shí)數(shù)組是否為空的情況。

之后還是直接遍歷數(shù)組的操作。

查找元素

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

獲取pos位置的元素

這里可能會(huì)出現(xiàn)數(shù)組為空的情況和pos不合法的情況，所以需要判斷。

我這里是手動(dòng)拋出的異常，沒(méi)有另外寫了。

更改pos位置的值

刪除操作

刪除某個(gè)位置上的元素，這里是直接從這個(gè)元素開始，讓其后面的元素覆蓋掉他前一個(gè)元素，以達(dá)到刪除的目的。

獲取順序表長(zhǎng)度

清空順序表

后面這幾個(gè)操作比較簡(jiǎn)單就不多敘述了。

3、ArrayList

簡(jiǎn)介：

在集合框架中，ArrayList是一個(gè)普通的類，實(shí)現(xiàn)了List接口，具體框架圖如下：

[說(shuō)明]

1. ArrayList實(shí)現(xiàn)了RandomAccess接口，表明ArrayList支持隨機(jī)訪問(wèn)。
2. ArrayList實(shí)現(xiàn)了Cloneable接口，表明ArrayList是可以clone的。
3. ArrayList實(shí)現(xiàn)了Serializable接口，表明ArrayList是支持序列化的。
4. 和Vector不同，ArrayList不是線程安全的，在單線程下可以使用，在多線程中可以選擇Vector或者CopyOnWriteArrayList。
5.  ArrayList底層是一段連續(xù)的空間，并且可以動(dòng)態(tài)擴(kuò)容，是一個(gè)動(dòng)態(tài)類型的順序表。

使用

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

 一些常見方法

 ArrayList的遍歷

循環(huán)遍歷

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

順序表和數(shù)組的區(qū)別：

上面說(shuō)，順序表的底層可以理解為一個(gè)數(shù)組，但是相比于數(shù)組，更加的高級(jí)。

順序表可以自己擴(kuò)容；

順序表嚴(yán)格區(qū)分?jǐn)?shù)組容量和元素的個(gè)數(shù)。

所以數(shù)組其實(shí)就是一種不完備的順序表。

順序表中的注意點(diǎn)：

• 我們需要區(qū)分順序表中的兩個(gè)概念：容量（capacity）和元素個(gè)數(shù)（size）。
• 容量可以理解為數(shù)組的大小（長(zhǎng)度），元素個(gè)數(shù)是size中記錄的有效元素個(gè)數(shù)。
• 順序表中，數(shù)據(jù)的存儲(chǔ)是需要連續(xù)的，不可以元素和元素之間存在“空隙”，當(dāng)進(jìn)行插入、刪除等操作時(shí)，操作完成后，也要保證順序表的連續(xù)。

總結(jié)

到此這篇關(guān)于Java中ArrayList與順序表的定義與實(shí)現(xiàn)的文章就介紹到這了,更多相關(guān)Java ArrayList與順序表內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論