插入和刪除的靈活度蚊丐,你有他強(qiáng)么?

【威哥說(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)先考慮鏈表

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個(gè)濱河市巩掺,隨后出現(xiàn)的幾起案子沪么,更是在濱河造成了極大的恐慌,老刑警劉巖锌半,帶你破解...
    沈念sama閱讀 222,807評(píng)論 6 518
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件禽车,死亡現(xiàn)場(chǎng)離奇詭異,居然都是意外死亡刊殉,警方通過(guò)查閱死者的電腦和手機(jī)殉摔,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,284評(píng)論 3 399
  • 文/潘曉璐 我一進(jìn)店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)记焊,“玉大人逸月,你說(shuō)我怎么就攤上這事”槟ぃ” “怎么了碗硬?”我有些...
    開封第一講書人閱讀 169,589評(píng)論 0 363
  • 文/不壞的土叔 我叫張陵,是天一觀的道長(zhǎng)瓢颅。 經(jīng)常有香客問(wèn)我恩尾,道長(zhǎng),這世上最難降的妖魔是什么挽懦? 我笑而不...
    開封第一講書人閱讀 60,188評(píng)論 1 300
  • 正文 為了忘掉前任翰意,我火速辦了婚禮,結(jié)果婚禮上信柿,老公的妹妹穿的比我還像新娘冀偶。我一直安慰自己,他們只是感情好渔嚷,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,185評(píng)論 6 398
  • 文/花漫 我一把揭開白布进鸠。 她就那樣靜靜地躺著,像睡著了一般形病。 火紅的嫁衣襯著肌膚如雪客年。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 52,785評(píng)論 1 314
  • 那天窒朋,我揣著相機(jī)與錄音搀罢,去河邊找鬼蝗岖。 笑死侥猩,一個(gè)胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的抵赢。 我是一名探鬼主播欺劳,決...
    沈念sama閱讀 41,220評(píng)論 3 423
  • 文/蒼蘭香墨 我猛地睜開眼唧取,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼!你這毒婦竟也來(lái)了划提?” 一聲冷哼從身側(cè)響起枫弟,我...
    開封第一講書人閱讀 40,167評(píng)論 0 277
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤,失蹤者是張志新(化名)和其女友劉穎鹏往,沒(méi)想到半個(gè)月后淡诗,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 46,698評(píng)論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡伊履,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,767評(píng)論 3 343
  • 正文 我和宋清朗相戀三年韩容,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片唐瀑。...
    茶點(diǎn)故事閱讀 40,912評(píng)論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡群凶,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出哄辣,到底是詐尸還是另有隱情请梢,我是刑警寧澤,帶...
    沈念sama閱讀 36,572評(píng)論 5 351
  • 正文 年R本政府宣布力穗,位于F島的核電站毅弧,受9級(jí)特大地震影響,放射性物質(zhì)發(fā)生泄漏当窗。R本人自食惡果不足惜形真,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,254評(píng)論 3 336
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望超全。 院中可真熱鬧咆霜,春花似錦、人聲如沸嘶朱。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,746評(píng)論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)疏遏。三九已至脉课,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間财异,已是汗流浹背倘零。 一陣腳步聲響...
    開封第一講書人閱讀 33,859評(píng)論 1 274
  • 我被黑心中介騙來(lái)泰國(guó)打工, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留戳寸,地道東北人呈驶。 一個(gè)月前我還...
    沈念sama閱讀 49,359評(píng)論 3 379
  • 正文 我出身青樓,卻偏偏與公主長(zhǎng)得像疫鹊,于是被迫代替她去往敵國(guó)和親袖瞻。 傳聞我的和親對(duì)象是個(gè)殘疾皇子司致,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,922評(píng)論 2 361

推薦閱讀更多精彩內(nèi)容