C++超详细讲解单链表的实现

首先我们来了解一下单链表的概念。

单链表是一种常见的数据结构，在计算机科学中被广泛使用。它是由节点所组成的数据结构，其中每个节点都包含两部分，一个是存储数据的元素，另一个是指向下一个节点的指针。单链表的首节点被称为头部，而最后一个节点则被称为尾部。单链表可以通过在头部插入和删除元素来实现高效地数据操作。接下来我们将讲解如何实现一个 C++ 版的单链表。

实现单链表

首先，我们需要定义一个节点结构体，表示单链表的每一个节点。它包括一个存储数据的元素和一个指向下一个节点的指针。

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

接着，我们需要定义一个链表类 LinkedList，用于实现单链表操作：

class LinkedList {
public:
    LinkedList() : head(nullptr) {}

    void add(int val);  // 添加元素
    bool remove(int val);  // 删除元素
    void display();  // 打印链表

private:
    ListNode* head;  // 链表头节点
};

我们通过 LinkedList 类提供的接口 add、remove、display 来操作单链表。

add 函数用于向链表中添加节点。当链表为空时，需要创建新的头节点。当链表不为空时，需要遍历到尾节点，然后将节点添加到链表尾部。

void LinkedList::add(int val) {
    ListNode* node = new ListNode(val);
    if (!head) {
        head = node;
    } else {
        ListNode* cur = head;
        while (cur->next) {
            cur = cur->next;
        }
        cur->next = node;
    }
}

remove 函数用于删除链表中的节点。需要遍历链表，查找到对应的节点，然后将其从链表中删除。

bool LinkedList::remove(int val) {
    ListNode dummy(0);
    dummy.next = head;
    ListNode* cur = &dummy;
    while (cur->next) {
        if (cur->next->val == val) {
            cur->next = cur->next->next;
            return true;
        }
        cur = cur->next;
    }
    return false;
}

display 函数用于打印链表中的元素。需要遍历链表，将元素依次输出。

void LinkedList::display() {
    ListNode* cur = head;
    while (cur) {
        std::cout << cur->val << "->";
        cur = cur->next;
    }
    std::cout << "null\n";
}

示例说明

我们可以使用以下代码来测试单链表的实现：

int main() {
    LinkedList list;

    // 添加节点
    list.add(1);
    list.add(2);
    list.add(3);

    // 打印链表
    list.display();  // output: 1->2->3->null

    // 删除节点
    list.remove(2);

    // 打印链表
    list.display();  // output: 1->3->null

    return 0;
}

在这个示例中，我们创建了一个 LinkedList 对象，然后向链表中添加节点，并使用 display 函数打印链表。接着，我们删除了节点 2，并再次使用 display 函数打印链表，可以看到节点 2 已经被删除了。

另外一个示例是，我们可以使用单链表来计算两个数字的和。具体实现可以参考以下代码：

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    ListNode dummy(0);
    ListNode* cur = &dummy;
    int carry = 0;
    while (l1 || l2 || carry) {
        int sum = (l1 ? l1->val : 0) + (l2 ? l2->val : 0) + carry;
        carry = sum / 10;
        cur->next = new ListNode(sum % 10);
        cur = cur->next;
        if (l1) l1 = l1->next;
        if (l2) l2 = l2->next;
    }
    return dummy.next;
}

这个函数接收两个链表作为参数，并返回它们的和的链表。在函数内部，我们使用了循环来遍历链表节点，对节点上的值进行求和，然后将结果存储在新的链表节点上。需要注意的是，如果当前节点为空，我们需要将其值置为 0。

以上就是 C++ 实现单链表的详细攻略。