目錄
?順序表（ArrayList）
什么是順序表？?
代碼實(shí)現(xiàn)?（MyArrayList）
--- 打印順序表?
--- 新增元素?
1.新增元素，默認(rèn)在數(shù)組最后新增
2.在指定位置新增元素?
--- 判斷是否包含某個元素
--- 查找某個元素具體位置（下標(biāo)）
--- 獲取 pos 位置的元素
--- 給pos位置 的值設(shè)為 value?
--- 獲取順序表長度
--- 刪除第一次出現(xiàn)的關(guān)鍵字?
--- 清除順序表?
完整代碼
ArrayList
ArrayList 的實(shí)例化
ArrayList的構(gòu)造?
ArrayList常見操作
ArrayList的遍歷
---- 迭代器?
--- 用法一?
--- 用法二?
--- 從后往前打印?
----??for循環(huán)+下標(biāo)
---- foreach?
ArrayList 的優(yōu)缺點(diǎn)?
優(yōu)點(diǎn)?
缺點(diǎn)?
鏈表 （LinkedList）
什么是鏈表？
單向?不帶頭?非循環(huán)?鏈表?
代碼實(shí)現(xiàn)?
節(jié)點(diǎn)
插入數(shù)據(jù)?
--- 頭插法?
?--- 尾插法
--- 任意位置插入（第一個數(shù)據(jù)節(jié)點(diǎn)為0號下標(biāo)）
打印鏈表?
?單鏈表的長度
查找單鏈表中是否包含關(guān)鍵字key
刪除第一次出現(xiàn)關(guān)鍵字為key的節(jié)點(diǎn)
刪除所有值為key的節(jié)點(diǎn)
清除鏈表?
完整代碼?
?雙向?不帶頭?非循環(huán)?鏈表
代碼實(shí)現(xiàn)?
創(chuàng)建節(jié)點(diǎn)內(nèi)部類?
插入數(shù)據(jù)
--- 頭插法?
--- 尾插法?
打印鏈表
查找鏈表中是否包含關(guān)鍵字key?
?鏈表的長度
任意位置插入,第一個數(shù)據(jù)節(jié)點(diǎn)為0號下標(biāo)
刪除第一次出現(xiàn)關(guān)鍵字為key的節(jié)點(diǎn)
刪除所有值為key的節(jié)點(diǎn)
清除鏈表?
完整代碼
?LinkedList的使用
LinkedList 的 常見方法?
LinkedList 的總結(jié)?
ArrayList和LinkedList的區(qū)別（順序表和鏈表的區(qū)別）（面試題）
前言：這篇博客我們重點(diǎn)講?線性表中的順序表、鏈表
線性表（linear list）是n個具有相同特性的數(shù)據(jù)元素的有限序列。
線性表是一種在實(shí)際中廣泛使用的數(shù)據(jù)結(jié)構(gòu)，常見的線性表：順序表、鏈表、棧、隊列...
線性表在邏輯上是線性結(jié)構(gòu)，也就說是連續(xù)的一條直線。但是在物理結(jié)構(gòu)上并不一定是連續(xù)的，線性表在物理上存儲時，通常以數(shù)組和鏈?zhǔn)浇Y(jié)構(gòu)的形式存儲。?
?順序表（ArrayList）
什么是順序表？?
順序表是用一段物理地址連續(xù)的存儲單元，依次存儲數(shù)據(jù)元素的線性結(jié)構(gòu)，一般情況下采用數(shù)組存儲。在數(shù)組上完成數(shù)據(jù)的增刪查改。
?也就是說，順序表? 底層結(jié)構(gòu)就是 一個數(shù)組。是使用數(shù)組 來完成的一種結(jié)構(gòu)。
那現(xiàn)在有一個數(shù)組，如果有一組數(shù)據(jù) 1，2，3，4，5，6，7 ， 我們現(xiàn)在想把這組數(shù)據(jù)放到數(shù)組里去。
我們先放進(jìn)1，2，3 ， 問當(dāng)前數(shù)組里有多少個有效數(shù)據(jù)？ 很明顯是 3 個。
那怎么利用程序判斷他有 3 個有效數(shù)據(jù)呢？
我們需要先定義一個變量 usedSize , 放進(jìn)一個數(shù)據(jù) usedSize++,放一個就加一下。這不就能確定有幾個有效數(shù)據(jù)了嗎。
代碼實(shí)現(xiàn)?（MyArrayList）
接下來我們利用代碼來實(shí)現(xiàn)順序表的增刪查改等方法：?
--- 打印順序表?
就是遍歷數(shù)組?
--- 新增元素?
1.新增元素，默認(rèn)在數(shù)組最后新增
?這么寫沒問題嗎？如果滿了怎么辦？
所有我們要寫一個方法來判斷是否滿了 ：
新增元素前我們要判斷是否滿了，滿了的話要擴(kuò)容?
新增看看效果：
??
2.在指定位置新增元素?
我們的邏輯應(yīng)該是把指定位置之后的數(shù)據(jù)?都向后挪，把指定位置空出來，再在指定位置插入數(shù)據(jù) 。
那具體該如何挪數(shù)據(jù)？?
我們要從最后的位置開始挪?，不能從第一個開始挪，不然會把之后的數(shù)據(jù)蓋掉。
?
那我們現(xiàn)在確定了挪的方法，接下來我們看看代碼如何實(shí)現(xiàn)：?
注意：我們這里是要判斷pos的位置是否合法的 ，
pos不能小于0，也不能跳著放（大于usedSize）.
為此我們還搞了個異常?
（ps:異常之前講過 鏈接?https://blog.csdn.net/iiiiiihuang/article/details/130671801?spm=1001.2014.3001.5501?）
我們看看運(yùn)行效果?：
看看位置不合法時的運(yùn)行結(jié)果：?
--- 判斷是否包含某個元素
運(yùn)行結(jié)果??
--- 查找某個元素具體位置（下標(biāo)）
運(yùn)行結(jié)果?
--- 獲取 pos 位置的元素
還要判斷位置是否合法。
運(yùn)行結(jié)果?
--- 給pos位置 的值設(shè)為 value?
?這里同樣要先判斷 pos 位置是否合法，那我們可以單獨(dú)寫一個方法，來判斷。（方法的封裝）
運(yùn)行結(jié)果?
--- 獲取順序表長度
--- 刪除第一次出現(xiàn)的關(guān)鍵字?
代碼實(shí)現(xiàn)?
?
注意：usedSize - 1 防止越界，這里是?this.elem[i] = this.elem[i + 1]， 那 i 走到倒數(shù)第二位就行了
運(yùn)行結(jié)果?
--- 清除順序表?
?
ps （小提一嘴）: 現(xiàn)在的都是整型這么寫可以，但是的是 引用類型 的時候要一個一個 置為 null ，刪除也要有類似操作。
完整代碼
import java.util.ArrayList;
import java.util.Arrays;
/**
* @Author: iiiiiihuang
*/
public class MyArrayList {
private int[] elem;//存放數(shù)據(jù)元素。
private int usedSize;//代表當(dāng)前順序表中有效數(shù)據(jù)個數(shù)。
private static final int DEFAULT_SIZE = 10;
/**
* 默認(rèn)構(gòu)造方法
*/
public MyArrayList() {
this.elem = new int[DEFAULT_SIZE];
}
/**
* 指定容量
* @param initCapacity
*/
public MyArrayList(int initCapacity) {
this.elem = new int[initCapacity];
}
/**
* 打印順序表中的所有元素
*/
public void display() {
for (int i = 0; i < this.usedSize; i++) {
System.out.print(this.elem[i] + " ");
}
}
public boolean isFull() {
if(this.usedSize == this.elem.length){
return true;
}
return false;
}
/**
* 新增元素，默認(rèn)在數(shù)組最后新增
* @param date
*/
public void add(int date){
if(isFull()){
//擴(kuò)容
this.elem = Arrays.copyOf(this.elem, 2*this.elem.length);
}
this.elem[this.usedSize] = date;
this.usedSize++;
}
//判斷pos位置是否合法
private void checkPos(int pos){
if(pos < 0 || pos >= usedSize){
throw new PosOutOfBoundsException(pos + "位置不合法");
}
}
/**
* 在指定位置（pos）新增元素
* @param pos
* @param date
*/
public void add(int pos, int date) {
//判斷pos位置是否合法
if(pos < 0 || pos > usedSize){
throw new PosOutOfBoundsException(pos + "位置不合法");
}
if(isFull()){
this.elem = Arrays.copyOf(this.elem, 2*this.elem.length);
}
for (int i = this.usedSize - 1; i >= pos; i--) {
this.elem[i + 1] = this.elem[i];
}
this.elem[pos] = date;
usedSize++;
}
/**
* 判斷是否包含某個元素
* @param toFind
* @return
*/
public boolean contains(int toFind){
for (int i = 0; i < this.usedSize; i++) {
if(this.elem[i] == toFind){
return true;
}
}
return false;
}
/**
* 查找某個元素具體位置(下標(biāo)）
* @param toFind
* @return
*/
public int indexOf(int toFind){
for (int i = 0; i < this.usedSize; i++) {
if(this.elem[i] == toFind){
return i;
}
}
return -1;
}
/**
* 獲取 pos 位置的元素
* @param pos
* @return
*/
public int get(int pos) {
//判斷pos位置是否合法
checkPos(pos);
return this.elem[pos];
}
/**
* 給pos位置 的值設(shè)為 value
* @param pos
* @param value
*/
public void set(int pos, int value) {
checkPos(pos);
this.elem[pos] = value;
}
/**
* 獲取順序表長度
*/
public int size() {
return this.usedSize;
}
/**
* 刪除第一次出現(xiàn)的關(guān)鍵字
* @param toRemove
*/
public void remove(int toRemove) {
//獲取要刪除元素下標(biāo)
int index = indexOf(toRemove);
if(index == -1){
System.out.println("沒有這個數(shù)據(jù)");
return;
}
//usedSize - 1 防止越界
for (int i = index; i < this.usedSize - 1; i++) {
this.elem[i] = this.elem[i + 1];
}
usedSize--;
}
/**
* 清除順序表
*/
public void clear() {
this.usedSize = 0;
}
}上述是自己實(shí)現(xiàn)一個順序表結(jié)構(gòu)，那以后用到順序表都要我們自己重新實(shí)現(xiàn)嗎？ 當(dāng)然不用啦！?
Java里面已經(jīng)幫你處理好了，有現(xiàn)成的 ，就是 ArrayList
ArrayList ?
在集合框架中，ArrayList是一個普通的類，實(shí)現(xiàn)了List接口 。?
1. ArrayList是以泛型方式實(shí)現(xiàn)的，使用時必須要先實(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ù)的空間，并且可以動態(tài)擴(kuò)容，是一個動態(tài)類型的順序表?
我們可以在 IDEA 里看到?ArrayList 的源碼
接下來我們 來介紹一下 ArrayList 的幾種用法。
ArrayList 的實(shí)例化
?這兩種方法都行，區(qū)別就在于，方法一 可以調(diào)用的方法更多一些。 但是方法二 發(fā)生了向上轉(zhuǎn)型，
一般情況下，我們用方法二多一點(diǎn)。
（ps: 向上轉(zhuǎn)型 前面介紹過了 鏈接??https://blog.csdn.net/iiiiiihuang/article/details/130484383?spm=1001.2014.3001.5501?）
ArrayList的構(gòu)造?
| 方法 | 解釋 |
| ArrayList() | 無參構(gòu)造 |
| ArrayList(Collection<? extends E> c) | 利用其他 Collection 構(gòu)建 ArrayList |
| ArrayList(int initialCapacity) | 指定順序表初始容量 |
當(dāng)我們調(diào)用不帶參數(shù)的構(gòu)造方法時，默認(rèn)在第一次 add 時才會分配大小為10的內(nèi)存
擴(kuò)容按1.5倍進(jìn)行擴(kuò)容?
??
ArrayList常見操作
?
| 方法 | 解釋 |
| boolean add(E e) | 尾插 e |
| void add(int index, E element) | 將 e 插入到 index 位置 |
| boolean addAll(Collection<? extends E> c) | 尾插 c 中的元素 |
| E remove(int index) | 刪除 index 位置元素 |
| boolean remove(Object o) | 刪除遇到的第一個 o |
| E get(int index) | 獲取下標(biāo) index 位置元素 |
| E set(int index, E element) | 將下標(biāo) index 位置元素設(shè)置為 element |
| void clear() | 清空 |
| boolean contains(Object o) | 判斷 o 是否在線性表中 |
| int indexOf(Object o) | 返回第一個 o 所在下標(biāo) |
| int lastIndexOf(Object o) | 返回最后一個 o 的下標(biāo) |
| List<E> subList(int fromIndex, int toIndex) | 截取部分 list |
注意：這個remove怎么用？?
?
要這么寫才能刪掉 等于2 的元素?
演示一下?subList
截取到2，3? ? （Java里一般都是左閉右開的 [ , , )? ?)?
如果我們把 list3 的 0 下標(biāo)該成 188 會方生什么？
我們發(fā)現(xiàn)，list2 的 1 下標(biāo)的位置（list3 的 0下標(biāo)）也變成了188??. 為什么？?
這是因為list3, 截取的時候并沒有真正的把這個數(shù)據(jù)拿出來，只是指向了1 下標(biāo)那兒的地址 ，所有更新值肯定會影響 list2.
ArrayList的遍歷
?
ArrayList 可以使用三方方式遍歷：使用迭代器 ，for循環(huán)+下標(biāo)、foreach?
?上面是直接 用sout 遍歷 的，是因為重寫了 toString 方法。?
---- 迭代器?
一般情況下，能夠直接通過 sout 輸出 引用指向?qū)ο螽?dāng)中的內(nèi)容的時候，此時一定重寫了 toString 方法。?
那我們看看ArrayList 里有沒有 toString (ctrl + F) 搜索一下。發(fā)現(xiàn)沒有。
?
但是?ArrayList ?還繼承了?AbstractList，我們?nèi)?AbstractList 里找找。發(fā)現(xiàn)還沒有。
但是?AbstractList 還繼承了?AbstractCollection ，
我們在?AbstractCollection 這里找到了 toString。
下面畫線那個部分就是 迭代器 （遍歷當(dāng)前集合）
--- 用法一?
--- 用法二?
上面兩個用那個都行?
--- 從后往前打印?
ps : 這個方法不行，因為這個不能傳參?
----??for循環(huán)+下標(biāo)
---- foreach?
?
?
ArrayList 的優(yōu)缺點(diǎn)?
優(yōu)點(diǎn)?
?1.可以通過下標(biāo) 進(jìn)行隨機(jī)訪問，順序表適合對靜態(tài)的數(shù)據(jù)進(jìn)行 查找 和 更新
缺點(diǎn)?
1.添加元素的效率比較低 （假如在 0 位置添加元素，就需要把后面所有的元素都往后移）
2.刪除的效率也低（假如刪除?0 位置元素，也需要移動后面所有的元素）
3.擴(kuò)容 按1.5 倍擴(kuò)容，有浪費(fèi) 空間的情況。
（順序表不適合用來 插入和刪除 數(shù)據(jù)）
順序表適合對靜態(tài)的數(shù)據(jù)進(jìn)行 查找 和 更新，不適合用來 插入和刪除 數(shù)據(jù)，這時候就需要用 鏈表來做。接下來我們來介紹鏈表。
鏈表 （LinkedList）
什么是鏈表？ ?
鏈表 是一種 物理存儲結(jié)構(gòu)上非連續(xù)?的存儲結(jié)構(gòu)，數(shù)據(jù)元素的 邏輯順序 是通過鏈表中的 引用鏈接次序?qū)崿F(xiàn)的 。
鏈表是由一個一個 節(jié)點(diǎn) 連成的 ：（這個是單向 不帶頭 非循環(huán) 鏈表的節(jié)點(diǎn)）
?
單向 不帶頭 非循環(huán) 鏈表?
除此之外還有很多 類型的 鏈表，一般從三個方向去分?
- 單向? ? 雙向
- 不帶頭? ?帶頭
- 非循環(huán)? ?循環(huán)??
?經(jīng)過排列組合就會有下面這幾種類型的鏈表：
- 單向?不帶頭?非循環(huán)?鏈表
- 單向?不帶頭?循環(huán)?鏈表
- 單向?帶頭?非循環(huán)?鏈表
- 單向?帶頭?循環(huán)?鏈表
- 雙向?不帶頭?非循環(huán)?鏈表
- 雙向?不帶頭?循環(huán)?鏈表
- 雙向?帶頭?非循環(huán)?鏈表
- 雙向?帶頭?循環(huán)?鏈表
上面我們畫了不帶頭的?鏈表，接下來我們了解一下 帶頭的是啥樣的？
再來看看 循環(huán)的 ：
等我們把單向的介紹完，在介紹雙向的 。
我們重點(diǎn)講?單向?不帶頭?非循環(huán)?鏈表 和?雙向?不帶頭?非循環(huán)?鏈表 （這兩種是工作，筆試面試考試重點(diǎn)）
單向?不帶頭?非循環(huán)?鏈表?
代碼實(shí)現(xiàn)?
節(jié)點(diǎn)
上述可知 鏈表是由一個一個 節(jié)點(diǎn) 組成的，所以我們可以把這個節(jié)點(diǎn)定義成個內(nèi)部類?。
還得有一個 指向 第一個節(jié)點(diǎn) 的屬性：
插入數(shù)據(jù)?
--- 頭插法?
??
注意：如果我們把下面的語句反過來寫可以嗎？ 變成?head = node;? node.next = head;
?
?不可以，先把node 置為 head, node 的下一個指向 head, 那不就是 自己指向自己了嗎，后面的節(jié)點(diǎn)就都丟失了。
我們插入看看效果?
?--- 尾插法
先找到最后一個節(jié)點(diǎn)，
所以循環(huán)里要寫成 cur.next != null, 在到最后一個節(jié)點(diǎn)這就不進(jìn)入循環(huán)了，那此時cur 就是最后一個節(jié)點(diǎn)，而不能寫成cur != null, 這樣會遍歷完整個鏈表，停不住。?
?
運(yùn)行看看效果：?
似乎是可以的，但是如果現(xiàn)在鏈表了一個節(jié)點(diǎn)也沒有，再插入呢？
報錯了?。 ?空指針異常 ，為啥呀？ 我們返回代碼哪里看一看，調(diào)試一下：
我們發(fā)現(xiàn)當(dāng) 鏈表里一個節(jié)點(diǎn)都沒有的時候，head? = null，那cur = head, cur 也是 null，
那cur都為空了，哪來的 next ，那當(dāng)然就報出來空指針異常了。
所以接下來我們改進(jìn)一下代碼：?
那我們再運(yùn)行一下代碼，就沒有任何問題了
--- 任意位置插入（第一個數(shù)據(jù)節(jié)點(diǎn)為0號下標(biāo)）
?
很明顯，我們要確定 插入位置的前一個節(jié)點(diǎn)， 那如果你要插入 2 位置，那你就要找到 1 位置節(jié)點(diǎn)，那從 0 位置到 1 位置要走一步，也就是 index - 1 步。
找到要插入位置的前一個節(jié)點(diǎn)。這個是寫方法?里面，還是單獨(dú)封裝看你喜好。
（我用的 while 循環(huán)，如果用for 循環(huán)的話，i < index - 1,? 我覺得while 循環(huán)好理解點(diǎn)。）
?
?找到位置了，我們就可以插入了。?
先判斷插入位置合不合法（類比上面的順序表的部分）
都要先和后邊的節(jié)點(diǎn)建立聯(lián)系哦??
看看效果
打印鏈表?
?
但是用上面的方式走完之后，我自己都不知道頭節(jié)點(diǎn)在哪里了 ，很可怕耶，
所以我們定義一個 cur節(jié)點(diǎn) 來代替 頭節(jié)點(diǎn) 往下走。
?
?單鏈表的長度
?
查找單鏈表中是否包含關(guān)鍵字key
刪除第一次出現(xiàn)關(guān)鍵字為key的節(jié)點(diǎn)
?
還是要找到刪除節(jié)點(diǎn)的前一個，
為什么，循環(huán)那里要 cur.next != null, 因為，cur.next 不能是null，因為如果它是 null 的話，
那cur.next.val 就找不到值，那就會引起空指針異常，所以只要走到倒數(shù)第一個停住就好了（cur走到最后一個節(jié)點(diǎn)時不進(jìn)入循環(huán)）?
看看效果：
刪除所有值為key的節(jié)點(diǎn)
?
注意 ：我們刪除的是 cur 對應(yīng)的值，cur 從第二個節(jié)點(diǎn)開始走，那如果第一個也是23（要刪除的值）呢?，所以我們要單獨(dú)刪除頭節(jié)點(diǎn)，且在最后，不能放在前面。
運(yùn)行結(jié)果?
清除鏈表?
完整代碼?
/**
* @Author: iiiiiihuang
*/
public class MySingleLinkedList {
//把節(jié)點(diǎn)定義成個內(nèi)部類
static class ListNode {
public int val;//節(jié)點(diǎn)的值域
public ListNode next;//下一個節(jié)點(diǎn)的地址
public ListNode(int val) {
this.val = val;
}
}
public ListNode head;//頭節(jié)點(diǎn)
/**
* 頭插法
* @param data
*/
public void addFirst(int data) {
//給插入的數(shù)據(jù)創(chuàng)個節(jié)點(diǎn)
ListNode node = new ListNode(data);
node.next = head;
head = node;
}
/**
* 尾插法
* @param data
*/
public void addLast(int data) {
ListNode node = new ListNode(data);
ListNode cur = head;
if(cur == null) {
head = node;
return;
}
//先找到最后一個節(jié)點(diǎn)
while (cur.next != null) {
cur = cur.next;
}
cur.next = node;
}
/**
* 打印鏈表
*/
public void display() {
ListNode cur = head;
while(cur != null) {
System.out.print(cur.val + " ");
cur = cur.next;
}
System.out.println();
}
/**
* 任意位置插入
* @param index
* @param data
*/
public void addIndex(int index,int data) {
ListNode node = new ListNode(data);
//先判斷插入位置合不合法
if(index < 0 || index > size()){
throw new IndexOutOfBoundsException();
}
if(index == 0) {
addFirst(data);
return;
}
if(index == size()) {
addLast(data);
return;
}
ListNode cur = findIndexSubOne(index);
node.next = cur.next;
cur.next = node;
}
//找到要插入位置的前一個節(jié)點(diǎn)
private ListNode findIndexSubOne(int index) {
ListNode cur = head;
while (index - 1 != 0) {
cur = cur.next;
index--;
}
return cur;
}
/**
* 單鏈表的長度
* @return
*/
public int size() {
ListNode cur = head;
int count = 0;
while (cur != null) {
count++;
cur = cur.next;
}
return count;
}
/**
* 查找單鏈表中是否包含關(guān)鍵字key
* @param key
* @return
*/
public boolean contains(int key) {
ListNode cur = head;
while (cur != null) {
if(cur.val == key) {
return true;
}
cur = cur.next;
}
return false;
}
/**
* 刪除第一次出現(xiàn)關(guān)鍵字為key的節(jié)點(diǎn)
* @param key
*/
public void remove(int key) {
if(head == null) {
return;
}
//單獨(dú)刪除頭節(jié)點(diǎn)
if(head.val == key) {
head = head.next;
return;
}
//找到刪除節(jié)點(diǎn)的前一個
ListNode cur = findRemSubOne(key);
if(cur == null) {
System.out.println("沒有你要刪除的數(shù)字");
return;
}
ListNode rem = cur.next;
cur.next = rem.next;
}
//找到刪除節(jié)點(diǎn)的前一個節(jié)點(diǎn)
private ListNode findRemSubOne(int key) {
ListNode cur = head;
//這里跳過了頭節(jié)點(diǎn)
while (cur.next != null) {
if (cur.next.val == key) {
return cur;
}
cur = cur.next;
}
return null;
}
/**
* 刪除所有值為key的節(jié)點(diǎn)
* @param key
*/
public void removeAllKey(int key) {
ListNode cur = head.next;
ListNode prev = head;
while (cur != null) {
if(cur.val == key) {
prev.next = cur.next;
} else {
prev = cur;
}
cur = cur.next;
}
//刪除頭節(jié)點(diǎn)
if(head.val == key) {
head = head.next;
}
}
/**
* 清除鏈表
*/
public void clear() {
this.head = null;
}
}?雙向?不帶頭?非循環(huán)?鏈表
畫圖看看結(jié)構(gòu)
代碼實(shí)現(xiàn)?
創(chuàng)建節(jié)點(diǎn)內(nèi)部類?
上面有的方法這也有 ????
插入數(shù)據(jù)
--- 頭插法?
鏈表為空時，必須單獨(dú)分情況，因為如果不分會：
運(yùn)行結(jié)果?
--- 尾插法?
?
打印鏈表
和上面一樣?
查找鏈表中是否包含關(guān)鍵字key?
和上面一樣?
?鏈表的長度
和上面一樣
運(yùn)行結(jié)果?
任意位置插入,第一個數(shù)據(jù)節(jié)點(diǎn)為0號下標(biāo)
運(yùn)行結(jié)果
刪除第一次出現(xiàn)關(guān)鍵字為key的節(jié)點(diǎn)
代碼?
頭尾分開來，不然會空指針異常 。
運(yùn)行結(jié)果?
但是上面的代碼還有問題
如果只有一個節(jié)點(diǎn)時，head = head.next; 那此時head 就是 null，那此時再head.prev 就會引起空指針異常?
所以要改成這樣：
刪除所有值為key的節(jié)點(diǎn)
和上面幾乎一致，只有一點(diǎn)不一樣。?
運(yùn)行結(jié)果?
清除鏈表?
最簡單粗暴的?
或者把每一個都置為空?
?
完整代碼
import java.util.List;
/**
* @Author: iiiiiihuang
*/
public class MyLinkedList {
static class ListNode {
private int val;
private ListNode prev;
private ListNode next;
public ListNode(int val) {
this.val = val;
}
}
public ListNode head;
public ListNode last;
/**
* 頭插法
* @param data
*/
public void addFirst(int data){
ListNode node = new ListNode(data);
if(head == null) {
head = node;
last = node;
}else {
node.next = head;
head.prev = node;
head = node;
}
}
/**
* 尾插法
* @param data
*/
public void addLast(int data){
ListNode node = new ListNode(data);
if(head == null) {
head = node;
last = node;
} else {
last.next = node;
node.prev = last;
node = last;
}
}
/**
* 任意位置插入,第一個數(shù)據(jù)節(jié)點(diǎn)為0號下標(biāo)
* @param index
* @param data
*/
public void addIndex(int index,int data){
ListNode node = new ListNode(data);
checkIndex(index);
if(index == 0) {
addFirst(data);
return;
}
if(index == size()) {
addLast(data);
return;
}
ListNode cur = searchIndex(index);
node.prev = cur.prev;
node.next = cur;
cur.prev.next = node;
cur.prev = node;
}
//找到插入位置
private ListNode searchIndex(int index) {
ListNode cur = head;
while (index != 0) {
cur = cur.next;
index--;
}
return cur;
}
//檢查index的位置是否合法
private void checkIndex(int index) {
if(index < 0 || index > size()) {
throw new IndexOutOfBoundsException("位置不合法");
}
}
/**
* 查找關(guān)鍵字key是否在鏈表當(dāng)中
* @param key
* @return
*/
public boolean contains(int key){
ListNode cur = head;
while (cur != null) {
if(cur.val == key) {
return true;
}
cur = cur.next;
}
return false;
}
/**
* 刪除第一次出現(xiàn)關(guān)鍵字為key的節(jié)點(diǎn)
* @param key
*/
public void remove(int key){
ListNode cur = head;
while (cur != null) {
if(cur.val == key) {
//刪除頭節(jié)點(diǎn)
if(cur == head) {
head = head.next;
if(head != null) {
//只有一個節(jié)點(diǎn)時
head.prev = null;
} else {
last = null;
}
} else {
//刪除中間節(jié)點(diǎn) 和 尾巴節(jié)點(diǎn)
if(cur.next != null) {
//刪除中間節(jié)點(diǎn)
cur.prev.next = cur.next;
cur.next.prev = cur.prev;
} else {
cur.prev.next = cur.next;
last = last.prev;
}
}
return;
} else {
cur = cur.next;
}
}
}
/**
* 刪除所有值為key的節(jié)點(diǎn)
* @param key
*/
public void removeAllKey(int key){
ListNode cur = head;
while (cur != null) {
if(cur.val == key) {
//刪除頭節(jié)點(diǎn)
if(cur == head) {
head = head.next;
if(head != null) {
//只有一個節(jié)點(diǎn)時
head.prev = null;
} else {
last = null;
}
} else {
//刪除中間節(jié)點(diǎn) 和 尾巴節(jié)點(diǎn)
if(cur.next != null) {
//刪除中間節(jié)點(diǎn)
cur.prev.next = cur.next;
cur.next.prev = cur.prev;
} else {
cur.prev.next = cur.next;
last = last.prev;
}
}
}
cur = cur.next;
}
}
/**
* 得到鏈表的長度
* @return
*/
public int size(){
ListNode cur = head;
int count = 0;
while (cur != null) {
count++;
cur = cur.next;
}
return count;
}
/**
* 打印鏈表
*/
public void display(){
ListNode cur = head;
while (cur != null) {
System.out.print(cur.val + " ");
cur = cur.next;
}
System.out.println();
}
/**
* 清除鏈表
*/
public void clear(){
ListNode cur = head;
while (cur != null) {
//先記錄下數(shù)據(jù)
ListNode curNext = cur.next;
cur.prev = null;
cur.next = null;
cur = curNext;
}
head = null;
last = null;
}
}?LinkedList的使用
先實(shí)例化一下?
我們之前寫的方法他都有，你只要調(diào)用就好了。???????
LinkedList 的 常見方法?
| 方法 | 解釋 |
| boolean add(E e) | 尾插 e |
| void add(int index, E element) | 將 e 插入到 index 位置 |
| boolean addAll(Collection<? extends E> c) | 尾插 c 中的元素 |
| E remove(int index) | 刪除 index 位置元素 |
| boolean remove(Object o) | 刪除遇到的第一個 o |
| E get(int index) | 獲取下標(biāo) index 位置元素 |
| E set(int index, E element) | 將下標(biāo) index 位置元素設(shè)置為 element |
| void clear() | 清空 |
| boolean contains(Object o) | 判斷 o 是否在線性表中 |
| int indexOf(Object o) | 返回第一個 o 所在下標(biāo) |
| int lastIndexOf(Object o) | 返回最后一個 o 的下標(biāo) |
| List<E> subList(int fromIndex, int toIndex) | 截取部分 list |
LinkedList 的總結(jié)?
1. LinkedList實(shí)現(xiàn)了List接口
2. LinkedList的底層使用了雙向鏈表
3. LinkedList沒有實(shí)現(xiàn)RandomAccess接口，因此LinkedList不支持隨機(jī)訪問
4. LinkedList的任意位置插入和刪除元素時效率比較高，時間復(fù)雜度為O(1)
5. LinkedList比較適合任意位置插入或刪除的場景??文章來源：http://www.zghlxwxcb.cn/news/detail-693996.html
ArrayList和LinkedList的區(qū)別（順序表和鏈表的區(qū)別）（面試題） ?
| 不同點(diǎn) | ArrayList | LinkedList |
| 存儲空間上 | 物理上一定連續(xù) | 邏輯上連續(xù)，但物理上不一定連續(xù) |
| 隨機(jī)訪問 | 支持O(1) （有下標(biāo)） | 不支持：O(N) |
| 頭插 | 需要搬移元素，效率低O(N) | 只需修改引用的指向，時間復(fù)雜度為O(1) |
| 插入 | 空間不夠時需要擴(kuò)容 | 沒有容量的概念 |
| 應(yīng)用場景 | 元素高效存儲+頻繁訪問時 | 任意位置插入和刪除頻繁時 |
╰(*°▽°*)╯╰(*°▽°*)╯╰(*°▽°*)╯╰(*°▽°*)╯╰(*°▽°*)╯完?╰(*°▽°*)╯╰(*°▽°*)╯╰(*°▽°*)╯╰(*°▽°*)╯╰(*°▽°*)╯文章來源地址http://www.zghlxwxcb.cn/news/detail-693996.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)篇】線性表1 --- 順序表、鏈表 （萬字詳解?。。┑奈恼戮徒榻B完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
