第 12 天簡單介紹過 linked-list
今天再更多基本知識

linked-list Introdution

Array 是一個很好用的東西，可是會造成

• 資料需要先 pre-allocating => 空間浪費
• 讀取速度緩慢

而 linked-list 有著 **Dynamically allocate memory space ** ，並使用指標將資料一一串起

在 linked-list 結構中，資料可能長這樣：

根據圖片，我們可以這樣宣告

class Student { 
    public:
    int id;
    char* name;
    Student* next;
};

並且可以這樣使用：

Student* sp = new Student;
sp -> id = 106001001;
sp -> name = "John Doe";
sp -> next = NULL;

其中的 NULL 表示接地，在 C 語言中

#define NULL (void *)0

C++11 之後

#define NULL nullptr

而在我寫 leetcode 的經驗，nullptr 略快一些。

linked-list 中還有一個重要角色：next 表示下一個 data

Types of Linked Lists

• Singly linked lists are space-efficient.
• Doubly linked lists support two-way traversal.
• Circular Linked List with pre and next

Singly linked-list:

Double linked-list:

Cicular linked-list:

Conclusion

Arrays:

• 空間不自由，而且可能造成浪費
  Linked lists
• Traversal 慢 (∵ involves many memory address translation)
• Search 也慢