??????作者：
@小魚不會(huì)騎車
??????專欄：
《java練級(jí)之旅》
??????個(gè)人簡(jiǎn)介：
一名?？拼笠辉谧x的小比特，努力學(xué)習(xí)編程是我唯一的出路??????

介紹線性表

在認(rèn)識(shí)順序表前我們先認(rèn)識(shí)一下線性表：

小魚曾在一本書中看到這么一個(gè)例子他是這樣介紹線性表的：

在一個(gè)幼兒園中，每次放學(xué)時(shí)老師帶領(lǐng)著小朋友們一個(gè)接著一個(gè)從教室出來(lái)，并且他們之間的次序都是一樣的，例如小明排在第4位，則每次放學(xué)時(shí)他都是排在第四位，前面同樣是那個(gè)的小女孩，后面也一直是那個(gè)男孩。

老師是這么解釋的：為了保障小朋友的安全，避免漏掉小朋友，所以在出門前就安排好了他們出門的次序，誰(shuí)誰(shuí)在前，誰(shuí)誰(shuí)在后，當(dāng)這樣養(yǎng)成習(xí)慣時(shí)，如果是有哪個(gè)小朋友沒有到位，則他前面的和后面的小朋友就會(huì)發(fā)現(xiàn)并且報(bào)告給老師，誰(shuí)誰(shuí)不在，老師也可以很快地清點(diǎn)人數(shù)，萬(wàn)一有人走丟，也能在最快時(shí)間知道，及時(shí)去尋找。

通過(guò)上面的例子我們就可以看出：線性表是一個(gè)序列，也可以理解為他們之間的元素是有順序的，并且第一個(gè)元素?zé)o前驅(qū)，最后一個(gè)元素?zé)o后繼，其余元素有且僅有一個(gè)前驅(qū)和后繼，并且如果一個(gè)小朋友的衣服被兩個(gè)或多個(gè)小朋友拉扯，這其實(shí)是在打架！不是有序排隊(duì)。

總結(jié)：

線性表（linear list） 是n個(gè)具有相同特性的數(shù)據(jù)元素的有限序列。
線性表是一種在實(shí)際中廣泛使用的數(shù)據(jù)結(jié)構(gòu)，常見的線性表：順序表、鏈表、棧、隊(duì)列…
線性表在邏輯上是線性結(jié)構(gòu)，也就說(shuō)是連續(xù)的一條直線。但是在物理結(jié)構(gòu)上并不一定是連續(xù)的，線性表在物理上存儲(chǔ)時(shí)，通常以數(shù)組和鏈?zhǔn)浇Y(jié)構(gòu)的形式存儲(chǔ)。

順序表

在簡(jiǎn)單介紹完線性表之后，我們可以將順序表理解為用數(shù)組的形式來(lái)實(shí)現(xiàn)線性表。

那一個(gè)順序表都會(huì)有什么操作呢？舉個(gè)例子：

如果有小朋友排隊(duì)的時(shí)候突然想去廁所，那么當(dāng)他去廁所之后，是不是他后面的同學(xué)都向前移動(dòng)一下，先將這個(gè)空位補(bǔ)上？
對(duì)的！ 大概就是如下圖的過(guò)程

過(guò)了一會(huì)上廁所的小朋友回來(lái)了，是不是剛剛移動(dòng)的小朋友需要集體后移來(lái)給這個(gè)小朋友騰出地方??？
就像下圖：

我們可以將上述的兩個(gè)操作理解為增加和刪除元素，那我們還是不是需要有查找和修改的功能啊？

那么大體的思路我們有了，接下來(lái)就是實(shí)現(xiàn)順序表了！

定義一個(gè)順序表類（Arraylist）

我們這個(gè)順序表用到的是數(shù)組，所以我們就可以在這個(gè)順序表中定義一個(gè)數(shù)組的成員變量，由于順序表中的元素沒有指定是什么類型，那么我們就創(chuàng)建一個(gè)泛型類的順序表，以及一個(gè)泛型數(shù)組！并且我們還需要一個(gè)值來(lái)記錄數(shù)組內(nèi)元素的個(gè)數(shù)，那么為了方便，我們還可以利用構(gòu)造方法初始化我們的數(shù)組大小。

代碼如下：

public class Arraylist<E> {

    public E[] elem;//創(chuàng)建這個(gè)成員變量
    public int usedSize;//0/。記錄長(zhǎng)度
    //默認(rèn)容量
    private static final int DEFAULT_SIZE = 10;

    public Arraylist() {//初始化數(shù)組
        this.elem = (E[]) new Object[DEFAULT_SIZE];
    }

    public Arraylist(int p) {
        this.elem = (E[]) new Object[p];
    }
 }   

我們對(duì)構(gòu)造方法進(jìn)行了重載，如果需要指定數(shù)組大小則可以在實(shí)例化順序表類時(shí)輸入指定的數(shù)組大小，如果沒有指定數(shù)組的大小，我們就將數(shù)組大小默認(rèn)設(shè)置為10個(gè)元素的大??！

那么成員屬性和構(gòu)造方法我們都實(shí)現(xiàn)了，接下來(lái)就是順序表中的增刪查改等方法了！

查找順序表元素（indexOf）

我們查找元素一般時(shí)有兩個(gè)需求。

第一：查找到元素返回元素的下標(biāo)
第二：判斷數(shù)組中有沒有這個(gè)元素，如果有返回true否則返回false。

所以根據(jù)著兩個(gè)需求我們可以寫兩個(gè)方法

第一個(gè):當(dāng)該元素存在時(shí)返回該元素的下標(biāo)

  // 查找某個(gè)元素對(duì)應(yīng)的位置
  //toFind是我們要查找的元素
    public int indexOf(E toFind) {
        for (int i = 0; i < usedSize; i++) {
            if (elem[i].equals(toFind)) {
                return i;
            }
        }
        return -1;
    }

第二個(gè):當(dāng)該元素存在時(shí)返回true否則返回false

 // 判定是否包含某個(gè)元素
    public boolean contains(E toFind) {
        for (int i = 0; i <usedSize ; i++) {
            if (elem[i].equals(toFind)) {
                return true;
            }
        }
        return false;
    }

兩者的區(qū)別其實(shí)就是返回值的不同，其實(shí)實(shí)現(xiàn)起來(lái)是很簡(jiǎn)單的。

遍歷順序表（display）

那我們也可以接著這個(gè)思路再寫一個(gè)打印方法，打印出數(shù)組所有元素的值

遍歷數(shù)組有五種方法，雖然有些不會(huì)經(jīng)常用到，但是小魚還是一一給大家列舉出來(lái)！
①、使用 for 循環(huán)打印

最簡(jiǎn)單的方法，但是需要自己去實(shí)現(xiàn)

  /**
     * 打印順序表:
     * 根據(jù)usedSize判斷即可
     */
    public void display() {
        for (int i = 0; i < usedSize; i++) {
            System.out.print(elem[i]+" ");
        }
        System.out.println();
    }

②、使用 Arrays.toString() 或 Arrays.deepToString()

對(duì)于一維數(shù)組，可以使用Arrays.toString()方法，它支持將任意類型的數(shù)組轉(zhuǎn)換為字符串
一維數(shù)組用 Arrays.toString() 方法，多維數(shù)組用 Arrays.deepToString() 方法

 public void display() {
       //自己順序表中不推薦使用 
        System.out.println(Arrays.toString(elem));
    }

注：在自己實(shí)現(xiàn)的順序表中不推薦使用Arrays.toString() 方法以及后面介紹到的遍歷數(shù)組的方法,因?yàn)轫樞虮砻看味际菙U(kuò)容2倍或者1.5倍的內(nèi)存，這就說(shuō)明我們的數(shù)組其實(shí)是有很多元素是沒有被賦值默認(rèn)為null或0的，又因?yàn)?code>Arrays.toString() 方法會(huì)將數(shù)組中所以元素打印出來(lái)，那么就會(huì)有下面的情景

③、使用 Arrays.asList()

該方法是將數(shù)組轉(zhuǎn)化為list
以下幾點(diǎn)需要注意：
（1）該方法不適用于基本數(shù)據(jù)類型
（byte,short,int,long,float,double,boolean），但可以用基本數(shù)據(jù)類型的包裝類。比如int的包裝類Integer.(Object 數(shù)組也是有效)
（2）該方法將數(shù)組與列表鏈接起來(lái)，當(dāng)更新其中之一時(shí)，另一個(gè)自動(dòng)更新
（3）不支持add和remove方法

 public void display() {
        //運(yùn)行結(jié)果和上面情況一樣！
        System.out.println(Arrays.asList(elem));
    }

運(yùn)行結(jié)果

④、使用for each

for-each 是 for 循環(huán)的另外一種使用方式. 能夠更方便的完成對(duì)數(shù)組的遍歷. 可以避免循環(huán)條件和更新語(yǔ)句寫錯(cuò).

   public void display() {
        //依舊是打印全部數(shù)組
        for (E x:elem) {
            System.out.print(x+" ");
        }
        System.out.println();

    }

運(yùn)行結(jié)果

⑤、使用迭代器

迭代器是設(shè)計(jì)模式的一種，后序容器接觸多了再給大家鋪墊（由于自己實(shí)現(xiàn)的順序表沒有迭代器，于是用的是java自帶的）

public static void main(String[] args) {
     List<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(666);
        list.add(888);
        Iterator<Integer> it = list.listIterator();
        while(it.hasNext()){
            System.out.print(it.next() + " ");
        }
        System.out.println();
   }

運(yùn)行結(jié)果

注意：

1. ArrayList最長(zhǎng)使用的遍歷方式是：for循環(huán)+下標(biāo) 以及 foreach
2. 迭代器是設(shè)計(jì)模式的一種，后序容器接觸多了再給大家鋪墊

定義一個(gè)異常（SubscriptException）

由于我們的增，刪，改以及獲取下標(biāo)對(duì)應(yīng)得元素的值，都需要傳下標(biāo)這個(gè)參數(shù)，又因?yàn)槲覀冚斎氲南聵?biāo)可能會(huì)越界，所以我們自己實(shí)現(xiàn)一個(gè)異常，一旦輸入的下標(biāo)越界，則拋出這個(gè)異常
注：

我們繼承的是一個(gè)編譯時(shí)異常也可以稱之為受查異常的Exception,所以我們?nèi)绻玫竭@個(gè)異常就需要聲明這個(gè)異常！

class SubscriptException extends Exception {

    public SubscriptException(String e) {
        super(e);
    }
}

接下來(lái)我們就可以去實(shí)現(xiàn)后面經(jīng)常會(huì)用到的判斷下標(biāo)是否會(huì)越界的方法了.

在這個(gè)方法中，當(dāng)我們輸入的下標(biāo)的值如果比我們的數(shù)組的長(zhǎng)度長(zhǎng)或者說(shuō)等于我們的數(shù)組的長(zhǎng)度那么就拋出這個(gè)異常！

  public void transBoundary(int pos) throws SubscriptException {
       
        if (pos>=usedSize) {
            throw new  SubscriptException("輸入下標(biāo)異常");
        }
    }

那么有人拋出異常就一定有人去接收這個(gè)異常，在下面實(shí)現(xiàn)

   //檢查要輸入的位置是否合法
    private boolean checkPosInAdd(int pos) throws SubscriptException {
        try {
            transboundary(pos);
        }catch (SubscriptException e) {
            System.out.println("捕捉到了下標(biāo)異常");
            e.printStackTrace();
            return false;
        }
        return true;//合法
    }

當(dāng)我們捕捉到這個(gè)異常的時(shí)候返回false,否則返回true,注意我們?cè)诜椒ǖ膮?shù)后面都聲明了這個(gè)異常！??！

增加元素（Add）

我們將鋪墊整理好了之后就可以進(jìn)行增，刪，改等操作了！

我們?cè)黾釉赜袃煞N方式：

第一種是在數(shù)組的最后一個(gè)位置插入，也可以稱為尾插!
第二種是指定位置插入。

我們先來(lái)討論一下，插入元素需要注意什么？

1.注意下標(biāo)是否越界
2.注意數(shù)組容量是否夠用
3.在插入元素之后數(shù)組元素加一

第一種方式的實(shí)現(xiàn)（比較簡(jiǎn)單）：

代碼如下：

    // 新增元素,默認(rèn)在數(shù)組最后新增
    public void add(E data) {
        if (isFull()) {
           elem= Capacity(elem);
        }
        elem[usedSize]=data;
        usedSize++;
    }

根據(jù)上面提到需要注意的第二點(diǎn)，我們就可以知道，該方法中的isFull方法就是判斷數(shù)組容量是否夠用，方法的實(shí)現(xiàn)如下

  /**
     * 判斷當(dāng)前的順序表是不是滿的！
     *
     * @return true:滿   false代表空
     */
    public boolean isFull() {
    //當(dāng)我的數(shù)組長(zhǎng)度和我的元素個(gè)數(shù)一樣多時(shí)，就返回true
    //意思就是需要擴(kuò)容
        return usedSize==elem.length;
    }

如果數(shù)組容量不夠，就去調(diào)用Capacity（）方法，當(dāng)然這個(gè)擴(kuò)容數(shù)組的方法也是需要咱們自己實(shí)現(xiàn)的，方法具體內(nèi)容如下

   //擴(kuò)容數(shù)組
    public E[] Capacity(E[]array) {

        return Arrays.copyOf(array,array.length*2);
    }

我們的數(shù)組需要擴(kuò)容時(shí)，一次擴(kuò)容一倍，如果是擴(kuò)容的容量太小，那么就需要擴(kuò)容很多次，這就造成了時(shí)間上的浪費(fèi)！雖然這樣擴(kuò)容可能會(huì)存在空間上的浪費(fèi)，但是當(dāng)我們學(xué)到線性表中的鏈表時(shí)就可以進(jìn)一步的解決這個(gè)問(wèn)題。

數(shù)組擴(kuò)容之后，將數(shù)組進(jìn)行尾插，最后數(shù)組元素個(gè)數(shù)加一！

第二種（指定位置插入）：

這里需要考慮的就是，我們?cè)撊绾尾迦?，以及需要注意的事?xiàng).

小魚先將總的代碼拿出來(lái)，下面進(jìn)行分析：

  public void add(int pos, E data) throws SubscriptException {
		//判斷要插入的元素是否是最后一個(gè)位置
        if (pos==usedSize) {//如果是則調(diào)用尾插的方法
            add(data);
            return;
        }
       if (!checkPosInAdd(pos)) {
       //判斷輸入的下標(biāo)是否越界，
       //如果越界則直接返回
           return;
       }
        //檢查容量
        if (isFull()) {
            elem=Capacity(elem);
        }
        for (int i = usedSize-1; i >=pos; i--) {
            //向后覆蓋
            elem[i+1]=elem[i];
        }
        set(pos,  data);
        usedSize++;
        System.out.println("添加成功");
    }

這一部分理解起來(lái)有一些困難，不過(guò)小魚會(huì)畫圖一步一步剖析，大家如果看完之后還有疑問(wèn)，或者改進(jìn)的方法請(qǐng)大膽私信小魚！??！
畫圖一步一步分析

第一步：我們先不管第一個(gè)方法，直接看第二個(gè)方法（藍(lán)色框框）

但是其實(shí)是存在坑的，假如我要插入元素的位置是數(shù)組的最后一個(gè)位置，那么由于transBoundary()中的判定條件，當(dāng)我輸入的下標(biāo)是數(shù)組的最后一個(gè)位置，又因?yàn)橄嗟人运蜁?huì)拋出數(shù)組越界的異常，我們?yōu)榱私鉀Q這個(gè)問(wèn)題，我在執(zhí)行這個(gè)方法前先進(jìn)行了第一步的判斷，也就是上圖中綠色的框框里面，當(dāng)我輸入的下標(biāo)就是數(shù)組的最后一個(gè)位置時(shí)，則直接調(diào)用尾插方法，避免了拋出異常。（解決方法很多，這只是小魚認(rèn)為好一些的）

第二步 ：

接下來(lái)就是檢查容量了，這個(gè)在上面講到過(guò)這里就不再重復(fù)，直接跳到紅框框里面的第四個(gè)方法。

前面講到的一個(gè)小朋友上廁所的例子大家還記得吧，當(dāng)在隊(duì)伍中的小朋友去上廁所回來(lái)時(shí)，就需要各位小朋友將他之前的位置騰出來(lái)，那么他原來(lái)位置后的小朋友就需要集體后移，如圖

所以我們可以根據(jù)該圖的思路，自己實(shí)現(xiàn)一個(gè)插入方法！

    for (int i = usedSize-1; i >=pos; i--) {
            //向后覆蓋
            elem[i+1]=elem[i];
        }
        set(pos,data);
        usedSize++;
        System.out.println("添加成功");

讓我們的數(shù)組中所有在pos位置及pos位置后面的元素后移一位，移動(dòng)之后將調(diào)用set()方法。

方法實(shí)現(xiàn)如下：

    // 給 pos 位置的元素設(shè)為【更新為】 value
    public void set(int pos, E value) throws SubscriptException {
        //修改元素
       if (!checkPosInAdd(pos)) {
           return;
       }
           elem[pos]=value;
    }

將pos位置的元素修改為要插入的元素，并且在使用這個(gè)方法時(shí)，也需要判斷下標(biāo)是否越界！
最后數(shù)組元素個(gè)數(shù)加一，打印添加成功提示程序員。

刪除元素（Delete）

經(jīng)過(guò)上述的增加元素，我們也可以發(fā)現(xiàn)，刪除元素其實(shí)也是有兩個(gè)方法：
方法一：刪除最后一個(gè)元素
方法二：刪除指定元素

方法一（尾刪）:

    public void delete() {
        //刪除最后一個(gè)元素
        elem[usedSize-1]=null;
        usedSize--;
    }

由于我們的usedSize是數(shù)組元素的個(gè)數(shù)，又因?yàn)槲覀兊臄?shù)組是從0下標(biāo)開始的，所以我們需要將usedSize-1,將該下標(biāo)置為null之后再對(duì)數(shù)組元素個(gè)數(shù)進(jìn)行減一。

方法二（指定刪除）：

這個(gè)問(wèn)題就相當(dāng)于前面講到過(guò)的小朋友去廁所問(wèn)題，當(dāng)這個(gè)小朋友去廁所后，那么他后面的小朋友就需要向前走將他的位置補(bǔ)上，也就是都像前移，具體如何實(shí)現(xiàn)呢？

所以我們的大概思路就是，將要?jiǎng)h除的元素的后面的元素都進(jìn)行前移的操作，最后將最后一個(gè)元素置為null,最后數(shù)組元素個(gè)數(shù)減一.

注意：

需要判斷下標(biāo)是否越界

    public void delete(int pos) throws SubscriptException {
        //判斷是否越界
        if (!checkPosInAdd(pos)) {
            return;
        }
        for (int i = pos; i < usedSize-1; i++) {
            elem[i]=elem[i+1];
        }
        //將最后一個(gè)元素置為null
        elem[usedSize-1]=null;
        //元素個(gè)數(shù)減一
        usedSize--;
        
    }

刪除下標(biāo)為2的元素，運(yùn)行結(jié)果

還有一些小魚就不進(jìn)行講解了，大家可以自己實(shí)現(xiàn)：

清空順序表
獲取順序表長(zhǎng)度
獲取下標(biāo)對(duì)于位置的元素
判斷順序表是否為空
刪除第一次出現(xiàn)的關(guān)鍵字

總結(jié)

順序表的缺點(diǎn)：

• ArrayList底層使用連續(xù)的空間，任意位置插入或刪除元素時(shí)，需要將該位置后序元素整體往前或者往后搬移，故時(shí)間復(fù)雜度為O(N)
• 增容需要申請(qǐng)新空間，拷貝數(shù)據(jù)，釋放舊空間。會(huì)有不小的消耗。
• 增容一般是呈2倍的增長(zhǎng)，勢(shì)必會(huì)有一定的空間浪費(fèi)。例如當(dāng)前容量為100，滿了以后增容到200，我們?cè)倮^續(xù)插入了5個(gè)數(shù)據(jù)，后面沒有數(shù)據(jù)插入了，那么就浪費(fèi)了95個(gè)數(shù)據(jù)空間。

那么我們?nèi)绾谓鉀Q呢？

這些問(wèn)題將會(huì)在鏈表中給大家講解?。?！

文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-831705.html

到了這里，關(guān)于你還不懂《順序表》？那就不要錯(cuò)過(guò)這篇文章！?。〉奈恼戮徒榻B完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！