一、線性表

線性表（linear list）是n個(gè)具有相同特性的數(shù)據(jù)元素的有限序列。 線性表是一種在實(shí)際中廣泛使用的數(shù)據(jù)結(jié)構(gòu)，常見的線性表：順序表、鏈表、棧、隊(duì)列...

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

二、順序表

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

接口的實(shí)現(xiàn)

注意事項(xiàng):

• 接口里的抽象方法一定要重寫
• 接口里的默認(rèn)方法可選重寫
• 接口里的空接口不用重寫
• 不是接口方法不用重寫
• 快捷重寫鍵: ctrl + o

使用方法

現(xiàn)在我們通過數(shù)據(jù)結(jié)構(gòu)來使用這些方法

數(shù)據(jù)結(jié)構(gòu)與以往我們練習(xí)有最大的不同就是，可以實(shí)現(xiàn)自己造輪子

1.display方法

我們來寫一個(gè)遍歷

display可以遍歷數(shù)據(jù)表中的所有元素

這樣可以遍歷所有數(shù)據(jù)表中的有效數(shù)據(jù)

不可以用for each來遍歷，因?yàn)樗袛?shù)據(jù)都是零，無法區(qū)分是否為有效數(shù)據(jù)

正常來講，因?yàn)楝F(xiàn)在數(shù)據(jù)表里沒有任何有效數(shù)據(jù)，所以分割線下面應(yīng)該是沒有數(shù)據(jù)打印的，但是打印了許多的零是因?yàn)橛胒or each來遍歷的話所有數(shù)據(jù)都是零，無法區(qū)分是否為有效數(shù)據(jù)

2.add方法

這里有兩個(gè)add方法

• 第一個(gè)add方法 默認(rèn)將數(shù)據(jù)放在數(shù)組最后
• 第二個(gè)add方法 指定將數(shù)據(jù)放在數(shù)組中某位置

第一個(gè)add方法

如果滿了，那我們就使用grow來進(jìn)行擴(kuò)容，這里使用的是二倍擴(kuò)容，這里的grow用的是private修飾符，畢竟使用者也無需觸碰到擴(kuò)容

輸出結(jié)果：

第二個(gè)add方法

這個(gè)比較抽象，我們先講一下思路：

• 要將數(shù)據(jù)插入數(shù)組某一位置，那么我們就要把在原先在這個(gè)位置上的數(shù)據(jù)移動(dòng)到下一個(gè)位置，
• 但是有個(gè)問題，如果該數(shù)據(jù)所在的下一個(gè)位置上還有數(shù)據(jù)，就會導(dǎo)致兩個(gè)數(shù)據(jù)重疊，
• 因此我們要首先移動(dòng)最后一個(gè)有效數(shù)據(jù)，
• 在技術(shù)上可以實(shí)現(xiàn)為 將i下標(biāo)的數(shù)據(jù)定義為 有效數(shù)據(jù)-1 ，即 usedSize-1(有零下標(biāo)) ，再將i下標(biāo)的值賦值給i+1 ，直到 i== 插入數(shù)據(jù)位置，(即pos位置)也要挪動(dòng)

i = usedSize - 1;
[i+1] = [i];//直到挪動(dòng)完 i==pos

然后將要插入的數(shù)據(jù)放到pos位置，最終讓usedSize++(插入了一個(gè)數(shù)據(jù)就多了一個(gè)有效數(shù)據(jù))就可以了，但是涉及到數(shù)組，我們還要判斷是否會溢出.

代碼：

看似代碼一切正常，但有同學(xué)可能會問：

• 如果插入的下標(biāo)位置是負(fù)數(shù)怎么辦?
• 如果插入的下標(biāo)位置大于 usedSize 怎么辦?

數(shù)據(jù)結(jié)構(gòu)規(guī)定 每次插入數(shù)據(jù)的位置 不能有空隙 即前驅(qū)必須存在 也就是說 插入位置的前一個(gè)位置不能是空的

現(xiàn)在我們要實(shí)現(xiàn)：

• pos < 0 不可以插入
• pos > usedSize 不可以插入
• pos == usedSize 可以插入

代碼：

這一塊前面都提到過就不解釋了

3.contains 與 indexof 方法

為了能更好的理解這兩個(gè)方法，請大家依據(jù)中間紅色字體的要求來編寫一段代碼

代碼：

那如果是引用類型怎么辦，那就不能這樣比較了，應(yīng)該用equals來比較

因此不是說數(shù)據(jù)表只能放整型

4.get方法

如果數(shù)據(jù)表是空的怎么辦

當(dāng)然也可以再寫一個(gè)空異常

5.set方法

這個(gè)方法的作用是更新，或者說是覆蓋舊的數(shù)據(jù)

因此pos(數(shù)據(jù)的下標(biāo))必須在0到usedSize - 1之間

6.remove方法

這個(gè)方法的作用是刪除

注意必須是usedSize-1，如果不減一，在數(shù)據(jù)放滿的情況下array[i+1]會越界

7.clear方法

這個(gè)方法很簡單，就是清空數(shù)組，因?yàn)橹拔覀儗ata全部存放于usedSzie中

如果usedSize = 0，那么就相當(dāng)于把數(shù)據(jù)全部清空了

上面的寫法適用于基本數(shù)據(jù)類型

如果是引用數(shù)據(jù)類型，如何使用這個(gè)方法?

如果是引用數(shù)據(jù)類型，那么存儲的是地址，這種情況下我們需要遍歷這些地址，把他們?nèi)恐脼榭?，否則會引起內(nèi)存泄漏

什么是內(nèi)存泄漏，簡單來說內(nèi)存泄漏就是我已經(jīng)不使用某個(gè)對象了，但是有個(gè)引用數(shù)據(jù)類型一直在引用這個(gè)對象，那么這個(gè)對象就不能被回收，因此會一直浪費(fèi)內(nèi)存

因?yàn)槭腔绢愋退詴?bào)錯(cuò)，把基本類型換為應(yīng)用類型就不會報(bào)錯(cuò)了

順序表的優(yōu)點(diǎn)與缺點(diǎn)

• 優(yōu)點(diǎn)：給定下標(biāo)的情況下，查詢速度非?？?O(1)
• 缺點(diǎn)：如果要?jiǎng)h除或增添數(shù)據(jù)，非常慢 O(N)

三、ArrayList簡介

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

【說明】

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

四、ArrayList的使用

ArrayList的構(gòu)造

ArrayList常見方法

ArrayList常用遍歷方法

可大致分為

for         for-each       Interator迭代器

其中Interator可以延伸出其他用法，ListInterator是Interator用法的延伸

二維數(shù)組

總結(jié)

以上為個(gè)人經(jīng)驗(yàn)，希望能給大家一個(gè)參考，也希望大家多多支持腳本之家。

最新評論