[C] Linked list
Sep 28, 2021
利用指標,把原本的結構變數串起來。
在第一個結構後面加一個指標、讓它指向下一個結構;在第二個結構後面,再加一個指標,讓它指向下一個結構… 依次連接。
透過這樣的方式,能讓每個能彈性擴充。
當我們想在 Tzuyu 和 Mina 之間插入一個 Sana 時,就讓 Tzuyu 指向 Sana,再讓 Sana 指向後面 Mina。
鏈結串列的好處是彈性靈活,能動態跟記憶體要空間、或釋放空間。
鏈結串列由以下元素構成:
- 起始:指向鏈結串列第一個節點的指標
- 鏈結串列的節點:
- 當前節點的資料
- 下一個節點的地址
- 結尾:最後一個節點連接的地址寫「NULL」,表示鏈結串列結束。
Linked list 建立、列印、釋放空間
typedef struct node {
int val;
struct node* next;
} Node;Node* create_list(int arr[], int len){
//boundary
if(!arr || len == 0)
return NULL;
//main
Node *head, *tail;
for(int i=0; i<len; i++){
//create node
Node* curr = (Node*)malloc(sizeof(Node));
curr->val = arr[i];
curr->next = NULL;
//if it's first new node
if(i == 0){
head = curr;
tail = curr;
}else{
tail->next = curr;
tail = tail->next;
}
}
return head;
}void print_list(Node* head){
Node* p = head;
while(p){
printf("%d ", p->val);
p = p->next;
}
printf("\n");
}void delete_list(Node* head){
while(head){
Node* tmp = head;
head = head->next;
free(tmp);
}
}
還有一種Linked list是雙向的,可以做更方便的雙向搜尋