缺點

長度固定

找飯店 ?

Trivago !

需要動態長度的資料結構？

Linked List !

需要增加長度時

先宣告一塊新的記憶體

需要增加長度時

再連接（Link）起來

恭喜你得到一條 Linked List !

事前準備

結構宣告

struct node {
    int data;
    // 要存的資料，型別、數量不拘
    
    node *next;
    // 宣告指標準備做一個 Link 的動作
};

事前準備

記住頭尾的位置

node *head = NULL;
node *rear = NULL;

/*
    分別用兩個指標 head 跟 rear 記住 linked list 頭尾的位置
    初始值設為 NULL (尚無節點)
*/

事前準備

記憶體宣告函式

node *newNode(int data){
    node *res = new node;
    res->data = data;
    res->next = NULL;
    // 初始化 next 為 NULL
}

操作

尾端插入

void insertRear(int data){
    if(head == NULL)
        head = rear = newNode(data);
    else{
        rear->next = newNode(data);
        // 讓原本的最後一個節點的 next 指向新的尾巴
        
        rear = rear->next
        // 讓 rear 這個指標指向新的尾巴
    }
}

操作

遍歷

node *getNode(int index){
    node *res = head;
    
    // 這裡讓 head 的 index 為 0
    // 注意不要對 NULL 取值！
    for(int i = 0; i < index && res != NULL; i++)
        res = res->next
    
    return res
}

動動腦

利用 Linked List 實作 Queue 跟 Stack

用 Linked List 實作 Queue

新的值插在尾巴，取值由頭取

node *pop(){
    node *res = head;
    
    if(head != NULL)
        head = head->next;
    // 將 head 指向新的頭
    
    return res;
}

用 Linked List 實作 Stack

新的值插在頭，取值由頭取

void push(int data){
    node *newHead = newNode(data);
    newHead->next = head;
    // 新頭的 next 指向原本的 head
    
    head = newHead;
    // 讓 head 指向後來的頭
}

刪除任意位置的值：陣列

將後面的值全部往前搬

刪除任意位置的值：Linked List

讓前一個節點的 next 指向自己的 next

刪除任意位置的值：Linked List

讓前一個節點的 next 指向自己的 next

動動腦

在任意位置插入？

動動腦

在任意位置插入？

void insert(node *pos, node *insert){
    insert->next = pos->next
    pos->next = insert
}

因為要存取到前一個節點的值所以每次都要再從頭遍歷一次？

把前一個節點也記下來就好了

struct node{
    int data;
    
    node *prev, *next;
    // prev 指向上一個節點，next 指向下一個節點。
}

Double Linked List !

同樣的原理但要維護的值變多了

Array

優點：隨機存取、省空間

缺點：長度固定、任意插入／刪除慢

Linked List

優點：長度可變動、任意插入／刪除快

缺點：需要空間去存記憶體位置、循序存取