欢迎使用本站,预祝练习时长两年半的选手们到成功! [本模块信息来自tem/def/head]

双向链表&增删改查-AI生成

时间:2024-05-11 13:07 作者:admin 点击:
在C++中,双向链表是一种常见的数据结构,它由一系列节点组成,每个节点包含数据部分和两个指针,分别指向前一个节点和后一个节点。 以下是手写双向链表并完成基本的增删改查功

在C++中,双向链表是一种常见的数据结构,它由一系列节点组成,每个节点包含数据部分和两个指针,分别指向前一个节点和后一个节点。

以下是手写双向链表并完成基本的增删改查功能的示例代码:

#include <iostream>

// 定义双向链表的节点结构
struct Node {
    int data;
    Node* prev;
    Node* next;
    Node(int val) : data(val), prev(nullptr), next(nullptr) {}
};

// 双向链表类
class DoublyLinkedList {
private:
    Node* head;
    Node* tail;
public:
    DoublyLinkedList() : head(nullptr), tail(nullptr) {}

    // 在链表头部添加元素
    void push_front(int value) {
        Node* newNode = new Node(value);
        newNode->next = head;
        if (head != nullptr) {
            head->prev = newNode;
        } else {
            tail = newNode; // 如果链表为空,tail也指向新节点
        }
        head = newNode;
    }

    // 在链表尾部添加元素
    void push_back(int value) {
        Node* newNode = new Node(value);
        if (tail != nullptr) {
            tail->next = newNode;
            newNode->prev = tail;
        } else {
            head = newNode; // 如果链表为空,head也指向新节点
        }
        tail = newNode;
    }

    // 删除链表头部的元素
    void pop_front() {
        if (head == nullptr) return;
        Node* temp = head;
        head = head->next;
        if (head != nullptr) {
            head->prev = nullptr;
        } else {
            tail = nullptr; // 如果链表只有一个元素,删除后链表变空
        }
        delete temp;
    }

    // 删除链表尾部的元素
    void pop_back() {
        if (tail == nullptr) return;
        Node* temp = tail;
        if (tail->prev != nullptr) {
            tail = tail->prev;
            tail->next = nullptr;
        } else {
            head = nullptr; // 如果链表只有一个元素,删除后链表变空
        }
        delete temp;
    }

    // 查找元素并修改
    bool update(int value, int newValue) {
        Node* current = head;
        while (current != nullptr) {
            if (current->data == value) {
                current->data = newValue;
                return true;
            }
            current = current->next;
        }
        return false;
    }

    // 删除指定值的元素
    bool remove(int value) {
        Node* current = head;
        while (current != nullptr) {
            if (current->data == value) {
                if (current->prev != nullptr) {
                    current->prev->next = current->next;
                } else {
                    head = current->next; // 如果删除的是头节点
                }
                if (current->next != nullptr) {
                    current->next->prev = current->prev;
                } else {
                    tail = current->prev; // 如果删除的是尾节点
                }
                delete current;
                return true;
            }
            current = current->next;
        }
        return false;
    }

    // 打印链表
    void print() {
        Node* current = head;
        while (current != nullptr) {
            std::cout << current->data << " ";
            current = current->next;
        }
        std::cout << std::endl;
    }

    // 析构函数,释放链表内存
    ~DoublyLinkedList() {
        while (head != nullptr) {
            pop_front();
        }
    }
};

int main() {
    DoublyLinkedList list;

    // 测试双向链表功能
    list.push_front(10);
    list.push_back(20);
    list.push_front(30);
    list.push_back(40);
    list.print(); // 应该输出: 30 10 20 40

    list.pop_front();
    list.pop_back();
    list.print(); // 应该输出: 20 40

    list.update(20, 50);
    list.print(); // 应该输出: 50 40

    if (list.remove(40)) {
        std::cout << "40 removed" << std::endl;
    }
    list.print(); // 应该输出: 50

    return 0;
}

这段代码定义了一个Node结构体,用于存储数据和指向前后节点的指针。

DoublyLinkedList类包含了双向链表的基本操作,如在头部和尾部添加元素、删除头部和尾部的元素、查找并修改元素、删除指定值的元素以及打印链表。

main函数中,我们创建了一个双向链表的实例,并测试了它的各种功能。


(责任编辑:admin)
    顶一下
    (0)
    0%
    踩一下
    (0)
    0%