C++ 数据结构超详细讲解单链表

什么是单链表

单链表是一种常见的线性数据结构，它由若干个节点组成，每个节点包含两部分内容：数据域和指针域。其中数据域存储节点所携带的数据，而指针域存储下一个节点的地址。

单链表的性质在于每个节点只有一个指针域，而第一个节点叫做头节点，通常不存放数据，只用来标注链表的起始位置。最后一个节点的指针域指向 NULL，即表示链表的结束。

如何实现单链表

在 C++ 中，我们可以定义一个结构体来表示单链表中的节点，如下所示：

struct ListNode {
    int val; // 存储节点的值
    ListNode* next; // 指向下一个节点的指针
    ListNode(int x) : val(x), next(nullptr) {} // 构造函数
};

有了这个节点结构体，我们就可以创建一个单链表了。在这里，我将实现一个具有常用操作的单链表类，包括节点的插入、删除、遍历等方法，具体实现如下：

class LinkedList {
public:
    LinkedList() : m_head(nullptr), m_size(0) {}
    ~LinkedList() {
        ListNode* temp = m_head;
        while (temp) {
            ListNode* cur = temp;
            temp = temp->next;
            delete cur;
        }
    }

    // 在单链表的开头插入节点
    void addFirst(int val) {
        ListNode* newNode = new ListNode(val);
        newNode->next = m_head;
        m_head = newNode;
        ++m_size;
    }

    // 在单链表的末尾插入节点
    void addLast(int val) {
        ListNode* newNode = new ListNode(val);
        if (m_head == nullptr) {
            m_head = newNode;
        } else {
            ListNode* temp = m_head;
            while (temp->next) {
                temp = temp->next;
            }
            temp->next = newNode;
        }
        ++m_size;
    }

    // 在单链表的指定位置插入节点
    void add(int index, int val) {
        if (index <= 0) {
            addFirst(val);
        } else if (index >= m_size) {
            addLast(val);
        } else {
            ListNode* newNode = new ListNode(val);
            ListNode* p = m_head;
            for (int i = 0; i < index - 1; ++i) {
                p = p->next;
            }
            newNode->next = p->next;
            p->next = newNode;
            ++m_size;
        }
    }

    // 删除单链表的第一个节点
    void removeFirst() {
        if (m_head) {
            ListNode* temp = m_head;
            m_head = m_head->next;
            delete temp;
            --m_size;
        }
    }

    // 删除单链表的最后一个节点
    void removeLast() {
        if (m_head) {
            if (m_head->next == nullptr) {
                delete m_head;
                m_head = nullptr;
            } else {
                ListNode* temp = m_head;
                while (temp->next->next) {
                    temp = temp->next;
                }
                delete temp->next;
                temp->next = nullptr;
            }
            --m_size;
        }
    }

    // 删除单链表的指定位置的节点
    void remove(int index) {
        if (index <= 0) {
            removeFirst();
        } else if (index >= m_size - 1) {
            removeLast();
        } else {
            ListNode* p = m_head;
            for (int i = 0; i < index - 1; ++i) {
                p = p->next;
            }
            ListNode* temp = p->next;
            p->next = temp->next;
            delete temp;
            --m_size;
        }
    }

    // 获取单链表的第一个节点
    ListNode* getFirst() const {
        return m_head;
    }

    // 获取单链表的最后一个节点
    ListNode* getLast() const {
        ListNode* temp = m_head;
        while (temp && temp->next) {
            temp = temp->next;
        }
        return temp;
    }

    // 获取单链表的指定位置的节点
    ListNode* get(int index) const {
        ListNode* p = m_head;
        for (int i = 0; i < index; ++i) {
            p = p->next;
        }
        return p;
    }

    // 获取单链表的节点个数
    int getSize() const {
        return m_size;
    }

    // 打印单链表的值
    void printList() const {
        ListNode* temp = m_head;
        while (temp) {
            std::cout << temp->val << " ";
            temp = temp->next;
        }
        std::cout << std::endl;
    }

private:
    ListNode* m_head; // 链表的头指针
    int m_size; // 链表的节点个数
};

单链表的使用

有了上面实现的单链表类，我们就可以轻松地在程序中使用单链表了。下面是一些使用示例：

示例一：将数组转为单链表

// 将数组转为单链表
LinkedList list;
int nums[] = {1, 2, 3, 4, 5};
int len = sizeof(nums) / sizeof(nums[0]);
for (int i = 0; i < len; ++i) {
    list.addLast(nums[i]);
}
// 打印单链表
list.printList();
// 输出：1 2 3 4 5

示例二：反转单链表

// 反转单链表
ListNode* newHead = nullptr;
ListNode* temp;
while (list.getFirst()) {
    temp = list.getFirst()->next;
    list.getFirst()->next = newHead;
    newHead = list.getFirst();
    list.removeFirst();
}
// 将反转后的结果转为单链表
list.getFirst() = newHead;
// 打印单链表
list.printList();
// 输出：5 4 3 2 1

总结

在 C++ 中实现单链表并不难，只需要用一个节点结构体表示链表中的节点，再用一个类来表示整个单链表，然后实现一些常用操作即可。单链表的操作就是对节点的操作，一定要注意节点为空的情况。