【威哥說(shuō)】威哥在此和小伙伴們道歉艳吠,本來(lái)計(jì)劃昨天早上給大家分享的視頻麦备,因?yàn)槭韬龀霈F(xiàn)了遺漏,導(dǎo)致大家沒(méi)有及時(shí)學(xué)習(xí)昭娩,今天不但要給大家補(bǔ)齊視頻凛篙,同時(shí)我還和磨礪營(yíng)的另外一個(gè)小伙伴甘愿自罰,以表示對(duì)大家的歉意栏渺。希望相信我以及磨礪營(yíng)的小伙伴們呛梆,能夠?qū)W習(xí)到更多的知識(shí)。(懲罰內(nèi)容磕诊,每人罰100個(gè)俯臥撐填物,如圖)更多技術(shù)干貨,請(qǐng)關(guān)注磨礪營(yíng)官網(wǎng)
【正文】
鏈表:鏈表是一種物理存儲(chǔ)單元上非連續(xù)霎终、非順序的存儲(chǔ)結(jié)構(gòu)滞磺,數(shù)據(jù)元素的邏輯順序是通過(guò)鏈表中的指針鏈接次序?qū)崿F(xiàn)的。鏈表由一系列結(jié)點(diǎn)(鏈表中每一個(gè)元素稱為結(jié)點(diǎn))組成莱褒,結(jié)點(diǎn)可以在運(yùn)行時(shí)動(dòng)態(tài)生成击困。每個(gè)結(jié)點(diǎn)包括兩個(gè)部分:一個(gè)是存儲(chǔ)數(shù)據(jù)元素的數(shù)據(jù)域,另一個(gè)是存儲(chǔ)下一個(gè)結(jié)點(diǎn)地址的指針域广凸。
這是百度上的回答阅茶,那么通俗點(diǎn)來(lái)說(shuō),就是鏈表是一個(gè)不連續(xù)炮障,沒(méi)有順序的存儲(chǔ)結(jié)構(gòu)目派。他們之間的連接是通過(guò)本節(jié)點(diǎn)中記錄下一個(gè)節(jié)點(diǎn)的地址來(lái)保持關(guān)系的坤候。就像鐵鏈胁赢,每一環(huán)扣著每一環(huán),所以名稱也是由此而來(lái)白筹。
那么解釋看懂了智末,我們?nèi)绾稳?shí)實(shí)在在的將這個(gè)存儲(chǔ)結(jié)構(gòu)在我們的代碼中體現(xiàn)出來(lái)呢。接下來(lái)徒河,跟著文章的思路走系馆。
首先我們要搞清楚,我們此處的存值是通過(guò)節(jié)點(diǎn)進(jìn)行存儲(chǔ)顽照,所以我們需要一個(gè)節(jié)點(diǎn)對(duì)象由蘑,那么通過(guò)在一個(gè)節(jié)點(diǎn)中保存下一個(gè)節(jié)點(diǎn)對(duì)象闽寡,所以我們要在一個(gè)節(jié)點(diǎn)中封裝下一個(gè)節(jié)點(diǎn)的引用,并且我們是通過(guò)節(jié)點(diǎn)中封裝屬性的方法對(duì)數(shù)據(jù)進(jìn)行存儲(chǔ)的尼酿,所以此處的節(jié)點(diǎn)對(duì)象我們可以命名為:
private class Node{
private int data; ?//節(jié)點(diǎn)要存儲(chǔ)的數(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)部類的方式來(lái)講節(jié)點(diǎn)存儲(chǔ)在節(jié)點(diǎn)管理類中爷狈,也就是說(shuō)將節(jié)點(diǎn)類封裝到我們的NodeManager中,這樣對(duì)外就不直接暴露根本的節(jié)點(diǎn)類:
class NodeManager{
//此處保存一個(gè)根節(jié)點(diǎn)
private Node root;
private class Node{
private int data; ?//節(jié)點(diǎn)要存儲(chǔ)的數(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)為空鹿响,就存儲(chǔ)在根節(jié)點(diǎn)中
if(root==null){
//新建一個(gè)節(jié)點(diǎn)(將要存儲(chǔ)的數(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)前對(duì)象,注意惶我,誰(shuí)調(diào)用此方法妈倔,this就表示誰(shuí),如果這里的下一個(gè)節(jié)點(diǎn)為空指孤,就將數(shù)據(jù)通過(guò)構(gòu)造方法存儲(chǔ)起來(lái)
if(this.next==null){
this.next = new Node(data);
}else{
//此處使用了遞歸算法启涯,如果檢測(cè)到下一個(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í)就會(huì)直接略過(guò)這個(gè)沒(méi)有記錄的這個(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)部的刪除方法鸣峭,同樣的我們需要使用遞歸來(lá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è)遞歸算法的問(wèn)題,自己調(diào)用自己充石,此處我們使用this關(guān)鍵字來(lái)表示誰(shuí)調(diào)用本方法莫换,然后來(lái)依次對(duì)數(shù)據(jù)進(jìn)行靈活的判斷。由于此處我們?cè)阪湵碇写鎯?chǔ)的是數(shù)字骤铃,所以無(wú)法對(duì)對(duì)象數(shù)據(jù)進(jìn)行修改拉岁,如果你保存的是一個(gè)對(duì)象,我們可以記錄一個(gè)唯一標(biāo)識(shí)對(duì)象的標(biāo)記惰爬,并通過(guò)此標(biāo)記來(lái)對(duì)對(duì)象進(jìn)行查詢單個(gè)和修改操作喊暖。
此處我們也看出來(lái)了,使用鏈表比較利于插入和刪除撕瞧,因?yàn)槲抑苯痈淖円幌鹿?jié)點(diǎn)的引用地址即可陵叽,所以頻繁做數(shù)據(jù)的插入和刪除操作時(shí)狞尔,我們可以優(yōu)先考慮鏈表