C++ 单链表教程

单链表是一种常见的线性数据结构，它由一系列节点组成，每个节点包含两个部分：

  • 数据域：存储数据
  • 指针域：指向下一个节点

与数组不同的是，链表在内存中不是连续存储的，而是通过指针将各个节点连接起来。

📌 一、定义节点结构体

我们先用 struct 定义一个链表节点：

#include <iostream>
using namespace std;

// 定义链表节点结构体
struct Node {
    int data;         // 数据域，存储整型数据
    Node* next;       // 指针域，指向下一个节点

    // 构造函数，方便创建节点时初始化数据
    Node(int val) : data(val), next(nullptr) {}
};

✅ 解释：

  • data 是节点存储的数据。
  • next 是一个指向下一个节点的指针。
  • 构造函数 Node(int val) 让我们能更方便地创建节点对象。

📌 二、创建并操作链表

我们将实现以下基本操作：

  1. 在链表末尾插入节点
  2. 打印链表内容
  3. 删除指定值的节点
  4. 清空链表

✅ 2.1 插入节点（尾插法）

// 在链表末尾插入新节点
void insert(Node*& head, int val) {
    Node* newNode = new Node(val);  // 创建新节点

    if (head == nullptr) {          // 如果链表为空
        head = newNode;             // 新节点成为头节点
    } else {
        Node* temp = head;
        while (temp->next != nullptr) {  // 找到最后一个节点
            temp = temp->next;
        }
        temp->next = newNode;       // 将最后一个节点的 next 指向新节点
    }
}

🔁 注意：这里使用了 Node*& head 表示对头指针的引用，可以修改头指针本身。

✅ 2.2 打印链表

// 打印链表内容
void printList(Node* head) {
    Node* temp = head;
    while (temp != nullptr) {
        cout << temp->data << " -> ";
        temp = temp->next;
    }
    cout << "NULL" << endl;
}

✅ 2.3 删除指定值的节点

// 删除第一个等于 val 的节点
void deleteNode(Node*& head, int val) {
    if (head == nullptr) return;  // 链表为空，直接返回

    // 如果头节点就是要删除的节点
    if (head->data == val) {
        Node* toDelete = head;
        head = head->next;        // 更新头节点
        delete toDelete;          // 释放内存
        return;
    }

    // 查找要删除的节点
    Node* temp = head;
    while (temp->next != nullptr && temp->next->data != val) {
        temp = temp->next;
    }

    // 如果找到了目标节点
    if (temp->next != nullptr) {
        Node* toDelete = temp->next;
        temp->next = temp->next->next;  // 跳过该节点
        delete toDelete;                // 释放内存
    } else {
        cout << "未找到值为 " << val << " 的节点。" << endl;
    }
}

✅ 2.4 清空链表

// 清空整个链表
void clearList(Node*& head) {
    while (head != nullptr) {
        Node* toDelete = head;
        head = head->next;
        delete toDelete;
    }
}

📌 三、主函数测试

int main() {
    Node* head = nullptr;  // 初始化头指针为空

    // 插入节点
    insert(head, 10);
    insert(head, 20);
    insert(head, 30);

    // 打印链表
    cout << "原始链表：" << endl;
    printList(head);  // 输出: 10 -> 20 -> 30 -> NULL

    // 删除节点
    deleteNode(head, 20);
    cout << "删除值为20的节点后：" << endl;
    printList(head);  // 输出: 10 -> 30 -> NULL

    // 清空链表
    clearList(head);
    cout << "清空链表后：" << endl;
    printList(head);  // 输出: NULL

    return 0;
}

🧠 总结

操作 时间复杂度
插入（尾插） O(n)
删除
查找
打印

📝 小贴士

  • 使用 new 动态分配内存，记得用 delete 回收内存，避免内存泄漏。
  • 修改头指针时要用 Node*& 引用传递。
  • 单链表适合频繁插入/删除的场景，但访问效率不如数组高。

如果你希望我继续扩展这个教程，比如添加：

  • 头插法
  • 中间插入
  • 反转链表
  • 环形链表判断 请告诉我！我可以为你进一步补充。

2 条评论

  • @ 2025-7-27 16:59:19 
    #include <iostream>
using namespace std;

// 定义单链表节点
struct Node {//结构体
	int data;         // 数据域，存储整型数据
	Node* next;       // 指针域，指向下一个节点
	// 构造函数，方便创建节点时初始化数据
	//Node(int val) : data(val), next(nullptr) {}
	Node() {
		//cout<<"hello"<<endl;
		this->data = 0;//this表示结构体指针本身->  .
		this->next = nullptr; //=NULL;
	}
	Node(int d) {
		this->data = d;//this表示结构体指针本身->   .
		//data = d;
		this->next = nullptr; //=NULL;
	}
//	Node(int d,Node* ptr){
//		this->data = data;//this表示结构体指针本身->  .
//		this->next=nullptr;//=NULL;
//		//data = d;
//	}
	Node(int val, Node* ptr): data(val), next(ptr) {}
};
//高级编程提倡一个概念叫做封装
struct LinkedList {
private://struct结构体public公开访问默认可以不写
	Node* head;       // 头指针，指向链表的第一个节点
	Node* tail;     // 尾指针，指向链表的最后一个节点
	int size;         // 链表的大小
public:
	// 构造函数，初始化空链表
	LinkedList() : head(nullptr), tail(nullptr), size(0) {}
	// 析构函数，释放链表占用的内存
	~LinkedList() {
		clear();
	}
	// 判断链表是否为空
	bool isEmpty() const {// const 表示这个结构体内部的这个isEmpty函数不会修改结构体成员，只会访问、读取
		return size == 0;//const作用有两点，增加安全 增加可读性
	}
	// 获取链表的大小
	int getSize() const {
		return size;
	}
	
	// 在链表尾部添加元素
	void append(int value) {//不带有哨兵结点的尾插法
		Node* newNode = new Node(value);
//通过new关键字申请一个Node大小的空间，返回该空间的地址 初始化
		if (isEmpty()) {
			// 如果链表为空，新节点既是头节点也是尾节点
			head = tail = newNode;
		} else {
			// 否则将新节点连接到尾部，并更新尾指针
			//如果没有尾指针，我们需要需要创建一个尾指针，初始化为头
			//开个循环一个一个找
//			Node* tail=head;
//			while(tail->next == nullptr){
//				tail = tail->next;
//			}
			tail->next = newNode;
			tail = newNode;
		}
		size++;
	}
	// 在链表头部添加元素
	void prepend(int value) {//不带有哨兵结点
		Node* newNode = new Node(value);
		
		if (isEmpty()) {
			// 如果链表为空，新节点既是头节点也是尾节点
			head = tail = newNode;
		} else {
			// 否则将新节点插入到头部，并更新头指针
			newNode->next = head;
			head = newNode;
		}
		size++;
	}
	
	// 清空链表
	void clear() {
		Node* current = head;
		
		while (current != nullptr) {
			Node* nextNode = current->next;
			delete current;
			current = nextNode;
		}
		
		head = tail = nullptr;
		size = 0;
	}
};

int main() {
	LinkedList list;
	// 在尾部添加元素
	list.append(10);
	list.append(20);
	list.append(30);
	
	
	
	
//Node* head = nullptr;  // 初始化头指针为空	
//	//Node a();//X
//	Node a;	//创建一个结构体变量，调用自定义的构造函数
//	Node b(6);
//	cout << b.data << endl;
//	Node c(8, nullptr);
//	cout << c.data << endl;
	return 0;
}
    • @ 2025-6-9 21:20:21

      C++单链表教程

      单链表是一种常见的数据结构，由多个节点组成，每个节点包含数据和指向下一个节点的指针。链表的优点是插入和删除操作效率高，但随机访问效率低。

      下面是一个完整的单链表实现示例：

      #include <iostream>

// 定义单链表节点结构体
struct Node {
    int data;         // 节点存储的数据
    Node* next;       // 指向下一个节点的指针
    
    // 构造函数，方便节点初始化
    Node(int value) : data(value), next(nullptr) {}
};

// 单链表类，封装链表操作
class LinkedList {
private:
    Node* head;       // 头指针，指向链表的第一个节点
    Node* tail;       // 尾指针，指向链表的最后一个节点
    int size;         // 链表的大小
    
public:
    // 构造函数，初始化空链表
    LinkedList() : head(nullptr), tail(nullptr), size(0) {}
    
    // 析构函数，释放链表占用的内存
    ~LinkedList() {
        clear();
    }
    
    // 判断链表是否为空
    bool isEmpty() const {
        return size == 0;
    }
    
    // 获取链表的大小
    int getSize() const {
        return size;
    }
    
    // 在链表尾部添加元素
    void append(int value) {
        Node* newNode = new Node(value);
        
        if (isEmpty()) {
            // 如果链表为空，新节点既是头节点也是尾节点
            head = tail = newNode;
        } else {
            // 否则将新节点连接到尾部，并更新尾指针
            tail->next = newNode;
            tail = newNode;
        }
        
        size++;
    }
    
    // 在链表头部添加元素
    void prepend(int value) {
        Node* newNode = new Node(value);
        
        if (isEmpty()) {
            // 如果链表为空，新节点既是头节点也是尾节点
            head = tail = newNode;
        } else {
            // 否则将新节点插入到头部，并更新头指针
            newNode->next = head;
            head = newNode;
        }
        
        size++;
    }
    
    // 在指定位置插入元素
    bool insert(int index, int value) {
        if (index < 0 || index > size) {
            std::cout << "插入位置无效" << std::endl;
            return false;
        }
        
        if (index == 0) {
            prepend(value);
            return true;
        }
        
        if (index == size) {
            append(value);
            return true;
        }
        
        // 找到插入位置的前一个节点
        Node* prev = head;
        for (int i = 0; i < index - 1; i++) {
            prev = prev->next;
        }
        
        // 创建新节点并插入到链表中
        Node* newNode = new Node(value);
        newNode->next = prev->next;
        prev->next = newNode;
        
        size++;
        return true;
    }
    
    // 删除指定位置的元素
    bool remove(int index) {
        if (index < 0 || index >= size) {
            std::cout << "删除位置无效" << std::endl;
            return false;
        }
        
        Node* toDelete;
        
        if (index == 0) {
            // 删除头节点
            toDelete = head;
            head = head->next;
            
            if (head == nullptr) {
                // 如果链表只有一个节点，删除后尾指针也要置空
                tail = nullptr;
            }
        } else {
            // 找到删除位置的前一个节点
            Node* prev = head;
            for (int i = 0; i < index - 1; i++) {
                prev = prev->next;
            }
            
            toDelete = prev->next;
            prev->next = toDelete->next;
            
            if (toDelete == tail) {
                // 如果删除的是尾节点，更新尾指针
                tail = prev;
            }
        }
        
        // 释放删除节点的内存
        delete toDelete;
        size--;
        return true;
    }
    
    // 查找元素在链表中的位置
    int find(int value) const {
        Node* current = head;
        int index = 0;
        
        while (current != nullptr) {
            if (current->data == value) {
                return index;
            }
            current = current->next;
            index++;
        }
        
        return -1;  // 未找到元素
    }
    
    // 打印链表中的所有元素
    void print() const {
        Node* current = head;
        
        while (current != nullptr) {
            std::cout << current->data << " ";
            current = current->next;
        }
        
        std::cout << std::endl;
    }
    
    // 清空链表
    void clear() {
        Node* current = head;
        
        while (current != nullptr) {
            Node* nextNode = current->next;
            delete current;
            current = nextNode;
        }
        
        head = tail = nullptr;
        size = 0;
    }
};

// 使用示例
int main() {
    LinkedList list;
    
    // 在尾部添加元素
    list.append(10);
    list.append(20);
    list.append(30);
    
    std::cout << "链表内容: ";
    list.print();  // 输出: 10 20 30
    
    // 在头部添加元素
    list.prepend(5);
    
    std::cout << "在头部添加5后: ";
    list.print();  // 输出: 5 10 20 30
    
    // 在指定位置插入元素
    list.insert(2, 15);
    
    std::cout << "在位置2插入15后: ";
    list.print();  // 输出: 5 10 15 20 30
    
    // 删除指定位置的元素
    list.remove(3);
    
    std::cout << "删除位置3的元素后: ";
    list.print();  // 输出: 5 10 15 30
    
    // 查找元素
    int pos = list.find(15);
    std::cout << "元素15的位置是: " << pos << std::endl;  // 输出: 2
    
    // 清空链表
    list.clear();
    std::cout << "清空链表后，链表大小: " << list.getSize() << std::endl;  // 输出: 0
    
    return 0;
}

      代码解释

      1. Node结构体：

        • 包含一个整数data存储节点数据
        • 包含一个指向下一个节点的指针next
        • 构造函数用于初始化节点数据

      2. LinkedList类：

        • head和tail指针分别指向链表的头部和尾部
        • size记录链表的大小
        • 提供了链表的基本操作方法，如添加、删除、查找等

      3. 主要方法说明：

        • append(): 在链表尾部添加元素
        • prepend(): 在链表头部添加元素
        • insert(): 在指定位置插入元素
        • remove(): 删除指定位置的元素
        • find(): 查找元素位置
        • print(): 打印链表内容
        • clear(): 清空链表

      单链表的核心在于节点之间通过指针连接，插入和删除操作只需要修改指针指向，无需移动大量数据，因此效率较高。但访问元素需要从头节点开始遍历，时间复杂度为O(n)。

      • 1
      447
      已通过
      0
      题解被赞
      1. 关于
      2. 联系我们
      3. 隐私
      4. 服务条款
      5. 版权申诉
      6. Language
      7. 兼容模式
      8. 主题
      4. 在线咨询
      5. Worker 0, 23ms
      6. Powered by Hydro v4.13.3 Community