屏东县网站建设_网站建设公司_企业官网_seo优化

单链表是一种常见的线性数据结构，由节点（Node）组成，每个节点包含数据域和指针域（指向下一个节点）。以下是单链表的核心操作实现，包括节点定义、链表类封装、增删查改、遍历、销毁等功能。

1. 完整代码实现

cpp

 

运行

 

#include <iostream>
#include <stdexcept>  // 用于异常处理
using namespace std;// 定义链表节点结构体
template <typename T>
struct ListNode {T data;               // 数据域ListNode<T>* next;    // 指针域，指向下一个节点// 节点构造函数ListNode(T val) : data(val), next(nullptr) {}
};// 单链表类封装
template <typename T>
class SinglyLinkedList {
private:ListNode<T>* head;    // 头节点指针（哨兵节点，不存储数据）int size;             // 链表元素个数public:// 构造函数：初始化空链表SinglyLinkedList() {head = new ListNode<T>(T());  // 头节点（哨兵），数据域默认值size = 0;}// 析构函数：销毁链表~SinglyLinkedList() {clear();          // 清空所有节点delete head;      // 释放头节点head = nullptr;}// 1. 清空链表void clear() {ListNode<T>* curr = head->next;  // 从第一个有效节点开始while (curr != nullptr) {ListNode<T>* temp = curr;curr = curr->next;delete temp;  // 释放当前节点}head->next = nullptr;size = 0;}// 2. 在链表尾部添加元素void push_back(T val) {ListNode<T>* newNode = new ListNode<T>(val);ListNode<T>* curr = head;// 找到最后一个节点while (curr->next != nullptr) {curr = curr->next;}curr->next = newNode;size++;}// 3. 在链表头部添加元素void push_front(T val) {ListNode<T>* newNode = new ListNode<T>(val);newNode->next = head->next;  // 新节点指向原第一个节点head->next = newNode;        // 头节点指向新节点size++;}// 4. 删除指定值的第一个节点bool remove(T val) {ListNode<T>* prev = head;ListNode<T>* curr = head->next;while (curr != nullptr) {if (curr->data == val) {prev->next = curr->next;  // 跳过待删除节点delete curr;              // 释放内存size--;return true;}prev = curr;curr = curr->next;}return false;  // 未找到该值}// 5. 根据索引删除节点（索引从0开始）bool removeAt(int index) {if (index < 0 || index >= size) {throw out_of_range("Index out of bounds");}ListNode<T>* prev = head;ListNode<T>* curr = head->next;for (int i = 0; i < index; i++) {prev = curr;curr = curr->next;}prev->next = curr->next;delete curr;size--;return true;}// 6. 查找元素是否存在bool find(T val) const {ListNode<T>* curr = head->next;while (curr != nullptr) {if (curr->data == val) {return true;}curr = curr->next;}return false;}// 7. 获取指定索引的元素（索引从0开始）T get(int index) const {if (index < 0 || index >= size) {throw out_of_range("Index out of bounds");}ListNode<T>* curr = head->next;for (int i = 0; i < index; i++) {curr = curr->next;}return curr->data;}// 8. 修改指定索引的元素bool set(int index, T val) {if (index < 0 || index >= size) {return false;}ListNode<T>* curr = head->next;for (int i = 0; i < index; i++) {curr = curr->next;}curr->data = val;return true;}// 9. 获取链表长度int getSize() const {return size;}// 10. 判断链表是否为空bool isEmpty() const {return size == 0;}// 11. 遍历打印链表void print() const {ListNode<T>* curr = head->next;if (curr == nullptr) {cout << "Linked list is empty" << endl;return;}cout << "Linked list: ";while (curr != nullptr) {cout << curr->data << " -> ";curr = curr->next;}cout << "nullptr" << endl;}
};// 测试代码
int main() {// 创建int类型的链表SinglyLinkedList<int> list;// 测试添加元素list.push_back(10);list.push_back(20);list.push_front(5);list.print();  // 输出：5 -> 10 -> 20 -> nullptr// 测试查找cout << "Find 10: " << boolalpha << list.find(10) << endl;  // truecout << "Find 30: " << boolalpha << list.find(30) << endl;  // false// 测试获取元素cout << "Index 1: " << list.get(1) << endl;  // 10// 测试修改元素list.set(1, 15);list.print();  // 5 -> 15 -> 20 -> nullptr// 测试删除元素list.remove(15);list.print();  // 5 -> 20 -> nullptrlist.removeAt(1);list.print();  // 5 -> nullptr// 测试清空list.clear();list.print();  // Linked list is empty// 测试边界情况try {list.get(0);  // 抛出异常} catch (const out_of_range& e) {cout << "Exception: " << e.what() << endl;}return 0;
}

 

2. 核心概念解析

（1）节点结构（ListNode）

• data：存储节点的实际数据，使用模板支持任意类型（int、string、自定义类型等）。
• next：指向链表中下一个节点的指针，尾节点的next为nullptr。

（2）头节点（哨兵节点）

• 代码中使用哨兵头节点（不存储有效数据），目的是统一空链表和非空链表的操作逻辑，避免处理head为nullptr的边界情况。
• 例如：空链表时head->next = nullptr，而非空时head->next指向第一个有效节点。

（3）核心操作说明

操作	功能描述	时间复杂度
push_back	尾部添加元素	O(n)
push_front	头部添加元素	O(1)
remove	删除指定值的第一个节点	O(n)
find	查找元素是否存在	O(n)
get/set	获取 / 修改指定索引元素	O(n)
clear	清空链表	O(n)

3. 关键注意事项

1. 内存管理：
   • 所有new创建的节点必须在析构 / 删除时用delete释放，避免内存泄漏。
   • 析构函数先调用clear()释放所有有效节点，再释放头节点。
2. 边界处理：
   • 操作索引时需检查是否越界（index < 0 || index >= size）。
   • 空链表的遍历 / 删除操作需特殊处理，避免访问nullptr。
3. 模板支持：
   • 代码使用模板template <typename T>，支持任意数据类型（如SinglyLinkedList<string>、SinglyLinkedList<double>）。
4. 遍历逻辑：
   • 从head->next开始遍历，直到curr == nullptr结束。

4. 扩展优化方向

• 尾指针优化：添加tail指针，将push_back的时间复杂度从 O (n) 降为 O (1)。
• 双向链表：扩展为双向链表（每个节点增加prev指针），支持反向遍历和高效删除指定节点。
• 迭代器封装：实现迭代器（iterator），支持 C++ 风格的范围遍历（for (auto val : list)）。
• 异常安全：使用智能指针（unique_ptr）替代裸指针，自动管理内存，避免手动delete。