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*& 引用传递。
  • 单链表适合频繁插入/删除的场景，但访问效率不如数组高。

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

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

3 条评论

  • @ 2026-4-11 19:42:31 
    #include <iostream>
#include <algorithm>//排序
using namespace std;
// 定义链表节点结构体
struct Node {
    int data;         // 数据域，存储整型数据
    Node* next;       // 指针域，指向下一个节点
};

void printList(Node* head);// 打印链表内容

// 在链表末尾插入新节点  尾插法
void insert(Node*& head, int val) {//链表头指针，指向链表头节点
    Node* newNode = new Node;  // 创建新节点
    newNode->data = val;
    newNode->next = nullptr;
    //Node newNodeTemp;//创建临时节点
    //newNodeTemp.data = val;
    // newNodeTemp.next = nullptr;
    //Node* newNode = &newNodeTemp;
    if (head == nullptr) {          // 如果链表为空
        head = newNode;             // 新节点成为头节点
        cout << "链表为空，插入节点成功！" <<val<< endl;
    }
    else {
        Node* temp = head;//创建临时节点指针
        while (temp->next != nullptr) {  // 找到最后一个节点
            temp = temp->next;
        }
        temp->next = newNode;       // 将最后一个节点的 next 指向新节点
        cout << "插入节点成功！" <<val<< endl;
    }
}
//头插法
// 在链表头部插入新节点
void insertHead(Node*& head, int val) {
    Node* newNode = new Node;//创建新节点
    newNode->data = val;
    newNode->next = nullptr;
    if (head == nullptr) {
        head = newNode;
        cout << "链表为空，插入节点成功！" <<val<< endl;
    }
    else {
        // 在链表头部插入新节点
        newNode->next = head;//新节点的next指向头节点
        head = newNode;//头指针指向新节点  更新
        cout << "插入节点成功！" <<val<< endl;
    }
    printList(head);
}
void insertMid(Node*& head, int pos, int val);//插入中间节点
int getLength(Node* head);//获取链表长度
void deleteNode(Node* head, int pos);//删除节点
int main() {
    Node* head = nullptr;  // 初始化头指针为空
    for (int i = 0; i < 5; i++) {
        insert(head, i);
    }
    printList(head);
    deleteNode(head, 2);
    printList(head);
	return 0;
}
int getLength(Node* head) {//获取链表长度
    int len = 0;//链表长度
    Node* cur = head;//游标
    while (cur != nullptr) {//游标不为空
        len++;//链表长度加1
        cur = cur->next;//游标后移
    }
    return len;
}
//中间插入节点
void insertMid(Node*& head,int pos, int val) {//头指针，插入位置，插入数据
    //位置从0开始
    Node* newNode = new Node;//new 申请节点
    newNode->data = val;
    newNode->next = nullptr;
    int len = getLength(head);//获取链表长度
    if (pos < 0 || pos > len) {
        cout << "插入位置不合法" << endl;
        return;
    }
    if (pos == 0) { 
        newNode->next = head;//头插法
        head = newNode;//头指针指向新节点
    }
    else{
        Node* cur = head;//创建一个指针，指向头节点
        for (int i = 0; i < pos - 1; i++) {//循环找到第pos-1个节点
            cur = cur->next;
        }
        newNode->next = cur->next;
        cur->next = newNode;
    }
    //len++;
    cout << "插入成功" << endl;
}
// 打印链表内容
void printList(Node* head) {
    Node* temp = head;//创建临时节点指针
    while (temp != nullptr) {
        cout << temp->data << " -> ";
        temp = temp->next;
    }
    cout << "NULL" << endl;
}
//删除指定位置的节点
void deleteNode(Node* head, int pos) { //pos为位置
    //pos为位置 从0开始
    int len = getLength(head);//获取链表长度
    if (pos < 1 || pos > len) {
        cout << "位置不合法" << endl;
        return;
    }
    if (pos == 0) {
        Node* temp = head;//创建临时节点指针
        head = head->next;
        delete temp;//释放内存 释放节点
        return;
    }
    Node* cur = head;
    //找到要删除的节点的前一个节点
    for (int i = 0; i < pos - 1; i++) {
        cur = cur->next;
    }
    Node* temp = cur->next;//备份要删除的节点
    cur->next = cur->next->next;//删除节点
    delete temp;//释放内存 释放节点
}
/*
*/
    • @ 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
        456
        已通过
        0
        题解被赞
        1. 关于
        2. 联系我们
        3. 隐私
        4. 服务条款
        5. 版权申诉
        6. Language
        7. 兼容模式
        8. 主题
        4. 在线咨询
        5. Worker 0, 44ms
        6. Powered by Hydro v4.13.3 Community