雖然以前寫(xiě)過(guò)一次鏈表，但是真的已經(jīng)忘得一干二凈了

鏈表理論基礎(chǔ)

• 鏈表：通過(guò)指針串聯(lián)在一起的線性結(jié)構(gòu)，每個(gè)節(jié)點(diǎn)都由數(shù)據(jù)域和指針域組成。
• 指針域：存放下一個(gè)節(jié)點(diǎn)的指針，最后一個(gè)節(jié)點(diǎn)的指針域指向null，也即空指針
• head：鏈表的入口節(jié)點(diǎn)，也即鏈表的頭節(jié)點(diǎn)

鏈表的類(lèi)型

• 單鏈表

  以上所講的最簡(jiǎn)單的鏈表為單鏈表（指針域指針只能指向下一個(gè)節(jié)點(diǎn)）

• 雙鏈表

  每個(gè)節(jié)點(diǎn)有兩個(gè)指針域，一個(gè)指向下一個(gè)節(jié)點(diǎn)，一個(gè)指向上一個(gè)節(jié)點(diǎn)

  可以向前、向后查詢(xún)

  （頭結(jié)點(diǎn)處向前查詢(xún)的指針為空指針）

• 循環(huán)鏈表

  相當(dāng)于單鏈表列表首尾相連，也即單鏈表最后一個(gè)指針指向head

  可以用于解決約瑟夫環(huán)問(wèn)題（這是什么問(wèn)題？）

鏈表的存儲(chǔ)方式

數(shù)組在內(nèi)存中連續(xù)分布，而鏈表不是連續(xù)分布。

鏈表通過(guò)指針域的指針鏈接在內(nèi)存中的各個(gè)節(jié)點(diǎn)，因此是胡亂分布在內(nèi)存的某地址上的（取決于操作系統(tǒng)的內(nèi)存管理）

鏈表的定義

• 如何定義一個(gè)單鏈表：

  class ListNode:
      def _init_(self, val, next=None):
          self.val = val
          self.next = next
  

  struct ListNode{
      int val;
      ListNode *next;
      ListNode(int x) : val(x), next(null){}   //節(jié)點(diǎn)的構(gòu)造函數(shù)
  }
  

• 注意構(gòu)造函數(shù)，如果不定義構(gòu)造函數(shù)，在初始化時(shí)就不能直接賦值：

  //自己定義了構(gòu)造函數(shù)
  ListNode* head = new ListNode(5);
  //沒(méi)有定義構(gòu)造函數(shù)，使用默認(rèn)構(gòu)造函數(shù)
  ListNode* head = new ListNode();
  head->val = 5;
  

鏈表的操作

• 刪除節(jié)點(diǎn)

如果鏈表中有節(jié)點(diǎn)A\B\C\D，現(xiàn)需要?jiǎng)h除節(jié)點(diǎn)C，只需將B節(jié)點(diǎn)中的next指針指向D即可。

注意，在c++中，C節(jié)點(diǎn)依舊存在于內(nèi)存當(dāng)中，因此需要手動(dòng)釋放，但Python中有自己的回收機(jī)制，不需要手動(dòng)釋放

• 添加節(jié)點(diǎn)

與上述相同，將前一個(gè)節(jié)點(diǎn)的next指針指向該節(jié)點(diǎn)，將該節(jié)點(diǎn)的next指針指向下一節(jié)點(diǎn)即可。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-500749.html

性能分析

• 鏈表操作，插入、刪除的時(shí)間復(fù)雜度為O（1），但是查詢(xún)的時(shí)間復(fù)雜度為O(n)，因?yàn)椴樵?xún)鏈表需要從頭開(kāi)始查詢(xún)
• 數(shù)組操作，插入、刪除時(shí)間復(fù)雜度為O(n)，因?yàn)閿?shù)組牽一發(fā)而動(dòng)全身，但是查詢(xún)時(shí)間復(fù)雜度為O(1)
• 數(shù)組長(zhǎng)度固定，想改動(dòng)長(zhǎng)度就要定義新數(shù)組；鏈表不固定

203.移除鏈表元素

• 注意虛擬節(jié)點(diǎn)的使用，為了更好地統(tǒng)一地管理頭結(jié)點(diǎn)
• 以及以前寫(xiě)的是Python語(yǔ)言，現(xiàn)在改c++有些變動(dòng)
• c++中要注意釋放內(nèi)存

707.設(shè)計(jì)鏈表

• 要學(xué)會(huì)自行定義鏈表結(jié)構(gòu)體
• 學(xué)會(huì)初始化鏈表怎么寫(xiě)
• 在c++中，要寫(xiě)初始化，相應(yīng)也要寫(xiě)

  public:
  	MyLinkdList(){
          //初始化，此時(shí)不用定義數(shù)據(jù)類(lèi)型，數(shù)據(jù)類(lèi)型在下面private里面定義
          _size = 0;
          _dummyHead = new ListNode(0);
      }
  private:
  	int _size;
  	ListNode* )dummyHead;
  

• dummyHead： 虛擬頭節(jié)點(diǎn)

206.反轉(zhuǎn)鏈表

• 設(shè)置了preNode, cur, nextNode三個(gè)節(jié)點(diǎn)，與此同時(shí)也要注意，如果head為空節(jié)點(diǎn)，那么nextNode是不存在的，所以要單獨(dú)討論
• 在設(shè)置反轉(zhuǎn)后的末尾節(jié)點(diǎn)指向nullptr時(shí)，并不是讓指向的節(jié)點(diǎn)deleta就行，直接delete節(jié)點(diǎn)會(huì)導(dǎo)致報(bào)錯(cuò)，應(yīng)該要讓她先指向nullptr，然后delete。
• 遞歸法沒(méi)太懂

到了這里，關(guān)于代碼隨想錄Day3|鏈表理論基礎(chǔ)|203.移除鏈表元素|707.設(shè)計(jì)鏈表|206.反轉(zhuǎn)鏈表的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！