一、Linked List
1.1 基本觀念介紹
Linked list 是一種常見的資料結構，會包含 head 和 tail 的資訊，以 null 來代表 Linked list 的終點，使用 node 來記錄、表示、儲存資料。
1.1.1 Singly linked list
單向鏈結串列 (單鏈結串列、線性鏈結串列、普通鏈結串列) 是最基本的鏈結串列，其特點是鏈結串列的鏈結方向是單向的，對鏈結串列的存取要通過從頭部開始，依序往下讀取。
每個 node 則會包含 value 和 next (Pointer，指向下一個 node 的位置) 的資訊。
1.1.2 Doubly linked list
雙向鏈結串列 (雙鏈結串列) 與單向鏈結串列最大的區別在於每個 node 都有兩個指標，分別指向上一個和下一個 node，所以從雙向鏈結串列中的任意一個 node 開始，都可以很方便地存取它的上一個和下一個 node。
這裡的每個 node 會包含 value, prev (指向前一個 node 的位置) 和 next。
1.1.3 Circularly Linked List
環狀鏈結串列 (迴圈鏈結串列) 與一般的鏈結串列操作基本一致，但串列頭尾的指標會連接在一起形成一個環。
Tail 的 next 指標會指向 head，head 的 prev 指標會指向 tail，而非 null。
1.2 Linked list 和 Array 比較
Linked list
記憶體位置為不連續性，因此不需要預留空間
插入 / 刪除 : O(1)
前提是已經知道數據位置
刪除方式是將指標轉向，本來的 node 雖然還留在記憶體中，但已經無法存取，可以選擇釋放記憶體，或是看語言由 garbage collection 處理
存取 / 搜尋 : O(n)
適用情境
無法預期資料數量時
需要頻繁增刪資料時
不需要頻繁查詢並取出資料時
Array
需要連續的記憶體空間，宣告時就需要決定空間大小，如果預設的空間太小容易發生上溢，如果太大容易造成記憶體空間浪費
插入 / 刪除 : O(n)
存取 / 搜尋 : O(1)
適用情境
需要快速取出資料時
不需要頻繁增刪資料時
資料的數量不會有太大變更時
1.3 實際運用範例
Linked list 可以用在創建 stack，或只能存取最後一個紀錄的，比如說瀏覽器的上一頁。
二、題目整理
- Linked list 解法建議善用畫圖 + 建立空表頭
Linked list 常出現之 LeetCode 題目整理
- 題號 : 根據 LeetCode 題目出現的頻率, top interview 150 等整理的，但注意不代表這就涵蓋所有面試會考的題目。或你可以選擇 Grind 來安排你要刷的題目
- 難度 : 按照你現在想要的難度選擇刷題
- 重要性 : 比如說你注意到、或別人提到 Google 很常考這個題目之類，可以設定你覺得相對的重要性，之後可以拿來篩選用
- 第一次是否解出來 : 紀錄解題是否第一次就成功，若不成功可能需要複習
- 解題思路 : 題目的思路過程，寫大綱就好不用寫很詳細
- 其他解法 : 若解出來是否還可以想到其他解法，或是看到別人提供了更好的解法便記錄下來，在面試時還可以提出自己有不同解法
- 學到技巧 : 如此題可以用 two pointer 來解，寫下來下次遇到別的題目就可以知道說我多一個解法可以想想看可不可行
- 複習次數 : 用來記錄第一次解不出來的題目之練習次數
- 複習筆記 : 有可能再做一次還是解不出來，那可寫下這次癥結點是什麼，怎麼解決的，盡量完全理解解法，讓自己如果再做一次題目時若還是卡住，可以看筆記或是回想筆記試圖解出來
- 上次解題時間 : 可用來篩選下次該複習的題目
三、References
--
相關文章
- Coding Interview 就是刷好刷滿刷爆 LeetCode 就會上?
- 簡單輕鬆十分鐘看懂 Time complexity & Space complexity 分析刷 LeetCode
- 簡單輕鬆十分鐘學會 Hash Map (雜湊表) 刷 LeetCode
沒有留言:
張貼留言