我們不過是普通人，只不過在彼此眼中閃閃發(fā)光

目錄

1、什么是順序表？

2、模擬實(shí)現(xiàn)ArrayList

2.1 模擬實(shí)現(xiàn)前的約定

2.2?構(gòu)造方法

2.3 add方法

2.4 contains 方法

2.5 indexOf 方法

2.6 get 方法

2.7 set 方法

2.8 remove 方法

2.9 getSize 和 clear 方法

3、ArrayList 的學(xué)習(xí)

3.1 ArrayList的成員屬性

3.2 ArrayList的構(gòu)造方法

3.2.1 構(gòu)造方法1

3.2.2 構(gòu)造方法2

3.2.3 構(gòu)造方法3?

3.3 ArrayList 的 add 方法

3.4 ArrayList的常用方法

4、ArrayList的使用

4.1 ArrayList的遍歷

4.2 撲克牌例子

4.2.1 準(zhǔn)備工作

4.2.2 買一副牌邏輯

4.2.3 洗牌邏輯

4.2.3 發(fā)牌邏輯(重點(diǎn))?

4.2.4 測(cè)試整體邏輯

1、什么是順序表？

這里運(yùn)用博主之前寫C語言實(shí)現(xiàn)順序表中引用的一句話：

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

順序表又可以分為動(dòng)態(tài)存儲(chǔ)的順序表和靜態(tài)存儲(chǔ)的順序表，基本上現(xiàn)在不會(huì)使用靜態(tài)的，這里就不介紹靜態(tài)的了，所謂動(dòng)態(tài)，就是當(dāng)順序表滿的時(shí)候會(huì)自動(dòng)擴(kuò)容！我們接著往下看：

在Java中官方提供了ArrayList類，底層也是用數(shù)組實(shí)現(xiàn)的順序表。

那么今天我們不急著去解讀ArrayList類，而是先憑借我們之前的學(xué)習(xí)面向?qū)ο蟮闹R(shí)，以及C語言數(shù)據(jù)結(jié)構(gòu)階段順序表的實(shí)現(xiàn)，嘗試著模擬實(shí)現(xiàn) ArrayList類，當(dāng)然，Java提供的是一個(gè)泛型類，可以存放任意指定類型數(shù)據(jù)(基本數(shù)據(jù)類型除外)?，我們就不模擬的那么復(fù)雜，能基本實(shí)現(xiàn)一些常見方法就行，等模擬實(shí)現(xiàn)之后，我們?cè)偃ラ喿x源碼。

2、模擬實(shí)現(xiàn)ArrayList

2.1 模擬實(shí)現(xiàn)前的約定

我們約定 elem 是存放整型數(shù)據(jù)的數(shù)組，size 表示數(shù)組當(dāng)前有效元素個(gè)數(shù)，DEFAULT_CAPACITY 容量值，那么就可以寫出這樣的代碼：

public class MyArrayList {
    private int elem[]; //存放數(shù)據(jù)
    private int size; //數(shù)組有效元素個(gè)數(shù)
    private static final int DEFAULT_CAPACITY = 10; //約定容量
}

同時(shí)我們還要實(shí)現(xiàn)以下幾個(gè)常用的方法：

public void add(int data);// 新增元素,默認(rèn)在數(shù)組最后新增

public void add(int pos, int data);// 在 pos 位置新增元素

public boolean contains(int toFind);// 判定是否包含某個(gè)元素

public int indexOf(int toFind);// 查找某個(gè)元素對(duì)應(yīng)的位置

public int get(int pos);// 獲取 pos 位置的元素

public void set(int pos, int value);// 給 pos 位置的元素設(shè)為 value

public void remove(int toRemove);//刪除第一次出現(xiàn)的關(guān)鍵字key

public int getSize()// 獲取順序表長(zhǎng)度

public void clear();// 清空順序表

其實(shí)還有很多方法，比如頭插，尾刪，但這些你實(shí)現(xiàn)了上面的，相信你自己也能解決的，現(xiàn)在我們就擼起袖子寫代碼吧：

2.2?構(gòu)造方法

這里我們想一想，?如何設(shè)置我們的構(gòu)造方法呢？如果用戶想一開始的時(shí)候就自定義大小呢？如果不想自定義我們是不是要設(shè)置一個(gè)默認(rèn)的大小？那么就可以寫出下面兩個(gè)構(gòu)造方法：

// 無參構(gòu)造方法，默認(rèn)將數(shù)組容量設(shè)置成DEFAULT_CAPACITY
public MyArrayList() {
    this.elem = new int[DEFAULT_CAPACITY];
}
// 帶參數(shù)構(gòu)造方法，將數(shù)組容量設(shè)置成用戶指定的容量
public MyArrayList(int capacity) throws IllegalCapacityException {
    // 檢查指定容量是否非法
    if (capacity <= 0) {
        throw new IllegalCapacityException("設(shè)置非法容量");
    }
    this.elem = new int[capacity];
}

代碼中的異常是我自定義的一個(gè)運(yùn)行時(shí)異常，如果對(duì)異常還不了解的，可以看博主之前寫的JavaSE系列文章，這里我就不再談異常了。

2.3 add方法

private void capacity() {
    //將原數(shù)組擴(kuò)大到2倍，利用Arrays.copyOf
    int len = getSize();
    this.elem = Arrays.copyOf(this.elem, len * 2);
}

// 新增元素,默認(rèn)在數(shù)組最后新增
public void add(int data) {
    // 1.空間是否滿了，滿了則需要擴(kuò)容
    if (getSize() == this.elem.length) {
        capacity(); //擴(kuò)容
    }
    // 2.往數(shù)組最后位置新增元素
    // 3.有效數(shù)據(jù)自增1
    this.elem[this.size++] = data;
}

在寫這個(gè)方法的時(shí)候，我們要注意數(shù)組如果滿了就要增容，而增容這里我們用到 copyOf 方法，每次擴(kuò)容2倍。

add方法重載，在pos位置新增：

// 在 pos 位置新增元素
public void add(int pos, int data) throws IllegalPosException {
    //1.檢查pos下標(biāo)的合法性(順序表指定插入前面必須有元素，不能隔著插入)
    if (pos > getSize() || pos < 0) {
        throw new IllegalPosException("指定插入pos位置不合法");
    }
    //2.判斷數(shù)組是否需要增容
    if (getSize() == this.elem.length) {
        capacity(); //擴(kuò)容
    }
    //3.從pos位置的元素都往后移
    for (int i = this.size - 1; i >= pos; i--) {
        this.elem[i + 1] = this.elem[i];
    }
    //4.pos位置放入數(shù)據(jù)，size自增
    this.elem[pos] = data;
    this.size++;
}

這里圖就不給大家畫了，在博主數(shù)據(jù)結(jié)構(gòu)C語言版本的時(shí)候已經(jīng)有很詳細(xì)了圖解了，感興趣的可以去看一看，大同小異。

這里我們直接來說第一個(gè)要注意的點(diǎn)，因?yàn)槭琼樞虮?，插入元素不能隔著元素插入，也就是你插入的位置前面必須要有元素！也就得?pos 必須小于等于我們的有效元素個(gè)數(shù)！

而且 pos 的位置不能小于0！

接著就是判斷擴(kuò)容和中間插入需要挪動(dòng)后面的元素了，過程很簡(jiǎn)單，這里就不多談了。

2.4 contains 方法

// 判定是否包含某個(gè)元素
public boolean contains(int toFind) {
    //1.遍歷數(shù)組
    for (int i = 0; i < getSize(); i++) {
        if (this.elem[i] == toFind) {
            return true; //2.找到返回true
        }
    }
    //3.找不到返回false
    return false;
}

這個(gè)方法就太簡(jiǎn)單了，看我寫的注釋就能看懂！

2.5 indexOf 方法

// 查找某個(gè)元素對(duì)應(yīng)的位置
public int indexOf(int toFind) {
    //1.遍歷數(shù)組
    for (int i = 0; i < getSize(); i++) {
        if (this.elem[i] == toFind) {
            return i; //2.找到返回下標(biāo)
        }
    }
    //3.找不到返回-1
    return -1;
}

這個(gè)方法跟上面contains方法大同小異，無需多言！

2.6 get 方法

// 獲取 pos 位置的元素
public int get(int pos) {
    //1.判斷pos位置是否合法
    if (pos > getSize() || pos < 0) {
        throw new IllegalPosException("獲取pos位置不合法");
    }
    //2.返回pos位置值
    return this.elem[pos];
}

這個(gè)方法需要注意的點(diǎn)就是判斷pos下標(biāo)位置的合法性，注意這一點(diǎn)就ok了！

2.7 set 方法

// 給 pos 位置的元素設(shè)為 value
public void set(int pos, int value) {
    //1.判斷pos位置是否合法
    if (pos > getSize() || pos < 0) {
        throw new IllegalPosException("pos位置不合法");
    }
    //2.設(shè)置值
    this.elem[pos] = value;
}

好像跟上面的 get 方法沒什么區(qū)別唉，多簡(jiǎn)單就不用我多說了吧！

2.8 remove 方法

//刪除第一次出現(xiàn)的關(guān)鍵字key
public void remove(int toRemove) {
    //1.獲取第一次key出現(xiàn)的位置
    int pos = indexOf(toRemove);
    if (pos == -1) {
        return;
    }
    //2.從pos位置的元素都往前覆蓋
    for (int i = pos + 1; i < getSize(); i++) {
        this.elem[i - 1] = this.elem[i];
    }
    //3.有效數(shù)據(jù)減一(如果是引用類型需要置null)
    this.size--;
}

這個(gè)方法我們就可以復(fù)用我們之前寫的 indexOf 方法了，不用重新寫查找邏輯了，接著把后面的元素覆蓋掉 pos 下標(biāo)的元素就可以了！記得別忘記有效數(shù)據(jù)減一哦！

2.9 getSize 和 clear 方法

// 獲取順序表長(zhǎng)度
public int getSize() {
    return this.size;
}

// 清空順序表
public void clear() {
    this.size = 0;
}

這兩個(gè)就簡(jiǎn)單了吧，但是要注意一點(diǎn)，如果你的順序表放的是引用類型，需要置null，方法已經(jīng)實(shí)現(xiàn)的差不多了，感興趣的下來結(jié)合代碼畫圖寫一寫吧！

3、ArrayList 的學(xué)習(xí)

3.1 ArrayList的成員屬性

• ArrayList實(shí)現(xiàn)了RandomAccess接口，表明ArrayList支持隨機(jī)訪問
• ArrayList實(shí)現(xiàn)了Cloneable接口，表明ArrayList是可以clone的
• ArrayList實(shí)現(xiàn)了Serializable接口，表明ArrayList是支持序列化的?

這就是類定義的前部分，這里還是比較復(fù)雜的，會(huì)隨著我們學(xué)習(xí)的深入，逐步學(xué)習(xí)到。

接下來我們來看ArrayList的幾個(gè)成員變量：

3.2 ArrayList的構(gòu)造方法

3.2.1 構(gòu)造方法1

當(dāng)前是一個(gè)帶參數(shù)的構(gòu)造方法，很好理解，根據(jù)傳遞的參數(shù)開辟大小，如果參數(shù)是等于0，就直接把?EMPTY_ELEMENTDATA 共享空數(shù)組賦值給存放數(shù)據(jù)的數(shù)組中，?如果是給定一個(gè)負(fù)數(shù)，顯然是錯(cuò)誤的，也即直接拋出異常！

3.2.2 構(gòu)造方法2

奇怪，這個(gè)無參構(gòu)造方法居然也是給了一個(gè)空數(shù)組，也就是沒有分配數(shù)組內(nèi)存，那到底是怎么把數(shù)據(jù)放進(jìn)去的呢？別急，隨著后面的講解，你會(huì)解開這個(gè)謎題。

3.2.3 構(gòu)造方法3?

按照集合迭代器返回元素的順序，構(gòu)造一個(gè)包含指定集合元素的列表，如果是屬于同類型，就直接放入到存放數(shù)據(jù)的數(shù)組中，如果不是同類型，則利用 copyOf 拷貝指定的集合，如果指定集合長(zhǎng)度為0，則把 EMPTY_ELEMENTDATA 共享空數(shù)組賦值給存放數(shù)據(jù)的數(shù)組中。

這個(gè)地方如果你不是很理解，沒關(guān)系，因?yàn)楝F(xiàn)在還沒接觸迭代器，隨著學(xué)習(xí)的深入就會(huì)接觸到。

3.3 ArrayList 的 add 方法

別小看這幾行代碼，跟我們自己模擬實(shí)現(xiàn)的還是有區(qū)別的，真正有內(nèi)涵的代碼其實(shí)在 ensureCapacityInternal 這個(gè)方法中，那么現(xiàn)在，我們就一步步去解開他的面紗：

有了上面的圖解我們不難看出，真正的擴(kuò)容是在 add 方法中實(shí)現(xiàn)的，所以在實(shí)例化 ArrayList 的時(shí)候，是不會(huì)默認(rèn)給你開辟空間的。所以 ArrayList 默認(rèn)容量是在 add 方法調(diào)用后，才會(huì)分配空間。而且在真正擴(kuò)容之前會(huì)檢測(cè)是否能擴(kuò)容成功，防止太大導(dǎo)致擴(kuò)容失敗。

3.4 ArrayList的常用方法

還有其他方法需要使用的話，就可以去查閱Java的幫助文檔，到了數(shù)據(jù)結(jié)構(gòu)階段，就要嘗試著自己看源碼，看文檔了，培養(yǎng)自主學(xué)習(xí)的能力！

4、ArrayList的使用

4.1 ArrayList的遍歷

對(duì)于順序表的遍歷，我們可以通過 for 循環(huán)，for-each，以及迭代器的方法遍歷：

public class TestArrayList {
    public static void main(String[] args) {
        ArrayList<Integer> arrayList = new ArrayList<>();
        arrayList.add(1);
        arrayList.add(2);
        arrayList.add(3);
        // 通過for循環(huán)遍歷ArrayList
        for (int i = 0; i < arrayList.size(); i++) {
            System.out.print(arrayList.get(i) + " ");
        }
        // 通過for-each循環(huán)遍歷ArrayList
        for (Integer integer : arrayList) {
            System.out.print(integer + " ");
        }
        // 通過迭代器遍歷ArrayList(了解即可)
        Iterator<Integer> it = arrayList.iterator();
        while (it.hasNext()) {
            System.out.print(it.next() + " ");
        }
    }
}

4.2 撲克牌例子

這里我們要運(yùn)用我們上面學(xué)的知識(shí)寫一個(gè)撲克牌的例子：

4.2.1 準(zhǔn)備工作

首先我們肯定有一個(gè)類把我們的一張撲克抽象出來，撲克有花色和點(diǎn)數(shù)，那么我們就可以這樣寫：

public class Poker {
    private String decor;
    private int number;

    public Poker(String decor, int number) {
        this.decor = decor;
        this.number = number;
    }

    @Override
    public String toString() {
        return this.decor + this.number;
    }
}

那么我們還得需要表示多張撲克牌，同時(shí)也需要一個(gè)存放撲克牌的容器，這里我們選用 ArrayList，同時(shí)還需要一個(gè)數(shù)組來存儲(chǔ)對(duì)應(yīng)花色。

public class Pokers {
    private final String[] decor = { "?", "?", "?", "?" };
    private List<Poker> pokerList = new ArrayList<>();

    // 獲取花色
    public String get(int index) {
        return decor[index];
    }
}

這里為什么可以使用 List 接收 ArrayList 的對(duì)象呢？因?yàn)?List 是一個(gè)接口，ArrayList 實(shí)現(xiàn)了這個(gè)接口，所以這里就實(shí)現(xiàn)了向上轉(zhuǎn)型。

4.2.2 買一副牌邏輯

準(zhǔn)備工作都做好了，我們要實(shí)現(xiàn)買一副牌的邏輯，除了大小王一共有52張牌，我們這里用11 12 13 代替 J Q K，每張牌一共有四種花色，也就是定義一個(gè)雙層循環(huán)遍歷放入到我們的容器中即可，最后在放入我們的大小王，這里不涉及太復(fù)雜，就定大小王的點(diǎn)數(shù)為0！

4.2.3 洗牌邏輯

買一副撲克牌的邏輯寫好了，那么現(xiàn)在就應(yīng)該洗牌了，那么洗牌應(yīng)該怎么去實(shí)現(xiàn)他呢？

我們可以運(yùn)用 Random 類中產(chǎn)生隨機(jī)數(shù)方法，但是產(chǎn)生了隨機(jī)數(shù)，如何打亂牌呢？

如果從最后一個(gè)開始洗，即 last 位置開始，產(chǎn)生 last 的隨機(jī)數(shù)是 [0~last) ，不包含last，所以我們可以從后往前洗牌，每次把最后一張牌與產(chǎn)生的隨機(jī)數(shù)位置的牌交換即可。(不考慮業(yè)務(wù)性)

4.2.3 發(fā)牌邏輯(重點(diǎn))?

如何去模擬實(shí)現(xiàn)發(fā)牌呢？一共有三個(gè)人打牌，每個(gè)人輪流摸牌，如果是54張牌要摸18輪，摸到的牌是不是也應(yīng)該放到對(duì)應(yīng)的人手上，站在編程的角度，應(yīng)該摸到的牌應(yīng)該放在對(duì)應(yīng)那個(gè)人的容器中。

如何表示我們上述的設(shè)想呢？假設(shè)我們有一個(gè)順序表，一共三個(gè)元素，分別代表三個(gè)人，而每個(gè)元素里面又放著一個(gè)順序表，而這個(gè)順序表對(duì)應(yīng)著這個(gè)人摸到的牌！我們就能畫出這樣的圖：

通過圖我們想一想，這個(gè)結(jié)構(gòu)不就是有一個(gè)ArrayList嗎？然后ArrayList里面放的元素類型還是ArrayList，我們要傳什么實(shí)參類型進(jìn)去呢？當(dāng)然是Poker了啊，因?yàn)槔锩娴腁rrayList最后是要放撲克牌的！于是我們就能寫出這樣的代碼：

這里我們要說一點(diǎn)，發(fā)牌的時(shí)候，每次都是刪除第一張牌，并且把刪除的第一張牌增加到對(duì)應(yīng)用戶的手牌中，這樣也就形成了摸牌邏輯，最后把牌打印出來就好了！

4.2.4 測(cè)試整體邏輯

最終我們?cè)趍ain方法中調(diào)用如上的 testGame方法實(shí)現(xiàn)的是這樣一個(gè)效果：

到這就實(shí)現(xiàn)的差不多啦！買牌，洗牌，發(fā)牌邏輯都沒問題，這個(gè)小練習(xí)，不涉及業(yè)務(wù)，我們主要是把學(xué)習(xí)的順序表知識(shí)運(yùn)用起來，聽博主一句話，學(xué)數(shù)據(jù)結(jié)構(gòu)，多敲代碼多畫圖！

下期預(yù)告：【Java 數(shù)據(jù)結(jié)構(gòu)】單鏈表與OJ題文章來源地址http://www.zghlxwxcb.cn/news/detail-828834.html

到了這里，關(guān)于【Java 數(shù)據(jù)結(jié)構(gòu)】順序表的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！