链表的建立，删除与插入

链表是一种基础且重要的数据结构，它在计算机科学中扮演着至关重要的角色，尤其是在处理动态数据集合时。链表不同于数组，它不依赖于物理存储位置的连续性，而是通过节点之间的引用关系来组织数据。在这个主题中，我们将深入探讨链表的建立、插入和删除操作。 ### 链表的建立 建立链表通常从创建一个空链表开始。在C++或Java等面向对象的语言中，可以定义一个链表节点类，包含数据域和指向下一个节点的指针（或引用）。例如： ```cpp struct ListNode { int val; // 节点值 ListNode *next; // 指向下一个节点的指针 ListNode(int x) : val(x), next(NULL) {} // 构造函数 }; ``` 然后，我们可以通过创建新的节点并连接它们来构建链表。例如，创建一个包含元素1、2和3的链表： ```cpp ListNode* head = new ListNode(1); head->next = new ListNode(2); head->next->next = new ListNode(3); ``` ### 链表的插入操作 链表的插入操作可以在链表的任何位置进行，包括头部（在已有节点之前）、尾部（在最后一个节点之后）或其他指定位置。以下是一些插入方法： 1. **头插法**：在链表的开头插入新节点。这只需要改变新节点的`next`指针为原头节点，并将头指针指向新节点。 ```cpp void insertAtHead(ListNode* &head, int val) { ListNode* newNode = new ListNode(val); newNode->next = head; head = newNode; } ``` 2. **尾插法**：在链表的末尾添加新节点。需要遍历整个链表找到尾部，然后将新节点链接到尾节点。 ```cpp void insertAtTail(ListNode* &head, int val) { ListNode* newNode = new ListNode(val); if (head == NULL) { head = newNode; } else { ListNode* current = head; while (current->next != NULL) { current = current->next; } current->next = newNode; } } ``` 3. **任意位置插入**：在指定位置插入新节点。需要先找到插入点，然后调整节点的指针关系。 ```cpp void insertAtPosition(ListNode* &head, int val, int position) { ListNode* newNode = new ListNode(val); if (position == 1) { insertAtHead(head, val); return; } ListNode* current = head; for (int i = 1; i < position - 1 && current != NULL; i++) { current = current->next; } if (current == NULL) { insertAtTail(head, val); } else { newNode->next = current->next; current->next = newNode; } } ``` ### 链表的删除操作 删除链表中的节点同样可以在不同位置进行，包括头部、尾部或指定位置。这里是一些删除方法： 1. **删除头节点**：只需更改头指针为第二个节点即可。 ```cpp void deleteHead(ListNode* &head) { if (head != NULL) { ListNode* temp = head; head = head->next; delete temp; } } ``` 2. **删除尾节点**：需要遍历链表找到前一个节点，然后断开连接。 ```cpp void deleteTail(ListNode* &head) { if (head == NULL || head->next == NULL) { return; } ListNode* current = head; while (current->next->next != NULL) { current = current->next; } ListNode* toDelete = current->next; current->next = NULL; delete toDelete; } ``` 3. **删除指定位置的节点**：找到目标节点的前一个节点，然后更新其`next`指针。 ```cpp void deleteAtPosition(ListNode* &head, int position) { if (head == NULL) return; if (position == 1) { deleteHead(head); return; } ListNode* current = head; for (int i = 1; i < position - 1 && current != NULL; i++) { current = current->next; } if (current != NULL) { ListNode* toDelete = current->next; current->next = current->next->next; delete toDelete; } } ``` 链表操作是数据结构和算法学习的基础，理解这些基本操作对于解决更复杂的问题至关重要。通过实践和模拟，你可以更好地掌握链表的工作原理，并能够灵活地在各种场景中应用它们。记住，链表虽然提供了比数组更高的灵活性，但它们在访问元素时通常效率较低，因为无法直接通过索引访问。因此，选择合适的数据结构取决于具体的应用需求。