目錄
?一.什么是鏈表
二.鏈表的實現(xiàn)
節(jié)點的插入
頭插法
尾插法
指定位置插入
節(jié)點的刪除
刪除第一次出現(xiàn)的關(guān)鍵字節(jié)點
刪除所有關(guān)鍵字節(jié)點
節(jié)點的查找
鏈表的清空
鏈表的長度
前言：在上一篇文章中，我們認(rèn)識了線性數(shù)據(jù)結(jié)構(gòu)中的順序表，而本篇文章則是介紹線性數(shù)據(jù)結(jié)構(gòu)中的另一個結(jié)構(gòu)——鏈表
想要了解順序表相關(guān)操作的知識可以查看這篇文章：
圖文詳解順序表的各種操作
?一.什么是鏈表
鏈表是一種數(shù)據(jù)結(jié)構(gòu)，它由一系列節(jié)點（node）構(gòu)成，每個節(jié)點中包含了數(shù)據(jù)（data）和指向下一個節(jié)點的指針（next）。鏈表中的節(jié)點可以在內(nèi)存中任何位置，它們通過指針鏈接在一起，形成一個鏈?zhǔn)浇Y(jié)構(gòu)。鏈表相對于數(shù)組的優(yōu)點在于它可以動態(tài)地增加、刪除節(jié)點，而不需要移動大量的數(shù)據(jù)。鏈表的缺點是訪問元素時需要遍歷整個鏈表，效率較低。
二.鏈表的實現(xiàn)
鏈表由不同的節(jié)點相互串起來，每個節(jié)點由倆個部分組成，一個是數(shù)據(jù)域，用來放具體是數(shù)值內(nèi)容，另一個是指針域，用來存放下一個節(jié)點的地址信息，彼此之間就像是用鏈條串起來一樣，就像下圖展示的這樣，所以稱之為鏈表。
對于上圖這樣的結(jié)構(gòu)，我們可以如下定義一個鏈表，將鏈表作為一個類，并且在這個類中有一個內(nèi)部類專門存儲每一個節(jié)點的數(shù)據(jù)結(jié)構(gòu)，還有一個頭節(jié)點單獨定義來記錄鏈表的起始位置
public class MyLinkList{
//節(jié)點的數(shù)據(jù)結(jié)構(gòu)
static class ListNode{
public int val;
public ListNode next;
}
//鏈表的屬性
public ListNode head;//記錄鏈表的第一個元素：頭節(jié)點
}
對一個鏈表，它應(yīng)該完成以下這些功能，我們將這些功能抽象出一個接口，然后通過這個接口去實現(xiàn)一個真正的鏈表
public interface Ilist {
//頭插
void addFirst(int data);
//尾插
void addLast(int data);
//指定插入
void addIndex(int index,int data);
//查詢是否存在
boolean contains(int key);
//刪除節(jié)點
void remove(int key);
//刪除所有與目標(biāo)相同的節(jié)點
void removeAllKey(int key);
//得到鏈表的長度
int size();
//清空鏈表
void clear();
//輸出鏈表的所有信息
void display();
}節(jié)點的插入
我們將節(jié)點的插入分為三種：
- 頭部插入：將節(jié)點插入到鏈表的最前面
- 尾部插入：將節(jié)點插入到鏈表的最后面
- 指定位置插入：將節(jié)點插入到鏈表的中間
頭插法
如圖，我們準(zhǔn)備對于剛才的鏈表進(jìn)行插入
我們這里分倆個步驟進(jìn)行操作：
- 將新節(jié)點指向頭節(jié)點
- 更新頭節(jié)點的位置
我們更改要添加節(jié)點的指針域，讓它指向新的節(jié)點?
在指向完成后，我們新添加的節(jié)點就已經(jīng)是鏈表的第一個節(jié)點了，所以我們要更新頭節(jié)點的信息，記錄新節(jié)點才是第一個節(jié)點
這樣我們就完成了頭部插入節(jié)點，具體代碼實現(xiàn)如下，先生成一個節(jié)點，然后按照上面圖示的思路進(jìn)行操作
//頭插法
public void addFirst(int data) {
ListNode newNode = new ListNode(data);
newNode.next = this.head;
this.head = newNode;
}尾插法
尾插法是將節(jié)點插入到鏈表的末尾，但是我們是并沒有記錄末尾節(jié)點的位置的，所以如果要使用尾插法的話就需要先找到尾部節(jié)點。那我們只需要根據(jù)最后一個節(jié)點特征進(jìn)行遍歷找到最后一個節(jié)點就可以了，而最后一個節(jié)點最大的特征就是，它只有數(shù)據(jù)域內(nèi)有信息，指針域里面是空。如果鏈表為空的話，那我們直接在頭節(jié)點之后添加就可以，整體流程如下：
整體代碼實現(xiàn)如下，先判斷是否為空鏈表，為空就直接在頭節(jié)點之后添加，不為空就遍歷找到最后一個節(jié)點，然后更改指針域內(nèi)容，添加新節(jié)點
//尾插法
public void addLast(int data) {
//當(dāng)鏈表為空的時候，直接將節(jié)點插入到頭節(jié)點的位置
ListNode newNode = new ListNode(data);
if (head == null) {
head = newNode;
}else{
ListNode cur = head;
while (cur.next != null){
cur = cur.next;
}
//找到最后一個節(jié)點
cur.next = newNode;
//newNode.next = null;//默認(rèn)新節(jié)點的指針域為空，所以這里可以不寫這一行代碼
}
}指定位置插入
在中間位置插入是最麻煩的，原因就在于我們不能立馬獲取到想要插入位置的信息，我們需要先進(jìn)行判斷，如果輸入位置是在最前面，那就可以使用頭插，如果是最后就使用尾插。在得知輸入位置在鏈表中間后，我們就需要先找到這個位置前后的節(jié)點的信息，如下圖，假如我們要插入的位置是第三個位置，那就需要知道第二個位置和第三個位置的信息，當(dāng)我們找到了后可以分倆布進(jìn)行操作（順序不能更改）：
- 先讓節(jié)點指向后面的節(jié)點
- 再讓前面的節(jié)點指向插入節(jié)點
第一步，讓插入節(jié)點指向后面的節(jié)點
第二步，將前面的節(jié)點指向插入的節(jié)點
我們可以通過代碼來實現(xiàn)這段過程，先是進(jìn)行合法性的判斷，然后是針對性的插入
//指定位置添加
public void addIndex(int index, int data) {
if(index < 0 || index > size()) {
//這里不一定非要拋出自定義異常，大家可以更具喜好自行設(shè)置
throw new IndexException("index不合法: "+index);
}
//如果輸入的位置在最前面就進(jìn)行頭插
if (index == 0)
addFirst(data);
//如果輸入的位置在鏈表最后就進(jìn)行尾插
if (index == size())
addLast(data);
//輸入位置在中間，就先找到這個節(jié)點的位置
ListNode cur = searchPrevIndex(index);
ListNode newNode = new ListNode(data);
//這倆步是順序非常重要
newNode.next = cur.next;
cur.next = newNode;
}
//找到位置對應(yīng)的節(jié)點
private ListNode searchPrevIndex(int index) {
ListNode cur = head;
int count = 0;
while (count != index-2) {
cur = cur.next;
count++;
}
return cur;
}節(jié)點的刪除
對于節(jié)點是刪除相當(dāng)于插入簡單了很多，我們依舊是分為倆種方式進(jìn)行刪除，一種是只刪除第一次出現(xiàn)的節(jié)點，另一種是刪除全部想要刪除的節(jié)點。
刪除第一次出現(xiàn)的關(guān)鍵字節(jié)點
我們依舊是用初始的鏈表進(jìn)行舉例，假如我們想要刪除第三個節(jié)點
第一步，我們直接更改要刪除節(jié)點的前面節(jié)點的指針域，讓它指向要刪除的節(jié)點后的節(jié)點
第二步，我們將要刪除的節(jié)點的指針域置為空
這倆步的順序同樣也不能錯，因為一旦我們先將要刪除的節(jié)點的指針域置為空，我們就無法再找到后面的節(jié)點了，鏈表就相當(dāng)于斷開了
我們封裝一個函數(shù)用來找到要刪除節(jié)點的前一個節(jié)點，然后通過它再刪除目標(biāo)節(jié)點
//刪除第一個關(guān)鍵字
public void remove(int key) {
if (head == null)
return;
if (head.val == key){
head = head.next;
return;
}
//查找val等于key的節(jié)點
ListNode cur = findKey(key);
if (cur == null){
System.out.println("查無此元素，無法刪除");
return;
}
ListNode delNode = cur.next;
cur.next = delNode.next;
//cur.next =cur.next.next;
}
//找到要刪除的元素的前一個節(jié)點
private ListNode findKey(int key){
ListNode cur = head;
while (cur.next != null){
if (cur.next.val != key) {
cur = cur.next;
}else{
return cur;
}
}
return null;
}刪除所有關(guān)鍵字節(jié)點
與剛才不同的是，刪除一個節(jié)點是先找到前驅(qū)節(jié)點，然后通過這個前驅(qū)節(jié)點進(jìn)行操作，而要刪除所有的關(guān)鍵字節(jié)點，則是對整個鏈表進(jìn)行遍歷，一旦是關(guān)鍵字，那我們就進(jìn)行覆蓋刪除，這里就不再畫圖了，畢竟整個流程相當(dāng)于多執(zhí)行幾次單個刪除操作
//刪除所有的關(guān)鍵字
public void removeAllKey(int key) {
if(head == null) {
return;
}
ListNode prev = head;
ListNode cur = head.next;
while (cur != null) {
if(cur.val == key) {
prev.next = cur.next;
cur = cur.next;
}else {
prev = cur;
cur = cur.next;
}
}
//除了頭節(jié)點都刪除完成了
if(head.val == key) {
head = head.next;
}
}節(jié)點的查找
節(jié)點的查找就是遍歷整個鏈表，如果找到就返回true，沒有找到就返回false
//查找是否存在
public boolean contains(int key) {
ListNode cur = head;
while (cur != null){
if (cur.val == key)
return true;
cur = cur.next;
}
return false;
}鏈表的清空
當(dāng)鏈表的頭節(jié)點為空，我們就視為鏈表被清空了
//清空鏈表
public void clear() {
head = null;
}鏈表的長度
遍歷整個鏈表，使用計算器進(jìn)行累加記錄節(jié)點個數(shù)，然后返回就可以文章來源：http://www.zghlxwxcb.cn/news/detail-754855.html
//求鏈表的長度
public int size() {
int count =0;
ListNode cur = head;
while (cur != null){
count++;
cur = cur.next;
}
return count;
}?
?本次的分享就到此為止了，希望我的分享能給您帶來幫助，也歡迎大家三連支持，你們的點贊就是博主更新最大的動力！
如有不同意見，歡迎評論區(qū)積極討論交流，讓我們一起學(xué)習(xí)進(jìn)步！
有相關(guān)問題也可以私信博主，評論區(qū)和私信都會認(rèn)真查看的，我們下次再見文章來源地址http://www.zghlxwxcb.cn/news/detail-754855.html
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)：圖文詳解單鏈表的各種操作（頭插法，尾插法，任意位置插入，刪除節(jié)點，查詢節(jié)點，求鏈表的長度，清空鏈表）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
