[C] Linked list

Samuel Liu
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是雙向的,可以做更方便的雙向搜尋

--

--