当前位置:   article > 正文

【C++】链表

【C++】链表

链表是一种常见的动态数据结构,与数组相比,它在插入和删除操作中具有更高的效率。链表的每个元素称为节点(Node),节点包含两个部分:数据域(存储数据)和指针域(指向下一个节点的指针)。链表的最大特点是节点的内存位置不需要连续,可以通过指针来链接在一起。

C++ 链表的类型

  1. 单向链表 (Singly Linked List): 每个节点只有一个指针,指向链表中的下一个节点。链表的末尾节点指针指向 nullptr,表示链表的结束。
  2. 双向链表 (Doubly Linked List): 每个节点有两个指针,一个指向下一个节点,另一个指向前一个节点。这样可以从头到尾遍历链表,也可以从尾到头遍历链表。
  3. 循环链表 (Circular Linked List): 链表的最后一个节点指向第一个节点,使链表成为一个环。
  4. 循环双向链表 (Circular Doubly Linked List): 双向链表的扩展,尾节点的next指针指向头节点,头节点的prev指针指向尾节点。

单向链表的结构与操作

1. 节点结构

单向链表的节点包含数据部分和指针部分。结构如下:

struct Node {
    int data;      // 存储数据
    Node* next;    // 指向下一个节点的指针
};
2. 初始化链表

链表的初始化通常从一个空链表开始,也就是头指针指向 nullptr

Node* head = nullptr;  // 初始化为空链表
3. 插入操作

在链表末尾插入节点:我们可以遍历链表,直到找到末尾节点,将新节点插入到末尾。

void insertAtEnd(Node*& head, int value) {
    Node* newNode = new Node();  // 创建新节点
    newNode->data = value;       // 设置节点的数据
    newNode->next = nullptr;     // 新节点的下一个节点为空

    if (head == nullptr) {       // 如果链表为空,新节点作为头节点
        head = newNode;
    } else {
        Node* temp = head;
        while (temp->next != nullptr) { // 找到末尾节点
            temp = temp->next;
        }
        temp->next = newNode;  // 将新节点连接到末尾
    }
}

在链表开头插入节点:直接将新节点的 next 指向当前头节点,并将头节点指向新节点。

void insertAtBeginning(Node*& head, int value) {
    Node* newNode = new Node();  // 创建新节点
    newNode->data = value;       // 设置节点的数据
    newNode->next = head;        // 将新节点的 next 指向当前的头节点
    head = newNode;              // 将头节点更新为新节点
}
4. 删除操作

删除指定值的节点:我们需要遍历链表,找到值为 value 的节点并删除。

void remove(Node*& head, int value) {
    if (head == nullptr) return;  // 如果链表为空,直接返回

    if (head->data == value) {    // 如果头节点是要删除的节点
        Node* temp = head;
        head = head->next;        // 头节点指向下一个节点
        delete temp;              // 释放原头节点
        return;
    }

    Node* current = head;
    Node* previous = nullptr;

    while (current != nullptr && current->data != value) {
        previous = current;
        current = current->next;
    }

    if (current == nullptr) return; // 没有找到要删除的节点

    previous->next = current->next; // 前一个节点指向当前节点的下一个节点
    delete current;                 // 释放当前节点
}
5. 遍历操作

遍历并打印链表:遍历链表,输出每个节点的值。

void printList(Node* head) {
    Node* temp = head;
    while (temp != nullptr) {
        std::cout << temp->data << " -> ";
        temp = temp->next;  // 移动到下一个节点
    }
    std::cout << "nullptr" << std::endl;
}
6. 搜索操作

查找某个值是否存在于链表中:遍历链表,查找目标值。

bool search(Node* head, int value) {
    Node* temp = head;
    while (temp != nullptr) {
        if (temp->data == value) {
            return true;  // 找到目标值
        }
        temp = temp->next;  // 移动到下一个节点
    }
    return false;  // 没找到目标值
}

双向链表的结构与操作

1. 节点结构

双向链表的节点包含数据部分,以及指向前一个节点和后一个节点的两个指针。

struct DoublyNode {
    int data;             // 存储数据
    DoublyNode* next;     // 指向下一个节点的指针
    DoublyNode* prev;     // 指向前一个节点的指针
};
2. 插入操作

在链表末尾插入节点:在双向链表中,插入新节点时不仅需要更新下一个节点的指针,还要更新前一个节点的指针。

void insertAtEnd(DoublyNode*& head, int value) {
    DoublyNode* newNode = new DoublyNode();  // 创建新节点
    newNode->data = value;
    newNode->next = nullptr;

    if (head == nullptr) {  // 如果链表为空
        newNode->prev = nullptr;
        head = newNode;
    } else {
        DoublyNode* temp = head;
        while (temp->next != nullptr) {
            temp = temp->next;
        }
        temp->next = newNode;
        newNode->prev = temp;
    }
}
3. 删除操作

删除指定值的节点:在双向链表中,删除节点时不仅要更新前一个节点的 next 指针,还要更新下一个节点的 prev 指针。

void remove(DoublyNode*& head, int value) {
    if (head == nullptr) return;

    DoublyNode* current = head;

    while (current != nullptr && current->data != value) {
        current = current->next;
    }

    if (current == nullptr) return;  // 没有找到要删除的节点

    if (current->prev != nullptr) {
        current->prev->next = current->next;
    } else {
        head = current->next;
    }

    if (current->next != nullptr) {
        current->next->prev = current->prev;
    }

    delete current;
}

链表的优缺点

优点:

  1. 动态大小:链表不需要预先分配内存,节点可以根据需要动态增加和减少。
  2. 插入和删除操作高效:在已知位置的情况下,插入和删除操作可以在 O(1) 时间内完成,不需要移动其他元素。
  3. 内存利用率高:链表的节点存储是非连续的,更容易利用分散的内存空间。

缺点:

  1. 访问速度较慢:链表的访问速度相对较慢,因为需要从头开始遍历链表,找到目标节点。
  2. 额外的内存开销:链表的每个节点都需要额外的指针域来存储指针,这会增加内存开销。
  3. 不利于缓存:链表的节点存储位置不连续,不利于 CPU 缓存的利用,可能导致更多的缓存未命中。

适用场景

链表适合以下场景:

  • 频繁插入和删除操作:特别是中间或两端的插入和删除操作频繁时,链表能够更高效地完成这些操作。
  • 动态数据集:当数据的数量不确定,需要灵活的增长或缩减时,链表是一个不错的选择。

不适合以下场景:

  • 需要快速随机访问:如果需要频繁访问链表中的某个元素,链表的线性访问速度可能无法满足需求,数组在这种情况下表现更好。

通过对 C++ 链表的详细介绍及其代码示例,你可以更好地理解链表的结构和操作,并能够在合适的场景中应用链表数据结构

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/人工智能uu/article/detail/1021790
推荐阅读
相关标签
  

闽ICP备14008679号