【威哥說】威哥在此和小伙伴們道歉，本來計(jì)劃昨天早上給大家分享的視頻娄猫，因?yàn)槭韬龀霈F(xiàn)了遺漏荞估，導(dǎo)致大家沒有及時(shí)學(xué)習(xí)，今天不但要給大家補(bǔ)齊視頻稚新，同時(shí)我還和磨礪營的另外一個(gè)小伙伴甘愿自罰勘伺，以表示對大家的歉意。希望相信我以及磨礪營的小伙伴們褂删，能夠?qū)W習(xí)到更多的知識飞醉。（懲罰內(nèi)容，每人罰100個(gè)俯臥撐，如圖）更多技術(shù)干貨請關(guān)注磨礪營官網(wǎng)
【正文】
鏈表：鏈表是一種物理存儲單元上非連續(xù)缅帘、非順序的存儲結(jié)構(gòu)轴术，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的。鏈表由一系列結(jié)點(diǎn)（鏈表中每一個(gè)元素稱為結(jié)點(diǎn)）組成钦无，結(jié)點(diǎn)可以在運(yùn)行時(shí)動態(tài)生成逗栽。每個(gè)結(jié)點(diǎn)包括兩個(gè)部分：一個(gè)是存儲數(shù)據(jù)元素的數(shù)據(jù)域，另一個(gè)是存儲下一個(gè)結(jié)點(diǎn)地址的指針域失暂。
這是百度上的回答彼宠，那么通俗點(diǎn)來說，就是鏈表是一個(gè)不連續(xù)弟塞，沒有順序的存儲結(jié)構(gòu)凭峡。他們之間的連接是通過本節(jié)點(diǎn)中記錄下一個(gè)節(jié)點(diǎn)的地址來保持關(guān)系的。就像鐵鏈决记，每一環(huán)扣著每一環(huán)摧冀，所以名稱也是由此而來。
那么解釋看懂了系宫，我們?nèi)绾稳?shí)實(shí)在在的將這個(gè)存儲結(jié)構(gòu)在我們的代碼中體現(xiàn)出來呢索昂。接下來，跟著文章的思路走扩借。
首先我們要搞清楚椒惨，我們此處的存值是通過節(jié)點(diǎn)進(jìn)行存儲，所以我們需要一個(gè)節(jié)點(diǎn)對象往枷，那么通過在一個(gè)節(jié)點(diǎn)中保存下一個(gè)節(jié)點(diǎn)對象，所以我們要在一個(gè)節(jié)點(diǎn)中封裝下一個(gè)節(jié)點(diǎn)的引用凄杯，并且我們是通過節(jié)點(diǎn)中封裝屬性的方法對數(shù)據(jù)進(jìn)行存儲的错洁，所以此處的節(jié)點(diǎn)對象我們可以命名為：
private class Node{
private int data; ?//節(jié)點(diǎn)要存儲的數(shù)據(jù)
private Node next; ?//節(jié)點(diǎn)內(nèi)部的節(jié)點(diǎn)（下一個(gè)節(jié)點(diǎn)）
//構(gòu)造方法完成初始化工作
public Node(int data){
this.data = data;
}
//定義getter 和 setter 方法
public void setData(int data){
this.data = data;
}
public int getData(){
return data;
}
}
此處我們使用內(nèi)部類的方式來講節(jié)點(diǎn)存儲在節(jié)點(diǎn)管理類中，也就是說將節(jié)點(diǎn)類封裝到我們的NodeManager中戒突，這樣對外就不直接暴露根本的節(jié)點(diǎn)類：
class NodeManager{
//此處保存一個(gè)根節(jié)點(diǎn)
private Node root;
private class Node{
private int data; ?//節(jié)點(diǎn)要存儲的數(shù)據(jù)
private Node next; ?//節(jié)點(diǎn)內(nèi)部的節(jié)點(diǎn)（下一個(gè)節(jié)點(diǎn)）
//構(gòu)造方法完成初始化工作
public Node(int data){
this.data = data;
}
//定義getter 和 setter 方法
public void setData(int data){
this.data = data;
}
public int getData(){
return data;
}
}
}
添加方法：
首先屯碴，我們需要添加方法，此時(shí)這個(gè)方法是管理類中的膊存，
//添加節(jié)點(diǎn)
public void add(int data){
//判斷如果根節(jié)點(diǎn)為空导而，就存儲在根節(jié)點(diǎn)中
if(root==null){
//新建一個(gè)節(jié)點(diǎn)（將要存儲的數(shù)據(jù)存入進(jìn)去）
root = new Node(data);
}else{
//此時(shí)我交給內(nèi)部類去完成添加
root.addNode(data);
}
}
現(xiàn)在進(jìn)入我們的節(jié)點(diǎn)內(nèi)部的添加方法：
//Node內(nèi)部的添加節(jié)點(diǎn)
public void addNode(int data){
//此處的this，表示當(dāng)前對象隔崎，注意今艺，誰調(diào)用此方法，this就表示誰爵卒，如果這里的下一個(gè)節(jié)點(diǎn)為空虚缎，就將數(shù)據(jù)通過構(gòu)造方法存儲起來
if(this.next==null){
this.next = new Node(data);
}else{
//此處使用了遞歸算法，如果檢測到下一個(gè)節(jié)點(diǎn)有數(shù)據(jù)钓株，就是用下一個(gè)節(jié)點(diǎn)的addNode方法实牡，這時(shí)候陌僵，就可以繼續(xù)我們的處理邏輯
this.next.addNode(data);
}
}
刪除方法：
首先，外部管理類中的刪除方法创坞，注意此處刪除有開發(fā)者可能也不太理解碗短，這里要注意的是，這里我們可以直接指定本節(jié)點(diǎn)中指定的下一個(gè)節(jié)點(diǎn)的引用题涨，這樣遍歷時(shí)就會直接略過這個(gè)沒有記錄的這個(gè)數(shù)據(jù)：
//刪除節(jié)點(diǎn)
public void del(int data){
if(root.getData()==data){
root = root.next;
}else{
//進(jìn)入到節(jié)點(diǎn)內(nèi)部類的刪除方法
root.delNode(data);
}
}
我們看看節(jié)點(diǎn)內(nèi)部的刪除方法偎谁，同樣的我們需要使用遞歸來進(jìn)行判斷，判斷到符合的節(jié)點(diǎn)携栋，直接執(zhí)行刪除操作：
//Node內(nèi)部的刪除節(jié)點(diǎn)
public void delNode(int data){
if(this.next!=null){
if(this.next.data==data){
this.next = this.next.next;
}else{
//此處使用遞歸
this.next.delNode(data);
}
}
}
查詢方法：
外部管理類的查詢方法：
//輸出所有節(jié)點(diǎn)
public void print(){
if(root!=null){//如果根節(jié)點(diǎn)不為空搭盾，就輸出然后繼續(xù)向下一個(gè)節(jié)點(diǎn)判斷輸出
System.out.print(root.getData()+"->");
root.printNode();
System.out.println();
}
}
節(jié)點(diǎn)內(nèi)部中的查詢方法：
//Node輸出所有節(jié)點(diǎn)
public void printNode(){
if(this.next!=null){
System.out.print(this.next.data+"->");
this.next.printNode();
}
}
這里面涉及到一個(gè)遞歸算法的問題，自己調(diào)用自己婉支，此處我們使用this關(guān)鍵字來表示誰調(diào)用本方法鸯隅，然后來依次對數(shù)據(jù)進(jìn)行靈活的判斷。由于此處我們在鏈表中存儲的是數(shù)字向挖，所以無法對對象數(shù)據(jù)進(jìn)行修改蝌以，如果你保存的是一個(gè)對象，我們可以記錄一個(gè)唯一標(biāo)識對象的標(biāo)記何之，并通過此標(biāo)記來對對象進(jìn)行查詢單個(gè)和修改操作跟畅。
此處我們也看出來了，使用鏈表比較利于插入和刪除溶推，因?yàn)槲抑苯痈淖円幌鹿?jié)點(diǎn)的引用地址即可徊件，所以頻繁做數(shù)據(jù)的插入和刪除操作時(shí)，我們可以優(yōu)先考慮鏈表
