C++单链表实现：头插法与尾插法详解

知识点： 1. 单链表的基本概念 单链表是一种基本的数据结构，由一系列节点组成，每个节点包含两个部分：一部分存储数据，另一部分存储指向下一个节点的指针。单链表的特点是每个节点只有一个指向下一个节点的链接，因此也称为单向链表。 2. 头插法建立单链表 头插法是一种在单链表头部插入新节点的方法。每次插入新节点时，都将其放置在链表的第一个位置，即链表头部。头插法的步骤通常如下： - 创建新节点 - 将新节点的next指针指向当前头节点 - 更新头节点为新节点 头插法的时间复杂度为O(1)，因为插入操作不依赖于链表的长度。 3. 尾插法建立单链表 尾插法是一种在单链表尾部插入新节点的方法。每次插入新节点时，都将其放置在链表的最后一个位置。尾插法通常需要维护一个指向链表尾部的指针，以便快速访问尾部进行插入。尾插法的步骤通常如下： - 判断链表是否为空，若为空则新节点即为头节点 - 若链表不为空，遍历链表找到尾节点 - 将尾节点的next指针指向新节点 - 更新尾节点指针为新节点 尾插法的时间复杂度为O(n)，因为最坏情况下需要遍历整个链表找到尾部。 4. C++代码实现 在C++中，单链表的节点通常使用结构体（struct）或类（class）来定义。下面是使用结构体定义节点和通过头插法及尾插法建立单链表的示例代码片段。 ```cpp #include <iostream> // 定义链表节点结构体 struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(NULL) {} }; // 头插法建立单链表 void insertAtHead(ListNode *&head, int value) { ListNode *newNode = new ListNode(value); newNode->next = head; head = newNode; } // 尾插法建立单链表 void insertAtTail(ListNode *&head, int value) { ListNode *newNode = new ListNode(value); if (head == NULL) { head = newNode; } else { ListNode *current = head; while (current->next != NULL) { current = current->next; } current->next = newNode; } } // 打印链表函数 void printList(ListNode *head) { while (head != NULL) { std::cout << head->val << " "; head = head->next; } std::cout << std::endl; } int main() { ListNode *head = NULL; // 初始化头节点为NULL insertAtHead(head, 3); insertAtHead(head, 2); insertAtHead(head, 1); printList(head); // 输出头插法建立的链表：1 2 3 insertAtTail(head, 4); insertAtTail(head, 5); printList(head); // 输出尾插法建立的链表：1 2 3 4 5 return 0; } ``` 5. 链表操作注意事项 在操作链表时，需要注意内存管理问题，特别是使用new操作符分配的内存。在删除节点时应确保释放对应内存以避免内存泄漏。在实际应用中，还需要考虑异常安全性和多线程环境下的线程安全问题。 6. 单链表与数组的比较 单链表相比数组具有动态的特点，可以在运行时根据需要添加或删除元素，而数组大小是固定的。然而，链表也有缺点，例如遍历链表时只能从头到尾进行，查找元素的时间复杂度为O(n)，而数组可以在O(1)的时间内随机访问元素。