[筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 17

重念一次早該補起來的「資料結構與演算法」。這篇筆記下何謂資料結構,並帶入一點連結串列 ( Linked List )。

notes-theideaofalgorithm-javascript-1


課程相關資訊

[連結]:https://hiskio.com/courses/572/lectures/29834

本篇範圍:Chapter 8

請注意:本系列文章為個人對應課程的消化吸收後,所整理出來的內容。換言之,並不一定會包含全部的課程內容,也有可能會添加其他資源來說明。


內容

為何要學資料結構?

JavaScript 中雖有 Array 和 Object,但時間複雜度可能會高達 O ( n^3 ) 或是 O ( n^2 ) 。運用一些資料結構,可以讓時間複雜度下降到 O ( n ), O ( logN ) 甚至是 O ( 1 )

Linked List 連結串列

JavaScript 的 Array 相比,它是一個在記憶體中「不連續」的資料結構。宣告一個新的連結串列時,會有起始點 head 和長度 length 兩個參數。接著其內的每一個元素節點,都會有值 value 和指針 pointer。當節點的 pointer 指向下一個 value 時,那連結就串起來了。若指向 null,那可能是被放棄的值,或是連結串列的最後一個。

優勢

1. 可以無限制的新增 node,也無須浪費多餘的記憶體位置
2. 插入新值和刪除都非常快

Insert

1. 新增一個節點元素
2. 以要插入的位置為基準點,其前一個的 next 改指向這個新增的節點。節點元素本身的 next 則指向原先的下一個 value
3. 整體元素的長度 + 1

Delete

1. 以要刪除的元素為基準點,其前一個的 next 改指向下一個 value
2. 將要刪除的元素其 next 改指向 null,這個元素實際上並不需要刪除
3. 整體元素的長度 – 1


系列文章

  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 9
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 8
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 7
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 6
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 5
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 4
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 33
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 32
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 31
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 30
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 3
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 29
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 28
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 27
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 26
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 25
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 24
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 23
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 22
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 21
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 20
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 2
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 19
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 18
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 16
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 15
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 14
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 13
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 12
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 11
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 10
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 1
  • 按讚加入粉絲團

    延伸閱讀