前言
一、單鏈表的概念
二、鏈表的創(chuàng)建
2.1鏈表的初始化
2.2 打印鏈表
2.3 獲取鏈表的長度
2.4?判斷鏈表是否為空
三、新增結點
3.1頭插
3.2?指定下標插入
四、刪除結點
4.1 頭刪
4.2 指定下標的刪除
4.3?刪除鏈表中的指定元素
五、單鏈表查找
六、附錄
總代碼
測試代碼
總結
前言
前一小節(jié)內容，我們學習了有關線性表中順序表的有關知識；今天我們將學習有關單鏈表的有關知識；單鏈表也是數據結構中的一大重點；今天就讓我們來學習它吧！?。。。。。。。。?/strong>
一、單鏈表的概念
鏈表是一種物理存儲結構上非連續(xù)、非順序的存儲結構，
整個鏈表就是通過對各個結點地址的鏈式儲存來實現(xiàn)的?。（鏈表就是由一個一個結點所組成的）
舉例說明：
鏈表的結構有點類似于火車，火車的每一節(jié)車廂都由插銷，和鉤子鏈接起來；
那么怎么這一個一個的結點是怎樣鏈接起來呢？
在Java中他是通過引用所指向的地址來鏈接起來的。
什么意思呢？
就是說鏈表的每一個結點元素都分為連兩部分，一部分用來儲存數值，另一部分來儲存地址。
儲存的是誰的地址呀！就是下一個結點的地址。
比如說在鏈表中有三個結點，那么他們之間的關系是這樣的：
既然說了，鏈表是由一個一個的結點組成的，那么在Java中結點是怎樣定義的呢？
我們從上面也可以發(fā)現(xiàn)在每一個結點都是一個獨立的小個體，我們不妨把他抽象為一個內部類，并放到單鏈表這個類的里面。這樣我們就可以在單鏈表這個類里面使用我們結點這個小個體，并嘗試把它串起來。
注意：本篇文章所討論的單鏈表用到了兩個文件：
- 單鏈表的構建文件MyLinkList.java
- 單鏈表的測試文件hLinkListTest.java
二、鏈表的創(chuàng)建
代碼：
public class MyLinkList {
ListNode head = null; // 聲明鏈表中的頭結點
//創(chuàng)建單鏈表結構，將鏈表的每一個結點都定義成一個內部類
public class ListNode {
public int val; // 該結點的數值域，儲存該結點的數值
public ListNode next; // 該結點的next域，儲存的是下一個結點的地址，兩個結點間正是通過next域產生關聯(lián)
public ListNode(int val) { // 構造方法，給新生成的結點賦值，同時next默認為null
this.val = val;
}
}
}如圖所示：我們定義了一個MyLinkList（單鏈表）類，同時在該類中還定義了一個內部類（結點類）。這樣就創(chuàng)建了一個基本的鏈表結構。
但光這樣肯定是不行的，我們對鏈表有一些基本的操作方法如下：
// 鏈表初始化
public ListNode listInit() { }
// 打印鏈表
public void linkedListPrint() { }
// 獲取鏈表長度
public int getSize() { return -1; }
//判斷該鏈表是否為空
private void isEmpty() { }2.1鏈表的初始化
首先我們要做的就是對我們的鏈表進行初始化的操作，那么怎么初始化呢？
當然是創(chuàng)建一些結點，并在每一個結點中都把下一個結點的地址給儲存起來，然后相互鏈接起來的呀！
代碼示例：
// 鏈表初始化 public ListNode listInit() { Scanner in = new Scanner(System.in); System.out.print("請輸入你要構建的鏈表的初始長度："); int n = in.nextInt(); System.out.print("請輸入鏈表第1個元素的值："); int firstVal = in.nextInt(); // this.head = new ListNode(firstVal); // 創(chuàng)建鏈表的第一個結點，將我們鏈表的頭結點引用head指向鏈表的第一個結點 ListNode cur = head; // 創(chuàng)建一個引用cur去完成鏈表的初始化(頭節(jié)點是整個鏈表的靈魂,不能直接使用,避免丟失鏈表) for (int i = 1; i < n; i++) { System.out.print("請輸入鏈表第" + (i + 1) + "個元素的值："); int val = in.nextInt(); ListNode node = new ListNode(val); // 當前結點的next域存放的是對下一個結點的引用變量node，node儲存的就是下一個結點的地址 cur.next = node; // 當前結點的next域存放的是對下一個結點的引用變量node cur = node; // 將當前結點移向下一個結點 } return this.head; // 返回該鏈表的頭結點 }
解析：
如圖所示：
對于結點的鏈接：用的就是cur這個結點引用變量;
當我們的cur引用也指向第一個結點后，cur.next代表的就是第一個結點的next域，只要next域里儲存了下一個結點的地址，這兩個結點就鏈接起來了。?
那要是再來個第三個結點node呢？??
不要著急，我們只需要讓cur = cur.next，cur.next = node就完成了結點間的鏈接;
當cur = cur.next 后，引用變量cur現(xiàn)在所引用的就變成了第二個結點，
那么cur.next = node的作用就是將第三個結點的地址儲存到了第二個結點的next域里。
接下第四、第五個結點也大致是這樣的操作;?
你可以會問：為啥非得要再定義一個結點的引用變量cur呢？我之間用head頭結點引用來不斷的改變指向，完成結點間的鏈接，不可以嗎？
可以是可以，但你有沒有想過，如果用head來操作結點的化，你在初始化鏈表后head還指向頭節(jié)點嗎？你還能找到頭結點嗎？
2.2 打印鏈表
// 打印鏈表 public void linkedListPrint() { ListNode cur = head; // 創(chuàng)建一個引用cur去完成鏈表的遍歷打印(頭節(jié)點是整個鏈表的靈魂,不能直接使用,避免丟失鏈表) while (cur != null) { System.out.print(cur.val + " "); // cur.val表示的就是當前結點的數值 cur = cur.next; // 打印完了當前結點，cur繼續(xù)指向下一個結點，完成對下一個結點的打印 } System.out.println(); }
2.3 獲取鏈表的長度
// 打印鏈表 public void linkedListPrint() { ListNode cur = head; // 創(chuàng)建一個引用cur去完成鏈表的遍歷打印(頭節(jié)點是整個鏈表的靈魂,不能直接使用,避免丟失鏈表) while (cur != null) { System.out.print(cur.val + " "); // cur.val表示的就是當前結點的數值 cur = cur.next; // 打印完了當前結點，cur繼續(xù)指向下一個結點，完成對下一個結點的打印 } System.out.println(); }
2.4?判斷鏈表是否為空
/** * 判斷該鏈表是否為空 * 為空就拋出異常，終止程序 */ private void isEmpty() { // 判斷鏈表是否為空，只是該類中使用，所有 if (head == null) { System.out.println("該鏈表為空?。。?); throw new NullPointerException(); // 如果拋出的是 RunTimeException 或者 RunTimeException 的子類，則可以不用處理，直接交給JVM來處理 //異常一旦拋出，其后的代碼就不會執(zhí)行，相當于就直接return了 } }
好了，現(xiàn)在我們就得到一個基本的鏈表了；
那么接下來就是對鏈表的操作了，那么一起來看看對鏈表都有那些操作吧！
// 在在鏈表頭插入元素 public void addHead(int val) { } //在鏈表的指定下標中插入元素 public void addIndex(int index, int val) { } // 刪除頭節(jié)點 public void deleteHead() { } //刪除指定下標的元素 public void deleteIndex(int index) { } // 刪除鏈表中所有數值是key的元素 public void deleteKey(int key) { } // 判斷元素key是否在當前鏈表中 public boolean contains(int key) { return false; }
三、新增結點
3.1頭插
// 在在鏈表頭插入元素 public void addHead(int val) { ListNode node = new ListNode(val); // 新插入的結點node node.next = head; // 直接將該結點node變成新的頭結點 head = node; }
3.2?指定下標插入
/** * 在鏈表的指定下標中插入元素 * @param index 所指定的下標 * @param val 元素值 */ public void addIndex(int index, int val) { if (index < 0 || index > getSize()) { // 注意這里index == getSize也是可以的，此時相當于是在鏈表的結尾新增一個元素 System.out.println("index下標不合法"); return; } ListNode node = new ListNode(val); // 要新增的那個結點node if (index == 0) { // 當新增的是頭結點的時候 addHead(val); return; } ListNode cur = head; for (int i = 0; i < index - 1; ++i) { // 這種情況包含了新增尾結點的時候 cur = cur.next; // 通過循環(huán)，讓cur指向—>新增指定下標所對應的元素的前一個元素 } node.next = cur.next; // 把該結點插入鏈表，且放到指定下標中，從后往前走，先將node結點指向下一個結點 cur.next = node; }舉例說明：
比如現(xiàn)在我們想在2下標插入我們新建的結點node，那么我們首先要找到要插入的結點的前一個結點->也就是下標為1的那個結點
然后呢??
你可能會說：這不就簡單了！直接下標為1的結點的next儲存新建的結點node的地址：0x7777，然后新建的node結點再指向我們原來下標為2的結點不就行了嗎？
這樣真的可以嗎？一起來看看吧！
上面所說的就是這樣的偽代碼：
下標為1的結點.next = node; node.next = 下標為2的結點; 但這有一個問題： 首先在一開始的鏈表中存在這樣的關系： 下標為1的結點.next = 下標為2的結點 那么就在上面的偽代碼中node.next = 下標為2的結點； 就相等于是：node.next = 下標為1的結點.next; 但問題是此時的：下標為1的結點.next = node; 即node.next = node;這合理嗎？不合理，所以我們要從后向前走 就是： node.next = 下標為2的結點; 下標為1的結點.next = node;所以說上面我們的那個想法是不合適的；
正確想法：
四、刪除結點
4.1 頭刪
// 刪除頭節(jié)點 public void deleteHead() { isEmpty(); // 檢查一下鏈表是否為空，為空的化就會拋出異常來終止程序 // 如果head頭節(jié)點不是鏈表的最后一個元素時，直接將head的下一個結點變成新的頭結點，原來的head頭結點就被系統(tǒng)自動回收了 if (head.next != null) { this.head = this.head.next; } else this.head = null; // 當head結點是鏈表的最后一個元素時 }
4.2 指定下標的刪除
在鏈表中，想要刪除一個結點其實就是讓該結點從鏈表中分離出來（沒有其他任何的結點指向他?）
比如：
我們想刪除1下標的結點，只需要找到1下標的前一個結點，也就是0下標。然后將0下標的next域里不再儲存1下標的結點地址，而改成儲存1下標的下一個結點->2下標的結點地址。這樣就相等于1下標的結點被孤立下來了（就相等于是刪除了）
/** * 刪除指定下標的元素 * @param index 要刪除的指定元素下標 */ public void deleteIndex(int index) { isEmpty(); // 檢查一下鏈表是否為空，為空的化就會拋出異常來終止程序 if (index < 0 || index >= getSize()) { // 注意此時index不能等于getSize因為是刪除不是新增，下標index最大是getSize - 1 System.out.println("要刪除的下標不合法！刪除失?。?！"); return; // 直接返回 } if (index == 0) { deleteHead(); // 當index等于0時，相當于是刪除的是頭節(jié)點 return; } ListNode cur = head; // 創(chuàng)建一個引用cur去完成循環(huán)(頭節(jié)點是整個鏈表的靈魂,不能直接使用,避免丟失鏈表) // 通過循環(huán)，讓cur指向—>要刪除元素的前一個元素 for (int i = 0; i < index - 1; ++i) { // 注意這里不能是i < index; 如果是i < index的話，cur就指向當前要刪除的那個元素了 cur = cur.next; } cur.next = cur.next.next; }圖片說明：
4.3?刪除鏈表中的指定元素
// 刪除鏈表中所有數值是key的元素 public void deleteKey(int key) { isEmpty(); // 檢查一下鏈表是否為空，為空的化就會拋出異常來終止程序 while (this.head.val == key && head != null) { // 當 head.val == key,相當于刪除頭節(jié)點 deleteHead(); // 因為是刪除鏈表中所有數值是key的元素，所以刪除一個后不能直接返回，還要繼續(xù)遍歷 // 處理特殊情況，當鏈表的的最后一個元素被刪除時 if (head == null) { return; // 直接return就好，此時head為空，如果再進行this.head.val == key的判斷就會發(fā)生空指針異常 } } ListNode cur = head; // 創(chuàng)建一個引用cur去完成鏈表的遍歷(頭節(jié)點是整個鏈表的靈魂,不能直接使用,避免丟失鏈表) while (cur.next != null) { if (cur.next.val == key) { cur.next = cur.next.next; // 包含了刪除尾結點的情況 } else { cur = cur.next; // cur引用指向下一個結點，以此來完成遍歷鏈表 } }
?
五、單鏈表查找：
/** * 判斷元素key是否在當前鏈表中 * @param key * @return 在鏈表中返回true,不在返回false */ public boolean contains(int key) { ListNode cur = this.head; while (cur != null) { if (cur.val == key) { return true; } else { cur = cur.next; } } return false; }
六、附錄
總代碼
//shift+回車，光標在任意位置都能換到下一行 // crl + z返回上一步，如果自己不小心誤刪了代碼可以用這個快捷鍵找回剛才誤刪的代碼 //import java.util.List; import java.util.Scanner; /** * 實現(xiàn)單鏈表的代碼 */ //變量名,方法名首字母小寫,如果名稱由多個單詞組成,除首字母外的每個單詞的首字母都要大寫. // 包名小寫 public class MyLinkList { ListNode head = null; // 聲明鏈表中的頭結點 //創(chuàng)建單鏈表結構，將鏈表的每一個結點都定義成一個內部類 public class ListNode { public int val; // 該結點的數值域，儲存該結點的數值 public ListNode next; // 該結點的next域，儲存的是下一個結點的地址，兩個結點間正是通過next域產生關聯(lián) public ListNode(int val) { // 構造方法，給新生成的結點賦值，同時next默認為null this.val = val; } } // 鏈表初始化 public ListNode listInit() { Scanner in = new Scanner(System.in); System.out.print("請輸入你要構建的鏈表的初始長度："); int n = in.nextInt(); System.out.print("請輸入鏈表第1個元素的值："); int firstVal = in.nextInt(); // this.head = new ListNode(firstVal); // 創(chuàng)建鏈表的第一個結點，將我們鏈表的頭結點指向鏈表的第一個結點 ListNode cur = head; // 創(chuàng)建一個引用cur去完成鏈表的初始化(頭節(jié)點是整個鏈表的靈魂,不能直接使用,避免丟失鏈表) for (int i = 1; i < n; i++) { System.out.print("請輸入鏈表第" + (i + 1) + "個元素的值："); int val = in.nextInt(); ListNode node = new ListNode(val); cur.next = node; cur = node; } return this.head; // 返回該鏈表的頭結點 } // 打印鏈表 public void linkedListPrint() { ListNode cur = head; // 創(chuàng)建一個引用cur去完成鏈表的遍歷打印(頭節(jié)點是整個鏈表的靈魂,不能直接使用,避免丟失鏈表) while (cur != null) { System.out.print(cur.val + " "); // cur.val表示的就是當前結點的數值 cur = cur.next; // 打印完了當前結點，cur繼續(xù)指向下一個結點，完成對下一個結點的打印 } System.out.println(); } // 獲取鏈表長度 public int getSize() { int count = 0; ListNode cur = this.head; while (cur != null) { count++; cur = cur.next; } return count; } /** * 判斷該鏈表是否為空 * 為空就拋出異常，終止程序 */ private void isEmpty() { // 判斷鏈表是否為空，只是該類中使用，所有 if (head == null) { System.out.println("該鏈表為空?。。?); throw new NullPointerException(); // 如果拋出的是 RunTimeException 或者 RunTimeException 的子類，則可以不用處理，直接交給JVM來處理 //異常一旦拋出，其后的代碼就不會執(zhí)行，相當于就直接return了 } } // 在在鏈表頭插入元素 public void addHead(int val) { ListNode node = new ListNode(val); node.next = head; head = node; } /** * 在鏈表的指定下標中插入元素 * @param index 所指定的下標 * @param val 元素值 */ public void addIndex(int index, int val) { if (index < 0 || index > getSize()) { // 注意這里index == getSize也是可以的，此時相當于是在鏈表的結尾新增一個元素 System.out.println("index下標不合法"); return; } ListNode node = new ListNode(val); // 要新增的那個結點node if (index == 0) { // 當新增的是頭結點的時候 addHead(val); return; } ListNode cur = head; for (int i = 0; i < index - 1; ++i) { // 這種情況包含了新增尾結點的時候 cur = cur.next; // 通過循環(huán)，讓cur指向—>新增指定下標所對應的元素的前一個元素 } node.next = cur.next; // 把該結點插入鏈表，且放到指定下標中，從后往前走，先將node結點指向下一個結點 cur.next = node; } // 刪除頭節(jié)點 public void deleteHead() { isEmpty(); // 檢查一下鏈表是否為空，為空的化就會拋出異常來終止程序 if (head.next != null) { this.head = this.head.next; } else this.head = null; // 當head結點是鏈表的最后一個元素時 } /** * 刪除指定下標的元素 * @param index 要刪除的指定元素下標 */ public void deleteIndex(int index) { isEmpty(); // 檢查一下鏈表是否為空，為空的化就會拋出異常來終止程序 if (index < 0 || index >= getSize()) { // 注意此時index不能等于getSize因為是刪除不是新增，下標index最大是getSize - 1 System.out.println("要刪除的下標不合法！刪除失敗?。?); return; // 直接返回 } if (index == 0) { deleteHead(); // 當index等于0時，相當于是刪除的是頭節(jié)點 return; } ListNode cur = head; // 創(chuàng)建一個引用cur去完成循環(huán)(頭節(jié)點是整個鏈表的靈魂,不能直接使用,避免丟失鏈表) // 通過循環(huán)，讓cur指向—>要刪除元素的前一個元素 for (int i = 0; i < index - 1; ++i) { // 注意這里不能是i < index; 如果是i < index的話，cur就指向當前要刪除的那個元素了 cur = cur.next; } cur.next = cur.next.next; } // 刪除鏈表中所有數值是key的元素 public void deleteKey(int key) { isEmpty(); // 檢查一下鏈表是否為空，為空的化就會拋出異常來終止程序 while (this.head.val == key && head != null) { // 當 head.val == key,相當于刪除頭節(jié)點 deleteHead(); // 因為是刪除鏈表中所有數值是key的元素，所以刪除一個后不能直接返回，還要繼續(xù)遍歷 // 處理特殊情況，當鏈表的的最后一個元素被刪除時 if (head == null) { return; // 直接return就好，此時head為空，如果再進行this.head.val == key的判斷就會發(fā)生空指針異常 } } ListNode cur = head; // 創(chuàng)建一個引用cur去完成鏈表的遍歷(頭節(jié)點是整個鏈表的靈魂,不能直接使用,避免丟失鏈表) while (cur.next != null) { if (cur.next.val == key) { cur.next = cur.next.next; // 包含了刪除尾結點的情況 } else { cur = cur.next; // cur引用指向下一個結點，以此來完成遍歷鏈表 } } } /** * 判斷元素key是否在當前鏈表中 * @param key * @return 在鏈表中返回true,不在返回false */ public boolean contains(int key) { ListNode cur = this.head; while (cur != null) { if (cur.val == key) { return true; } else { cur = cur.next; } } return false; } }
測試代碼
/** * 對單鏈表進行測試的代碼 */ public class LinkListTest { public static void main(String[] args) { MyLinkList myLinkList = new MyLinkList(); // 實例化一個鏈表對象 // 鏈表的初始化 myLinkList.listInit(); System.out.print("初始化鏈表后，鏈表的第一次打?。?); myLinkList.linkedListPrint(); System.out.println("==============="); myLinkList.addHead(1111); System.out.print("頭插結點1111后，鏈表的第二次打?。?); myLinkList.linkedListPrint(); myLinkList.addIndex(2, 2222); System.out.print("再指定下標2出插入新結點2222后，鏈表的第三次打?。?); myLinkList.linkedListPrint(); System.out.println("================"); myLinkList.deleteIndex(2); System.out.print("刪除指定下標2的結點2222后，鏈表的第四次打?。?); myLinkList.linkedListPrint(); myLinkList.deleteHead(); System.out.print("刪除頭節(jié)點后，鏈表的第五次打印："); myLinkList.linkedListPrint(); myLinkList.deleteKey(2); System.out.print("刪除鏈表中所有值是2的結點后，鏈表的第六次打?。?); myLinkList.linkedListPrint(); System.out.print("此時的鏈表長度為："); System.out.println(myLinkList.getSize()); } }
測試結果：
總結
本節(jié)內容我們學習了有關鏈表中有關的各種操作，如插入刪除等等；讓我們堆鏈表有了更深刻的學習和認識；文章來源：http://www.zghlxwxcb.cn/news/detail-414007.html
文章來源地址http://www.zghlxwxcb.cn/news/detail-414007.html
到了這里，關于【數據結構初階】第四節(jié).鏈表詳講的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！
