1.線性表
線性表可以執(zhí)行如下操作：
- 從線性表中提取一個(gè)元素。
- 向線性表插入一個(gè)元素坝辫。
- 從線性表刪除一個(gè)元素篷就。
- 找出線性表中元素的個(gè)數(shù)。
- 確定線性表中是否包含某個(gè)元素近忙。
- 確定線性表是否為空竭业。
實(shí)現(xiàn)線性表兩種方式:
1)數(shù)組（array）
數(shù)組大小是固定的。如果元素個(gè)數(shù)超過了數(shù)組的容量及舍，就創(chuàng)建一個(gè)更大的新數(shù)組未辆，并將當(dāng)前數(shù)組中的元素復(fù)制到新數(shù)組。
2）鏈?zhǔn)浇Y(jié)構(gòu)
由結(jié)點(diǎn)組成锯玛，每個(gè)結(jié)點(diǎn)都是動(dòng)態(tài)創(chuàng)建的咐柜，用來存儲(chǔ)一個(gè)元素。所有的結(jié)點(diǎn)鏈接成一個(gè)線性表攘残。
相應(yīng)的類為MyArrayList和MyLinkedList拙友，這兩種類具有相同的操作，但是具有不同的實(shí)現(xiàn)肯腕。
1）myArrayList
- 初始化：用默認(rèn)大小創(chuàng)建一個(gè)類型為E[ ]的數(shù)組data献宫。向數(shù)組插入一個(gè)新元素時(shí)钥平，首先確定數(shù)組是否有足夠的空間实撒，若空間不夠，則創(chuàng)建大小為當(dāng)前數(shù)組兩倍的新數(shù)組涉瘾，然后將當(dāng)前數(shù)組中的元素復(fù)制到新數(shù)組中知态。
-
插入元素：在指定下標(biāo)處插入一個(gè)新元素之前，必須將指定下標(biāo)后面的所有元素都向右移動(dòng)一個(gè)位置立叛，并將線性表的長(zhǎng)度加1负敏。
-
刪除元素：刪除指定下標(biāo)的一個(gè)元素時(shí)，應(yīng)該將該下標(biāo)后面的元素都向左移動(dòng)一個(gè)位置秘蛇，并將線性表大小減1其做。
實(shí)現(xiàn)：
2）鏈表
在使用數(shù)組實(shí)現(xiàn)的MyArrayList時(shí)顶考，add(int index,E e)插入和remove(int index)方法的效率很低，他們需要
移動(dòng)大量元素妖泄。為提高在線性表中插入和刪除元素的效率驹沿，可以采用鏈?zhǔn)浇Y(jié)構(gòu)來實(shí)現(xiàn)線性表。
-
結(jié)點(diǎn)
創(chuàng)建存儲(chǔ)3個(gè)結(jié)點(diǎn)的示例：
遍歷線性表中的結(jié)點(diǎn)：
如果結(jié)點(diǎn)是線性表中的最后一個(gè)蹈胡，那么它的指針數(shù)據(jù)next所包含的值為null渊季。
-
myLinkedList類
實(shí)現(xiàn)addFirst(e)方法：
實(shí)現(xiàn)addlast方法：
實(shí)現(xiàn)任意位置插入的方法：
實(shí)現(xiàn)removeFirst方法
實(shí)現(xiàn)removeLast()方法
實(shí)現(xiàn)remove(index)方法
3）ArrayList和LinkedList對(duì)比
使用數(shù)組實(shí)現(xiàn)ArrayList，使用鏈表實(shí)現(xiàn)LinkedList,ArrayList的開銷比LinkedList小罚渐。
但需要進(jìn)行插入刪除操作却汉，使用鏈表效率更高。
4）鏈表的變體
-
循環(huán)單鏈表：鏈表的最后一個(gè)結(jié)點(diǎn)的指針指回到第一個(gè)結(jié)點(diǎn)荷并。沒有tail結(jié)點(diǎn)
-
雙向鏈表：包含兩個(gè)指針的結(jié)點(diǎn)合砂，一個(gè)指針指向下一個(gè)結(jié)點(diǎn)，另一個(gè)指針指向前一個(gè)結(jié)點(diǎn)璧坟。雙向鏈表可以向前遍歷也可以向后遍歷既穆。
- 循環(huán)雙向鏈表：在雙向鏈表的基礎(chǔ)上，鏈表的第一個(gè)節(jié)點(diǎn)的前向指針指向最后一個(gè)結(jié)點(diǎn)雀鹃，鏈表的最后一個(gè)結(jié)點(diǎn)的后向指針指向第一個(gè)結(jié)點(diǎn)幻工。
2.棧
用數(shù)組或ArrayList可以實(shí)現(xiàn)棧，棧后進(jìn)先出黎茎。
3.隊(duì)列
用LinkedList來實(shí)現(xiàn)隊(duì)列囊颅。
4.優(yōu)先隊(duì)列
用堆實(shí)現(xiàn)優(yōu)先隊(duì)列。
