為自己Coding

YO~~ 剛跨入AI人工智慧領域的小小工程師, 熱愛自學, 熱愛分享, 下班後的我想為自己Coding, 積極撰寫教學文, 想將自學的程式知識分享給大家, 不斷追求進步的自己, 希望有一天能回饋社會,幫助需要幫助的人, 如果您有什麼很酷的想法,也覺得我還行,歡迎您找我合作~~

LeetCode筆記 - Linked List - 鏈結串列 - 觀念介紹

發布於

Github連結

攝影師:Alex Azabache,連結:Pexels



1. 什麼是鏈結串列 Linked List?


說明: 為一種常見的基礎資料結構,由很多個節點連結成一種線性的串列,但不會按照線性的順序來存儲資料,而是在每一個]節點中存放下一個節點的指標(Pointer),用來指向下一個資料的位置


類型: 單向鏈結串列、雙向鏈結串列、迴圈鏈結串列


適用範圍:

  • 不在意單點的存取操作,不然最好使用List或Array,因為它們可以直接透過索引找到該值,而鏈結串列只存放下一個指標,所以要一個一個找,尋找一個節點或者存取特定位置的節點需要O(n),而List或Array只要O(1)
  • 需要新增節點的成本較低時,因為它不必按照順序,在鏈結串列中插入節點的時間複雜度可以達到O(1)
  • 要操作的節點最好在開頭或結尾,因為搜尋節點的時間複雜度為O(n),但是如果是開頭或結尾要新增節點時間複雜度只需要O(1)



單向鏈結

開頭為head指向第一個節點,每個節點包含資料,和下一個節點的記憶體位置,如果不為環狀,最後一個節點會連向NIL




雙向鏈結 Doubly Linked List

開頭為head指向第一個節點,每個節點中包含資料,上一個節點指標和下一個節點指標,如果不為環狀,最後一個節點會連向NIL




2. 實現操作


  • 新增節點: x = ListNode(val)
  • 插入節點: 如果要insert在a和b之間

指定下一個節點: x.next = b

指定a的下一個節點為x: a.next = x

  • 刪除節點: 假設節點的鏈結為 a -> x => b,要刪除x節點

將a的下一個節點位置修正為b: a.next = b

  • 一次讀取所有鏈結的值
## 指向第一個節點
all = head
## 當節點不為空的時候
while all:
  ## 印出節點值
  print(a.val)
  ## 抓取下一個節點
  all = all.next




Reference

https://zh.wikipedia.org/wiki/链表

https://hiskio.com/courses/319/lectures/15386


喜歡我的文章嗎?
別忘了給點支持與讚賞,讓我知道創作的路上有你陪伴。

CC BY-NC-ND 2.0 版權聲明
2

看不過癮?

一鍵登入,即可加入全球最優質中文創作社區