C++链表基本操作 初始化 插入 删除 输出 清空

链表是一种常用的数据结构，它在计算机科学中扮演着重要的角色，特别是在C++这样的编程语言中。本篇文章将深入探讨链表的基本操作，包括初始化、插入、删除、输出以及清空，这些都是理解和使用链表必不可少的知识点。 让我们了解链表的概念。链表不同于数组，它不是一个连续的内存空间，而是由一系列节点组成，每个节点包含数据和指向下一个节点的指针。在C++中，链表通常通过定义一个结构体或类来实现，例如： ```cpp struct ListNode { int val; // 节点值 ListNode *next; // 指向下一个节点的指针 ListNode(int x) : val(x), next(NULL) {} // 构造函数 }; ``` ### 1. 初始化链表 链表的初始化通常涉及创建一个空链表，即头节点为空。在C++中，可以这样实现： ```cpp ListNode *head = NULL; ``` ### 2. 插入节点 插入节点是链表操作中的核心部分。有多种插入方式，如在链表头部、尾部或指定位置插入。以下是在头部插入节点的示例： ```cpp void insertAtHead(ListNode *&head, int val) { ListNode *newNode = new ListNode(val); newNode->next = head; head = newNode; } ``` ### 3. 删除节点 删除节点同样有多种情况，根据要删除节点的条件不同，实现方式也会有所不同。例如，删除特定值的节点： ```cpp ListNode* deleteNode(ListNode* head, int key) { if (head != NULL && head->val == key) { head = head->next; return head; } ListNode* current = head; while (current != NULL && current->next != NULL && current->next->val != key) { current = current->next; } if (current != NULL && current->next != NULL) { current->next = current->next->next; } return head; } ``` ### 4. 输出链表 输出链表通常采用迭代方式，从头节点开始遍历到尾部： ```cpp void printList(ListNode *head) { ListNode *temp = head; while (temp != NULL) { std::cout << temp->val << " "; temp = temp->next; } std::cout << std::endl; } ``` ### 5. 清空链表 清空链表涉及释放所有节点的内存，并将头节点设置为NULL： ```cpp void clearList(ListNode *&head) { ListNode *current = head, *next; while (current != NULL) { next = current->next; delete current; current = next; } head = NULL; } ``` 以上就是链表的基本操作，理解并掌握这些操作对于编写高效的C++代码至关重要。在实际应用中，链表经常与其他数据结构结合，如栈、队列、树等，形成更复杂的数据结构，解决更复杂的算法问题。因此，熟练掌握链表操作是提升编程能力的关键一步。