C++指针在链表操作中的应用方式

C++指针在链表操作中的应用方式

链表基础概念

在深入探讨 C++ 指针在链表操作中的应用之前，我们先来回顾一下链表的基本概念。链表是一种常见的动态数据结构，它由一系列节点组成，每个节点包含两部分：数据部分和指向下一个节点的指针（在双向链表中，还包含指向前一个节点的指针）。与数组不同，链表中的节点在内存中并不一定是连续存储的，这使得链表在插入和删除操作上具有更高的灵活性。

链表主要分为单链表、双向链表和循环链表。单链表的每个节点只有一个指向后继节点的指针；双向链表的节点除了有指向下一个节点的指针外，还有指向前一个节点的指针；循环链表则是链表的最后一个节点指向链表的头节点，形成一个环形结构。

C++指针基础

指针是 C++ 中一个强大且重要的特性，它允许我们直接操作内存地址。通过指针，我们可以动态地分配和释放内存，实现数据结构的灵活操作。在链表中，指针用于连接各个节点，构建起节点之间的逻辑关系。

定义指针变量的语法是在变量类型后加上 * 符号。例如，要定义一个指向 int 类型的指针，可以这样写：

int *ptr;

这里，ptr 就是一个指向 int 类型数据的指针。要让指针指向一个实际的变量，我们使用取地址符 &。例如：

int num = 10;
ptr = #

此时，ptr 就指向了变量 num 的内存地址。通过指针访问其所指向的变量的值，我们使用解引用符 *。例如：

cout << *ptr << endl; // 输出 10

单链表操作中的指针应用

单链表节点的定义

在 C++ 中，我们通过结构体来定义单链表的节点。每个节点包含数据和指向下一个节点的指针。下面是一个简单的单链表节点定义示例：

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

在这个定义中，data 用于存储节点的数据，next 是一个指向 ListNode 类型的指针，用于指向下一个节点。构造函数 ListNode(int val) 用于初始化节点的数据，并将 next 指针初始化为 nullptr，表示当前节点是链表的最后一个节点。

单链表的创建

创建单链表通常是通过逐个添加节点来完成的。我们可以从一个空链表开始，每次创建一个新节点，并将其连接到链表的末尾。下面是一个创建单链表的函数示例：

ListNode* createList(int arr[], int n) {
    if (n == 0) return nullptr;
    ListNode *head = new ListNode(arr[0]);
    ListNode *current = head;
    for (int i = 1; i < n; ++i) {
        current->next = new ListNode(arr[i]);
        current = current->next;
    }
    return head;
}

在这个函数中，首先根据数组的第一个元素创建链表的头节点。然后通过一个循环，逐个创建新节点并将它们连接到链表的末尾。current 指针始终指向链表的最后一个节点，以便进行新节点的连接操作。

单链表的遍历

遍历单链表是最基本的操作之一，通过指针我们可以顺序访问链表中的每个节点。下面是一个遍历单链表并输出节点数据的函数：

void traverseList(ListNode *head) {
    ListNode *current = head;
    while (current != nullptr) {
        cout << current->data << " ";
        current = current->next;
    }
    cout << endl;
}

在这个函数中，current 指针从链表的头节点开始，每次循环通过 current = current->next 移动到下一个节点，直到 current 为 nullptr，表示已经遍历完整个链表。

单链表的插入操作

单链表的插入操作可以分为在链表头部插入、在链表中间插入和在链表尾部插入。

在链表头部插入：在链表头部插入新节点是比较简单的操作。我们只需要创建一个新节点，然后让新节点的 next 指针指向原来的头节点，最后将头指针更新为新节点。下面是实现代码：

ListNode* insertAtHead(ListNode *head, int val) {
    ListNode *newNode = new ListNode(val);
    newNode->next = head;
    return newNode;
}

在链表中间插入：在链表中间插入节点需要找到插入位置的前一个节点。假设我们要在值为 target 的节点之后插入新节点，代码如下：

ListNode* insertAfter(ListNode *head, int target, int val) {
    ListNode *current = head;
    while (current != nullptr && current->data != target) {
        current = current->next;
    }
    if (current == nullptr) return head;
    ListNode *newNode = new ListNode(val);
    newNode->next = current->next;
    current->next = newNode;
    return head;
}

在这个函数中，首先通过循环找到值为 target 的节点。如果找到了，就创建新节点并将其插入到 target 节点之后。

在链表尾部插入：在链表尾部插入节点类似于创建链表时逐个添加节点的操作。我们需要找到链表的最后一个节点，然后让最后一个节点的 next 指针指向新节点。代码如下：

ListNode* insertAtTail(ListNode *head, int val) {
    ListNode *newNode = new ListNode(val);
    if (head == nullptr) return newNode;
    ListNode *current = head;
    while (current->next != nullptr) {
        current = current->next;
    }
    current->next = newNode;
    return head;
}

单链表的删除操作

单链表的删除操作同样需要通过指针来完成。删除操作也分为删除链表头部节点、删除链表中间节点和删除链表尾部节点。

删除链表头部节点：删除链表头部节点只需要将头指针指向头节点的下一个节点，并释放头节点的内存。代码如下：

ListNode* deleteHead(ListNode *head) {
    if (head == nullptr) return nullptr;
    ListNode *temp = head;
    head = head->next;
    delete temp;
    return head;
}

删除链表中间节点：删除链表中间节点需要找到要删除节点的前一个节点。假设要删除值为 target 的节点，代码如下：

ListNode* deleteNode(ListNode *head, int target) {
    if (head == nullptr) return nullptr;
    if (head->data == target) {
        ListNode *temp = head;
        head = head->next;
        delete temp;
        return head;
    }
    ListNode *current = head;
    while (current->next != nullptr && current->next->data != target) {
        current = current->next;
    }
    if (current->next == nullptr) return head;
    ListNode *temp = current->next;
    current->next = current->next->next;
    delete temp;
    return head;
}

在这个函数中，首先判断头节点是否是要删除的节点。如果不是，通过循环找到要删除节点的前一个节点，然后进行删除操作。

删除链表尾部节点：删除链表尾部节点需要找到链表的倒数第二个节点，然后将其 next 指针设置为 nullptr，并释放最后一个节点的内存。代码如下：

ListNode* deleteTail(ListNode *head) {
    if (head == nullptr) return nullptr;
    if (head->next == nullptr) {
        delete head;
        return nullptr;
    }
    ListNode *current = head;
    while (current->next->next != nullptr) {
        current = current->next;
    }
    ListNode *temp = current->next;
    current->next = nullptr;
    delete temp;
    return head;
}

双向链表操作中的指针应用

双向链表节点的定义

双向链表的节点除了包含数据和指向下一个节点的指针外，还包含指向前一个节点的指针。下面是双向链表节点的定义：

struct DoublyListNode {
    int data;
    DoublyListNode *prev;
    DoublyListNode *next;
    DoublyListNode(int val) : data(val), prev(nullptr), next(nullptr) {}
};

双向链表的创建

创建双向链表的过程与创建单链表类似，但在连接节点时需要同时设置 prev 和 next 指针。下面是一个创建双向链表的函数示例：

DoublyListNode* createDoublyList(int arr[], int n) {
    if (n == 0) return nullptr;
    DoublyListNode *head = new DoublyListNode(arr[0]);
    DoublyListNode *current = head;
    for (int i = 1; i < n; ++i) {
        DoublyListNode *newNode = new DoublyListNode(arr[i]);
        newNode->prev = current;
        current->next = newNode;
        current = newNode;
    }
    return head;
}

双向链表的遍历

双向链表可以从前往后遍历，也可以从后往前遍历。从前往后遍历的代码如下：

void traverseDoublyListForward(DoublyListNode *head) {
    DoublyListNode *current = head;
    while (current != nullptr) {
        cout << current->data << " ";
        current = current->next;
    }
    cout << endl;
}

从后往前遍历需要从链表的最后一个节点开始，通过 prev 指针逐个访问前一个节点。代码如下：

void traverseDoublyListBackward(DoublyListNode *head) {
    if (head == nullptr) return;
    DoublyListNode *current = head;
    while (current->next != nullptr) {
        current = current->next;
    }
    while (current != nullptr) {
        cout << current->data << " ";
        current = current->prev;
    }
    cout << endl;
}

双向链表的插入操作

双向链表的插入操作同样分为在头部插入、在中间插入和在尾部插入。

在链表头部插入：在双向链表头部插入新节点时，需要更新新节点的 next 指针和原头节点的 prev 指针，同时更新头指针。代码如下：

DoublyListNode* insertAtHeadDoubly(DoublyListNode *head, int val) {
    DoublyListNode *newNode = new DoublyListNode(val);
    if (head != nullptr) {
        head->prev = newNode;
        newNode->next = head;
    }
    return newNode;
}

在链表中间插入：在双向链表中间插入节点需要找到插入位置的前一个节点。假设要在值为 target 的节点之后插入新节点，代码如下：

DoublyListNode* insertAfterDoubly(DoublyListNode *head, int target, int val) {
    DoublyListNode *current = head;
    while (current != nullptr && current->data != target) {
        current = current->next;
    }
    if (current == nullptr) return head;
    DoublyListNode *newNode = new DoublyListNode(val);
    newNode->prev = current;
    newNode->next = current->next;
    if (current->next != nullptr) {
        current->next->prev = newNode;
    }
    current->next = newNode;
    return head;
}

在链表尾部插入：在双向链表尾部插入节点需要找到链表的最后一个节点，然后更新相关指针。代码如下：

DoublyListNode* insertAtTailDoubly(DoublyListNode *head, int val) {
    DoublyListNode *newNode = new DoublyListNode(val);
    if (head == nullptr) return newNode;
    DoublyListNode *current = head;
    while (current->next != nullptr) {
        current = current->next;
    }
    current->next = newNode;
    newNode->prev = current;
    return head;
}

双向链表的删除操作

双向链表的删除操作也需要更新多个指针。

删除链表头部节点：删除双向链表头部节点时，需要更新头指针以及新头节点的 prev 指针。代码如下：

DoublyListNode* deleteHeadDoubly(DoublyListNode *head) {
    if (head == nullptr) return nullptr;
    DoublyListNode *temp = head;
    head = head->next;
    if (head != nullptr) {
        head->prev = nullptr;
    }
    delete temp;
    return head;
}

删除链表中间节点：删除双向链表中间节点需要找到要删除节点的前一个节点和后一个节点，然后更新相关指针。假设要删除值为 target 的节点，代码如下：

DoublyListNode* deleteNodeDoubly(DoublyListNode *head, int target) {
    if (head == nullptr) return nullptr;
    DoublyListNode *current = head;
    while (current != nullptr && current->data != target) {
        current = current->next;
    }
    if (current == nullptr) return head;
    if (current->prev != nullptr) {
        current->prev->next = current->next;
    } else {
        head = current->next;
    }
    if (current->next != nullptr) {
        current->next->prev = current->prev;
    }
    delete current;
    return head;
}

删除链表尾部节点：删除双向链表尾部节点需要找到链表的倒数第二个节点，然后更新相关指针。代码如下：

DoublyListNode* deleteTailDoubly(DoublyListNode *head) {
    if (head == nullptr) return nullptr;
    if (head->next == nullptr) {
        delete head;
        return nullptr;
    }
    DoublyListNode *current = head;
    while (current->next->next != nullptr) {
        current = current->next;
    }
    DoublyListNode *temp = current->next;
    current->next = nullptr;
    delete temp;
    return head;
}

循环链表操作中的指针应用

循环链表节点的定义

循环链表节点的定义与单链表类似，但在构建链表时需要将最后一个节点的 next 指针指向头节点。下面是循环链表节点的定义：

struct CircularListNode {
    int data;
    CircularListNode *next;
    CircularListNode(int val) : data(val), next(nullptr) {}
};

循环链表的创建

创建循环链表时，最后一个节点的 next 指针需要指向头节点。下面是一个创建循环链表的函数示例：

CircularListNode* createCircularList(int arr[], int n) {
    if (n == 0) return nullptr;
    CircularListNode *head = new CircularListNode(arr[0]);
    CircularListNode *current = head;
    for (int i = 1; i < n; ++i) {
        current->next = new CircularListNode(arr[i]);
        current = current->next;
    }
    current->next = head;
    return head;
}

循环链表的遍历

循环链表的遍历需要注意终止条件，因为链表是环形的。我们可以设置一个标志来避免无限循环。下面是一个遍历循环链表的函数示例：

void traverseCircularList(CircularListNode *head) {
    if (head == nullptr) return;
    CircularListNode *current = head;
    do {
        cout << current->data << " ";
        current = current->next;
    } while (current != head);
    cout << endl;
}

循环链表的插入操作

循环链表的插入操作在不同位置有不同的处理方式。

在链表头部插入：在循环链表头部插入新节点时，需要找到链表的最后一个节点，并更新相关指针。代码如下：

CircularListNode* insertAtHeadCircular(CircularListNode *head, int val) {
    CircularListNode *newNode = new CircularListNode(val);
    if (head == nullptr) {
        newNode->next = newNode;
        return newNode;
    }
    CircularListNode *current = head;
    while (current->next != head) {
        current = current->next;
    }
    newNode->next = head;
    current->next = newNode;
    return newNode;
}

在链表中间插入：在循环链表中间插入节点需要找到插入位置的前一个节点。假设要在值为 target 的节点之后插入新节点，代码如下：

CircularListNode* insertAfterCircular(CircularListNode *head, int target, int val) {
    if (head == nullptr) return nullptr;
    CircularListNode *current = head;
    do {
        if (current->data == target) {
            CircularListNode *newNode = new CircularListNode(val);
            newNode->next = current->next;
            current->next = newNode;
            return head;
        }
        current = current->next;
    } while (current != head);
    return head;
}

循环链表的删除操作

循环链表的删除操作也需要注意更新指针，以保持链表的环形结构。

删除链表头部节点：删除循环链表头部节点时，需要找到链表的最后一个节点，并更新头指针和最后一个节点的 next 指针。代码如下：

CircularListNode* deleteHeadCircular(CircularListNode *head) {
    if (head == nullptr) return nullptr;
    if (head->next == head) {
        delete head;
        return nullptr;
    }
    CircularListNode *current = head;
    while (current->next != head) {
        current = current->next;
    }
    CircularListNode *temp = head;
    head = head->next;
    current->next = head;
    delete temp;
    return head;
}

删除链表中间节点：删除循环链表中间节点需要找到要删除节点的前一个节点，然后更新相关指针。假设要删除值为 target 的节点，代码如下：

CircularListNode* deleteNodeCircular(CircularListNode *head, int target) {
    if (head == nullptr) return nullptr;
    if (head->data == target && head->next == head) {
        delete head;
        return nullptr;
    }
    CircularListNode *current = head;
    CircularListNode *prev = nullptr;
    do {
        if (current->data == target) {
            if (prev == nullptr) {
                return deleteHeadCircular(head);
            }
            prev->next = current->next;
            delete current;
            return head;
        }
        prev = current;
        current = current->next;
    } while (current != head);
    return head;
}

通过以上对 C++ 指针在单链表、双向链表和循环链表操作中的应用介绍，我们可以看到指针在链表数据结构的实现和操作中起着核心作用。正确使用指针能够高效地实现链表的各种操作，为复杂数据结构和算法的构建提供基础。在实际编程中，需要特别注意指针的内存管理，避免出现内存泄漏和悬空指针等问题。