voidcreate_new_node(int node_nums){ int i; for (i=0; i< node_nums; i++){ // Declare new node current_node = (Node*)malloc(sizeof(Node)); printf("Data for node %d : ",i+1); // Enter node data scanf("%d", &(current_node->data)); // First node, don't have previous node, so let the first_node and previous_node equal to current_node if(i==0){ first_node = current_node; previous_node = current_node; } else{ // Set the previous node point to the current node previous_node->next = current_node; current_node->next = NULL; // Set the previous node to current node, prepare to next node creation (or not) previous_node = current_node; } } }
voidFreeList(Node* first){ Node *current, *temp_node; current = first; while ( current != NULL ){ // Put the node that wants to be removed into temp_node temp_node = current; // Let the current node point to the next node current = current->next; // Free the node free(temp_node); } }
// Return value should be the address of the node Node* SearchNode(Node* first, int item){ Node * node = first; while ( node != NULL){ if (node->data == item){ return node; } else{ node = node->next; } } }
voidInsertNode(Node* node, int item){ Node *new_node; new_node = (Node*)malloc(sizeof(Node)); // Point the new node to the nexy item of original node new_node->data = item; new_node->next = node->next; // Point the original node to new node node -> next = new_node; }
函數的傳入參數會是一個 node，並且還需要提供插入節點的資料值
接著就是新建立一個節點，為它分配記憶體空間
將新節點的 data 變數放入 item 這個資料值
將新結點的 next 放入原本輸入節點的下一個節點位址
將原本書入節點的 next 指向我們新建立的節點 這樣就完成插入節點的操作了
插頭
1 2 3 4 5 6 7 8
// Insert a node to the front of the list voidpush_front(int item){ Node * new_node; new_node = (Node*)malloc(sizeof(Node)); new_node->data = item; new_node->next = first_node; // new node pointer point to original first node first_node = new_node; // Update the first node to the new node }
// Insert a node to the back of the list voidpush_back(int item){ Node * new_node; new_node = (Node*)malloc(sizeof(Node)); new_node->data = item; new_node->next = NULL; // Handle empty list if (first_node == NULL){ first_node = new_node; } else{ // Initailize the current node to the first node for traversal Node * current_node = first_node; while (current_node->next != NULL){ // traverse through the list current_node = current_node->next; } // Point to the new node current_node->next = new_node; } }
Node* DeleteNode(Node* first ,Node* node){ Node* ptr= first; if (first == NULL) { printf("Noting to print\n"); } // Delete first node of the list if (node == first){ // Update the first pointer to the next node first = first->next; free(node); return first; } else{ // ptr traverse through the list while (ptr->next != node) { ptr = ptr->next; } ptr->next = node->next; free(node); return first; } }
傳入參數會有，初始節點，以及要被刪除的節點
一開始一樣會需要判斷 first_node 是否為 null，如果是 null 也沒東西給你刪
接著一樣會分成不同情況處理，分別是
刪除頭
刪除中間和尾端
刪除頭的處理方式會是先更新 first_node 更新為它的下一個節點
接著直接使用 free() 釋放記憶體
再來就是當鏈結還沒抵達要被刪除的節點時，繼續 traverse (ptr = ptr->next)
一旦找到了則將它的指標，先指向下一個節點的下一個節點位址
接著直接使用 free() 釋放記憶體
反轉鏈結串列 (Reverse Linked List)
要反轉一個陣列，會需要一個額外節點來暫時存放節點位址。
解釋
如果首先就把初始節點 (A節點)的指標指向 NULL 會有個問題，原先的指標存放的是下一個節點的位址，如果改成 NULL 不就不知道原先下一個節點的位址了嗎? 連節點位址都沒有要怎麼進行反轉?因此才需要額外的節點才指向到 B 節點，來存放B的記憶體位址。
因此步驟如下圖：
定義指標指向 NULL
建立暫存節點，指向到當前節點的下一個節點
將當前節點改指向 NULL
將下一個節點 (B節點)改指向上一個節點 (A節點)
更新暫存節點的指標，指向再下一個節點的位址
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
voidReverse(){ Node *current, *previous, *preceding; previous = NULL; current = first_node; // preceding node store the previous address of the current node preceding = first_node->next; while (preceding != NULL){ // pointer the current node to the NULL (previous) node current->next = previous; // Update previous poinert to current pointer previous = current; // Update current pointer to the preceding point current = preceding; // Update the preceding pointer to the next node; preceding = preceding->next; } current->next =previous; first_node=current; }
int node_numbers; int item; printf("The numbers of nodes:"); scanf("%d",&node_numbers); create_new_node(node_numbers); current_node = first_node; while (current_node!= NULL){ printf("[%p]|",current_node); printf("Data: %d",current_node->data); printf("| Addr. of next node=%p \n",current_node->next); current_node=current_node->next; }
// Traverse the list of nodes printf("=========================================================\n\n"); PrintList(first_node); printf("Serach Nodes: "); scanf("%d",&item); if (SearchNode(first_node,item)){ printf("Node found\n");} else {printf("Node not found\n");}
printf("Insert Node:"); // User input data scanf("%d",&item); if (SearchNode(first_node,item)){ printf("Node exisit in the list"); } else { // Insert behind the current node InsertNode(first_node,item); PrintList(first_node); }
printf("Reverse the list\n"); Reverse(); PrintList(first_node);
FreeList(first_node);
system("pause"); return0; }
voidcreate_new_node(int node_nums){ int i; for (i=0; i< node_nums; i++){ // Declare new node current_node = (Node*)malloc(sizeof(Node)); printf("Data for node %d : ",i+1); // Enter node data scanf("%d", &(current_node->data)); // First node, don't have previous node, so let the first_node and previous_node equal to current_node if(i==0){ first_node = current_node; previous_node = current_node; } else{ // Set the previous node point to the current node previous_node->next = current_node; current_node->next = NULL; // Set the previous node to current node, prepare to next node creation (or not) previous_node = current_node; } } }
// input parameter is node struct voidPrintList(Node* first){ // Decalre the address of input node Node *node = first; if (first == NULL){ printf("List is empty!\n"); } else{ while( node != NULL){ printf("%d -> ", node->data); node = node->next; } printf ("Null \n"); } }
voidFreeList(Node* first){ Node *current, *temp_node; current = first; while ( current != NULL ){ // Put the node that wants to be removed into temp_node temp_node = current; // Let the current node point to the next node current = current->next; // Free the node free(temp_node); } }
// Return value should be the address of the node Node* SearchNode(Node* first, int item){ Node * node = first; while ( node != NULL){ if (node->data == item){ return node; } else{ node = node->next; } } }
voidInsertNode(Node* node, int item){ Node *new_node; new_node = (Node*)malloc(sizeof(Node)); // Point the new node to the nexy item of original node new_node->data = item; new_node->next = node->next; // Point the original node to new node node -> next = new_node; }
// Insert a node to the front of the list voidpush_front(int item){ Node * new_node; new_node = (Node*)malloc(sizeof(Node)); new_node->data = item; new_node->next = first_node; // new node pointer point to original first node first_node = new_node; // Update the first node to the new node }
// Insert a node to the back of the list voidpush_back(int item){ Node * new_node; new_node = (Node*)malloc(sizeof(Node)); new_node->data = item; new_node->next = NULL; // Handle empty list if (first_node == NULL){ first_node = new_node; } else{ // Initailize the current node to the first node for traversal Node * current_node = first_node; while (current_node->next != NULL){ // traverse through the list current_node = current_node->next; } // Point to the new node current_node->next = new_node; } }
Node* DeleteNode(Node* first ,Node* node){ Node* ptr= first; if (first == NULL) { printf("Noting to print\n"); } // Delete first node of the list if (node == first){ // Update the first pointer to the next node first = first->next; free(node); return first; } else{ // ptr traverse through the list while (ptr->next != node) { ptr = ptr->next; } ptr->next = node->next; free(node); return first; } }
voidReverse(){ Node *current, *previous, *preceding; previous = NULL; current = first_node; // preceding node store the previous address of the current node preceding = first_node->next; while (preceding != NULL){ // pointer the current node to the NULL (previous) node current->next = previous; // Update previous poinert to current pointer previous = current; // Update current pointer to the preceding point current = preceding; // Update the preceding pointer to the next node; preceding = preceding->next; } current->next =previous; first_node=current; }
執行結果
總結: 透過這次的整理，算是有更加熟悉已經忘光的 linked list 操作，接下來就直接拿相關的LeetCode題目當練習吧
