Linked Lists

• Ordered list
• Store date in seperate locations in memory.
• Implementation
  • array

    Using 2 arrays, data[] and link[] with same itemSizes. (圖片：王致強資料結構)

  • dynamic allocation

    以node形式，有需要時new 一個空間，用完release掉。 (Wiki: Linked lists)

Linked lists Analysis (compared to array)

• 每個node佔用較多記憶體，但是記憶體空間利用率高
• Insertion / Deletion: $O(1)$
• Merge / Split: $O(1)$
• NO direct access (random access), need to access from HEAD node.

  Link Assignment

  
• x = y
  • 把y指到的node的memory address的值assign給x，所以x會指向y所指的memory address。
• *x = *y
  • y裡面所有欄位的資料（link/data等等）都會assign給x。
  • 但x和y還是指向不同的memory address。

References

• NCTU Open Course (彭文志)