2.2　順序表

順序表采用順序結(jié)構(gòu)存儲(chǔ)數(shù)據(jù)，在Java語(yǔ)言中常用的順序存儲(chǔ)結(jié)構(gòu)是數(shù)組。順序表如圖2-1所示。

2.2.1　順序表添加元素

在順序表指定位置添加元素，首先需要確定指定位置是否已經(jīng)有元素。如果指定位置沒(méi)有元素，就直接加入元素，如圖2-2所示。

如果指定位置已經(jīng)有元素，就需要將指定位置處的元素及其后續(xù)元素依次向后移動(dòng)，將指定位置空出后，插入指定元素，如圖2-3所示。

2.2.2　順序表查找元素

當(dāng)順序表按照索引查找元素時(shí)，將以O(shè)(1)的時(shí)間復(fù)雜度查找到指定的元素，如圖2-4所示。

順序表按照元素值查詢指定元素時(shí)，需要從第一個(gè)元素開(kāi)始依次向后查找元素，直至找到指定元素，查找的時(shí)間復(fù)雜度為O(n)。查找V5元素的過(guò)程如圖2-5所示。

2.2.3　順序表刪除元素

如果從順序表刪除的元素是末尾元素，就直接刪除即可，如圖2-6所示。

如果刪除的元素并非末尾元素，就已刪除元素后面的所有元素將依次向前移動(dòng)，如圖2-7所示。

2.2.4　順序表的實(shí)現(xiàn)

創(chuàng)建順序表實(shí)現(xiàn)類SequenceList并實(shí)現(xiàn)List接口。其中使用對(duì)象數(shù)組Object[]存儲(chǔ)線性表中的數(shù)據(jù)。順序表SequenceList類的代碼如下：

創(chuàng)建順序表測(cè)試類，驗(yàn)證順序表的功能。測(cè)試類的代碼如下：

執(zhí)行順序表測(cè)試類，測(cè)試結(jié)果如下：

因?yàn)榫€性表有最大容量maxSize = 15的限制，所以在測(cè)試代碼中再次添加新元素100時(shí)，將會(huì)拋出“順序表已滿，無(wú)法插入！”的異常信息。

2.2.5　順序表常見(jiàn)面試考點(diǎn)

（1）順序表的概念：順序表是使用順序結(jié)構(gòu)存儲(chǔ)的線性表。

（2）順序表的存儲(chǔ)：順序表必須使用一塊連續(xù)的存儲(chǔ)空間存儲(chǔ)數(shù)據(jù)。

（3）順序表的優(yōu)點(diǎn)：順序表是使用順序結(jié)構(gòu)存儲(chǔ)數(shù)據(jù)的，通過(guò)索引訪問(wèn)元素的時(shí)間復(fù)雜度為O(1)。

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

·　順序表的存儲(chǔ)空間必須是連續(xù)的，如果在順序表中存儲(chǔ)大量數(shù)據(jù)，那么對(duì)存儲(chǔ)介質(zhì)的容量是一個(gè)挑戰(zhàn)。

·　順序表的存儲(chǔ)容量是有限的、固定的，超過(guò)順序表的存儲(chǔ)容量將無(wú)法進(jìn)行數(shù)據(jù)存儲(chǔ)。

·　順序表中按值查找元素的時(shí)間復(fù)雜度為O(n)。

·　在順序表的非末尾位置添加元素將導(dǎo)致順序表此位置后的元素依次向后移動(dòng)。

·　在順序表的非末尾位置刪除元素將導(dǎo)致順序表此位置后的元素依次向前移動(dòng)。

（5）JDK中的實(shí)現(xiàn)：JDK中的ArrayList實(shí)現(xiàn)了順序表，并提供了動(dòng)態(tài)擴(kuò)容等高級(jí)特性，ArrayList的詳細(xì)內(nèi)容可參考本書(shū)4.2節(jié)。