C++数据结构之链表详解

链表是一种重要的数据结构，它可以动态的分配内存空间，实现灵活的元素插入，删除等操作。本文将详细讲解链表的定义、实现、常见操作以及链表的应用。

定义与特点

链表是一种线性表数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针。链表分为单向链表和双向链表，其中单向链表的每个节点只包含一个指针，指向下一个节点，而双向链表的每个节点包含两个指针，分别指向前一个节点和后一个节点。

链表的特点：
- 空间动态分配。
- 灵活的插入和删除操作。
- 随机访问效率较低，但插入和删除操作的效率很高。

实现

链表的实现需要定义一个节点结构体，包含数据和指针部分。下面是单向链表实现的代码：

struct ListNode {
    int val;        //数据部分
    ListNode* next; //指针部分
    ListNode(int x) : val(x), next(nullptr) {} //构造函数
};

常见操作

链表操作包括节点的插入、删除、查找等，下面介绍常用的操作：

节点的插入

链表的节点插入操作包括头部插入和尾部插入两种方式，可以通过指针操作实现。

//头部插入
ListNode* insertHead(ListNode* head, int val) {
    ListNode* new_node = new ListNode(val);
    new_node->next = head;
    return new_node;
}

//尾部插入
ListNode* insertTail(ListNode* head, int val) {
    if (!head) {
        return new ListNode(val);
    }
    ListNode* curr = head;
    while (curr->next) {
        curr = curr->next;
    }
    curr->next = new ListNode(val);
    return head;
}

节点的删除

链表的节点删除同样包括头部删除和尾部删除两种方式，需要将指针指向下一个节点或前一个节点，再释放删除的节点。

//头部删除
ListNode* deleteHead(ListNode* head) {
    if (!head) {
        return nullptr;
    }
    ListNode* temp = head->next;
    delete head;
    return temp;
}

//尾部删除
ListNode* deleteTail(ListNode* head) {
    if (!head) {
        return nullptr;
    }
    if (!head->next) {
        delete head;
        return nullptr;
    }
    ListNode* curr = head;
    while (curr->next->next) {
        curr = curr->next;
    }
    delete curr->next;
    curr->next = nullptr;
    return head;
}

节点的查找

链表的节点查找包括按值查找和按位置查找两种方式。

//按值查找
ListNode* findByValue(ListNode* head, int val) {
    ListNode* curr = head;
    while (curr && curr->val != val) {
        curr = curr->next;
    }
    return curr;
}

//按位置查找
ListNode* findByIndex(ListNode* head, int index) {
    ListNode* curr = head;
    int i = 0;
    while (curr && i != index) {
        curr = curr->next;
        i++;
    }
    return curr;
}

链表的应用

链表可用于实现栈、队列、哈希表等数据结构，同时也可以用于解决一些算法问题，如链表反转、链表合并等问题。

下面是链表合并的实现：

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    ListNode dummy(0);
    ListNode* curr = &dummy;
    while (l1 && l2) {
        if (l1->val < l2->val) {
            curr->next = l1;
            l1 = l1->next;
        } else {
            curr->next = l2;
            l2 = l2->next;
        }
        curr = curr->next;
    }
    curr->next = l1 ? l1 : l2;
    return dummy.next;
}

示例说明

假设现在有两个单向链表，l1表示[1,2,4]，l2表示[1,3,4]，需要将这两个链表合并成一个新的链表。

ListNode* l1 = new ListNode(1);
l1->next = new ListNode(2);
l1->next->next = new ListNode(4);

ListNode* l2 = new ListNode(1);
l2->next = new ListNode(3);
l2->next->next = new ListNode(4);

ListNode* l3 = mergeTwoLists(l1, l2);

最终得到的合并后的链表l3表示[1,1,2,3,4,4]。

另外一个示例是如何使用链表实现栈数据结构，下面是代码示例：

class MyStack {
public:
    /** Initialize your data structure here. */
    MyStack() {
        top_ = nullptr;
    }

    /** Push element x onto stack. */
    void push(int x) {
        ListNode* new_node = new ListNode(x);
        new_node->next = top_;
        top_ = new_node;
    }

    /** Removes the element on top of the stack and returns that element. */
    int pop() {
        if (!top_) {
            return -1;
        }
        ListNode* temp = top_;
        top_ = top_->next;
        int val = temp->val;
        delete temp;
        return val;
    }

    /** Get the top element. */
    int top() {
        return top_->val;
    }

    /** Returns whether the stack is empty. */
    bool empty() {
        return top_ == nullptr;
    }

private:
    ListNode* top_;
};

总结

链表是一种十分重要的数据结构，在算法问题中也非常常见。本文介绍了链表的定义、实现、常见操作和应用，并给出了两个示例说明链表的使用。希望本文可以帮助读者更好的掌握链表的知识。