• 博主簡介：努力學(xué)習(xí)的預(yù)備程序媛一枚~
• 博主主頁： @是瑤瑤子啦
• 所屬專欄: Java島冒險(xiǎn)記【從小白到大佬之路】

前言

因?yàn)楝幀幾诱趥鋺?zhàn)藍(lán)橋杯和校內(nèi)ACM選拔賽，最近在學(xué)習(xí)算法相關(guān)的知識(shí)。我是借助AcWing網(wǎng)站來學(xué)習(xí)的，這篇文章是我學(xué)習(xí)就我學(xué)習(xí)內(nèi)容的一個(gè)筆記，其中的一些對(duì)原理的解釋是我學(xué)習(xí)過程中可能看到彈幕或者評(píng)論的小伙伴，覺得講的很有道理醍醐灌頂，就引用過來了。
這篇是關(guān)于數(shù)據(jù)結(jié)構(gòu)，主要是利用數(shù)組模擬各種數(shù)據(jù)結(jié)構(gòu)，主要是提高算法效率。
對(duì)于一些比較晦澀難懂\讓人頭禿的地方，我習(xí)慣采用畫圖的方式來理解，所以你將看到我基于算法模板或題目精心繪制的圖解，希望能幫助一起學(xué)算法的同學(xué)噢！
因?yàn)楝幀幾幽壳斑€是小菜雞，可能會(huì)有理解不到位的地方，或者可以理解得更好的地方，還請(qǐng)大家多多指出哦！?

注意！下面每一種數(shù)據(jù)結(jié)構(gòu)的講解方式，采用代碼模板+文字說明&解釋+圖解

1.單鏈表(鄰接表）

作用：多用于鄰接表，存儲(chǔ)圖和樹

代碼模板

// head存儲(chǔ)鏈表頭，e[]存儲(chǔ)節(jié)點(diǎn)的值，ne[]存儲(chǔ)節(jié)點(diǎn)的next指針，idx表示當(dāng)前用到了哪個(gè)節(jié)點(diǎn),后一個(gè)
int head, e[N], ne[N], idx;
//NULL相當(dāng)于-1,所以head = -1相當(dāng)于head=NULL
// 初始化
void init()
{
    head = -1;
    idx = 0;
}

// 在鏈表頭插入一個(gè)數(shù)a
void insert(int a)
{   
    e[idx] = a, ne[idx] = head, head = idx ++ ;
}
//將x插入到下標(biāo)是k的點(diǎn)之后
void insert(int k, int x)
{
	e[idx] = x;
	ne[idx] = ne[k]
	ne[k] = idx;
	idx ++;
}

// 將頭結(jié)點(diǎn)刪除，需要保證頭結(jié)點(diǎn)存在
void remove()
{
    head = ne[head];
}

• 存儲(chǔ)節(jié)點(diǎn)數(shù)組的e[N]和存儲(chǔ)該節(jié)點(diǎn)的next指針數(shù)組ne[N]通過下標(biāo)關(guān)聯(lián)
• idx只是記錄當(dāng)前的操作的位置，一般實(shí)現(xiàn)的鏈表idx是亂序的(前后的節(jié)點(diǎn)的數(shù)組下標(biāo)不需要連續(xù)，需要通過當(dāng)前的ne[i]找到下一個(gè)idx。這也是兩者的聯(lián)系。
• head一開始=-1，這個(gè)-1相當(dāng)于物理地址的NULL，表示鏈表為空，即head指向一個(gè)頭節(jié)點(diǎn)，而使用頭插法，又巧妙的使這個(gè)空節(jié)點(diǎn)成為尾節(jié)點(diǎn)。聯(lián)想結(jié)構(gòu)體實(shí)現(xiàn)的單鏈表，最后一個(gè)節(jié)點(diǎn)的指針域是NULL所以，數(shù)組實(shí)現(xiàn)單鏈表的最后一個(gè)節(jié)點(diǎn)，假設(shè)是i,那么ne[i]=-1；
• 這里模擬的是沒有頭節(jié)點(diǎn)，head指針直接指向首元節(jié)點(diǎn)的單鏈表
• 雖然數(shù)組模擬的鏈表沒有用結(jié)構(gòu)體/類模擬的好理解，但是本質(zhì)都是一樣的，我們可以類比一下，對(duì)于一個(gè)節(jié)點(diǎn)Node。
• 所以其實(shí)畫圖的時(shí)候，也沒必要分的那么清楚，其實(shí)在我學(xué)習(xí)數(shù)組模擬鏈表之前，我一直認(rèn)為數(shù)組&鏈表屬于物理結(jié)構(gòu)，現(xiàn)在才發(fā)現(xiàn)，其實(shí)鏈表是一種邏輯結(jié)構(gòu)！

圖解

插入操作（頭插法）

2.雙鏈表

學(xué)習(xí)了數(shù)組模擬單鏈表，其實(shí)雙鏈表就很好理解了。其實(shí)就是多了一個(gè)指針域。

• 單鏈表：ne[i]存儲(chǔ)指針為i的節(jié)點(diǎn)的next指針
• 雙鏈表
  • l[i],指針為i的節(jié)點(diǎn)的前驅(qū)（指向前一個(gè)節(jié)點(diǎn)）
  • r[i],指針為i的節(jié)點(diǎn)的后驅(qū)（指向后一個(gè)節(jié)點(diǎn)）

//e[index],表示節(jié)點(diǎn)的值，l[index]表示節(jié)點(diǎn)的左指針，r[index]表示節(jié)點(diǎn)的右指針，idx表示當(dāng)前用到哪個(gè)節(jié)點(diǎn)的”地址“

int e[N],l[N],r[N],idx;

//初始化
void init(){
  //0是左端點(diǎn)，1是右端點(diǎn)
  r[0] = 1,l[1] = 0;
  idx = 2;
}
//在節(jié)點(diǎn)a的右邊插入一個(gè)數(shù)x
void insert(int a,int x){
  //1、讓待插入節(jié)點(diǎn)占位
  e[idx] = x;
  //2、處理待插入點(diǎn)左右兩側(cè)
  l[idx] = a,r[idx] = r[a];//注意，這里必須是r[a]，因?yàn)閍的下一個(gè)節(jié)點(diǎn)不一定和a順序存儲(chǔ)
  //3、處理前一個(gè)節(jié)點(diǎn)和后一個(gè)節(jié)點(diǎn)
  l[r[a]] = idx,r[a] = idx++;
}

Java島冒險(xiǎn)記【從小白到大佬之路】

LeetCode每日一題–進(jìn)擊大廠文章來源地址http://www.zghlxwxcb.cn/news/detail-790954.html

到了這里，關(guān)于【算法基礎(chǔ)】數(shù)據(jù)結(jié)構(gòu)| 單鏈表+雙鏈表 代碼實(shí)現(xiàn)+圖解+原理的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！