# 鏈表操作：遍歷，插入和刪除 > 原文： [https://www.programiz.com/dsa/linked-list-operations](https://www.programiz.com/dsa/linked-list-operations) #### 在本教程中，您將學習鏈表上的不同操作。 此外，您還將發現 C/C++ ，Python 和 Java 中鏈表操作的實現。 現在您已經了解了[鏈表](/data-structures/linked-list)和它們的[類型](/data-structures/linked-list-types)的基本概念，是時候深入了解可以執行的常見操作了。 請記住兩個要點： * `head`指向鏈表的第一個節點 * 最后一個節點的`next`指針是`NULL`，因此，如果下一個當前節點是`NULL`，我們已經到達鏈表的末尾。 在所有示例中，我們將假定鏈表具有三個節點`1 --->2 --->3`，其節點結構如下： ``` struct node { int data; struct node *next; }; ``` * * * ## 如何遍歷鏈表 顯示鏈表的內容非常簡單。 我們繼續將臨時節點移至下一個節點并顯示其內容。 當`temp`為`NULL`時，我們知道我們已經到達鏈表的末尾，因此我們退出了`while`循環。 ``` struct node *temp = head; printf("\n\nList elements are - \n"); while(temp != NULL) { printf("%d --->",temp->data); temp = temp->next; } ``` 該程序的輸出為： ``` List elements are - 1 --->2 --->3 ---> ``` * * * ## 如何將元素添加到鏈表 您可以將元素添加到鏈表的開始，中間或結尾。 ### 添加到開頭 * 為新節點分配內存 * 存儲數據 * 更改新節點的`next`指向`head` * 將`head`更改為指向最近創建的節點 ``` struct node *newNode; newNode = malloc(sizeof(struct node)); newNode->data = 4; newNode->next = head; head = newNode; ``` ### 添加到最后 * 為新節點分配內存 * 存儲數據 * 遍歷到最后一個節點 * 將最后一個節點的`next`更改為最近創建的節點 ``` struct node *newNode; newNode = malloc(sizeof(struct node)); newNode->data = 4; newNode->next = NULL; struct node *temp = head; while(temp->next != NULL){ temp = temp->next; } temp->next = newNode; ``` ### 添加到中間 * 分配內存并存儲新節點的數據 * 遍歷到新節點所需位置之前的節點 * 更改`next`指針以在其間包含新節點 ``` struct node *newNode; newNode = malloc(sizeof(struct node)); newNode->data = 4; struct node *temp = head; for(int i=2; i < position; i++) { if(temp->next != NULL) { temp = temp->next; } } newNode->next = temp->next; temp->next = newNode; ``` * * * ## 如何從鏈表中刪除 您可以從開頭，結尾或特定位置刪除。 ### 從頭刪除 * 將`head`指向第二個節點 ``` head = head->next; ``` ### 從結尾刪除 * 遍歷到倒數第二個元素 * 將其`next`指針更改為`null` ``` struct node* temp = head; while(temp->next->next!=NULL){ temp = temp->next; } temp->next = NULL; ``` ### 從中間刪除 * 遍歷到要刪除的元素之前的元素 * 更改`next`指針以將節點從鏈中排除 ``` for(int i=2; i< position; i++) { if(temp->next!=NULL) { temp = temp->next; } } temp->next = temp->next->next; ``` * * * ## 完整的鏈表操作程序 ```py # Linked list operations in Python # Create a node class Node: def __init__(self, item): self.item = item self.next = None class LinkedList: def __init__(self): self.head = None # Insert at the beginning def insertAtBeginning(self, data): new_node = Node(data) new_node.next = self.head self.head = new_node # Insert after a node def insertAfter(self, node, data): if node is None: print("The given previous node must inLinkedList.") return new_node = Node(data) new_node.next = node.next node.next = new_node # Insert at the end def insertAtEnd(self, data): new_node = Node(data) if self.head is None: self.head = new_node return last = self.head while (last.next): last = last.next last.next = new_node # Deleting a node def deleteNode(self, position): if self.head == None: return temp_node = self.head if position == 0: self.head = temp_node.next temp_node = None return # Find the key to be deleted for i in range(position - 1): temp_node = temp_node.next if temp_node is None: break # If the key is not present if temp_node is None: return if temp_node.next is None: return next = temp_node.next.next temp_node.next = None temp_node.next = next def printList(self): temp_node = self.head while (temp_node): print(str(temp_node.item) + " ", end="") temp_node = temp_node.next if __name__ == '__main__': llist = LinkedList() llist.insertAtEnd(1) llist.insertAtBeginning(2) llist.insertAtBeginning(3) llist.insertAtEnd(4) llist.insertAfter(llist.head.next, 5) print('Linked list:') llist.printList() print("\nAfter deleting an element:") llist.deleteNode(3) llist.printList() ``` ```java // Linked list operations in Java class LinkedList { Node head; // Create a node class Node { int item; Node next; Node(int d) { item = d; next = null; } } public void insertAtBeginning(int data) { // insert the item Node new_node = new Node(data); new_node.next = head; head = new_node; } public void insertAfter(Node prev_node, int data) { if (prev_node == null) { System.out.println("The given previous node cannot be null"); return; } Node new_node = new Node(data); new_node.next = prev_node.next; prev_node.next = new_node; } public void insertAtEnd(int data) { Node new_node = new Node(data); if (head == null) { head = new Node(data); return; } new_node.next = null; Node last = head; while (last.next != null) last = last.next; last.next = new_node; return; } void deleteNode(int position) { if (head == null) return; Node node = head; if (position == 0) { head = node.next; return; } // Find the key to be deleted for (int i = 0; node != null && i < position - 1; i++) node = node.next; // If the key is not present if (node == null || node.next == null) return; // Remove the node Node next = node.next.next; node.next = next; } public void printList() { Node node = head; while (node != null) { System.out.print(node.item + " "); node = node.next; } } public static void main(String[] args) { LinkedList llist = new LinkedList(); llist.insertAtEnd(1); llist.insertAtBeginning(2); llist.insertAtBeginning(3); llist.insertAtEnd(4); llist.insertAfter(llist.head.next, 5); System.out.println("Linked list: "); llist.printList(); System.out.println("\nAfter deleting an element: "); llist.deleteNode(3); llist.printList(); } } ``` ```c // Linked list operations in C #include <stdio.h> #include <stdlib.h> // Create a node struct Node { int item; struct Node* next; }; void insertAtBeginning(struct Node** ref, int data) { // Allocate memory to a node struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); // insert the item new_node->item = data; new_node->next = (*ref); // Move head to new node (*ref) = new_node; } // Insert a node after a node void insertAfter(struct Node* node, int data) { if (node == NULL) { printf("the given previous node cannot be NULL"); return; } struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); new_node->item = data; new_node->next = node->next; node->next = new_node; } void insertAtEnd(struct Node** ref, int data) { struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); struct Node* last = *ref; new_node->item = data; new_node->next = NULL; if (*ref == NULL) { *ref = new_node; return; } while (last->next != NULL) last = last->next; last->next = new_node; return; } void deleteNode(struct Node** ref, int key) { struct Node *temp = *ref, *prev; if (temp != NULL && temp->item == key) { *ref = temp->next; free(temp); return; } // Find the key to be deleted while (temp != NULL && temp->item != key) { prev = temp; temp = temp->next; } // If the key is not present if (temp == NULL) return; // Remove the node prev->next = temp->next; free(temp); } // Print the linked list void printList(struct Node* node) { while (node != NULL) { printf(" %d ", node->item); node = node->next; } } // Driver program int main() { struct Node* head = NULL; insertAtEnd(&head, 1); insertAtBeginning(&head, 2); insertAtBeginning(&head, 3); insertAtEnd(&head, 4); insertAfter(head->next, 5); printf("Linked list: "); printList(head); printf("\nAfter deleting an element: "); deleteNode(&head, 3); printList(head); } ``` ```cpp // Linked list operations in C++ #include <stdlib.h> #include <iostream> using namespace std; // Create a node struct Node { int item; struct Node* next; }; void insertAtBeginning(struct Node** ref, int data) { // Allocate memory to a node struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); // insert the item new_node->item = data; new_node->next = (*ref); // Move head to new node (*ref) = new_node; } // Insert a node after a node void insertAfter(struct Node* prev_node, int data) { if (prev_node == NULL) { cout << "the given previous node cannot be NULL"; return; } struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); new_node->item = data; new_node->next = prev_node->next; prev_node->next = new_node; } void insertAtEnd(struct Node** ref, int data) { struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); struct Node* last = *ref; new_node->item = data; new_node->next = NULL; if (*ref == NULL) { *ref = new_node; return; } while (last->next != NULL) last = last->next; last->next = new_node; return; } void deleteNode(struct Node** ref, int key) { struct Node *temp = *ref, *prev; if (temp != NULL && temp->item == key) { *ref = temp->next; free(temp); return; } // Find the key to be deleted while (temp != NULL && temp->item != key) { prev = temp; temp = temp->next; } // If the key is not present if (temp == NULL) return; // Remove the node prev->next = temp->next; free(temp); } // Print the linked list void printList(struct Node* node) { while (node != NULL) { cout << node->item << " "; node = node->next; } } // Driver program int main() { struct Node* head = NULL; insertAtEnd(&head, 1); insertAtBeginning(&head, 2); insertAtBeginning(&head, 3); insertAtEnd(&head, 4); insertAfter(head->next, 5); cout << "Linked list: "; printList(head); cout << "\nAfter deleting an element: "; deleteNode(&head, 3); printList(head); } ```