C++数据结构之双向链表怎么实现

双向链表（Doubly Linked List）是一种常见的数据结构，它允许在链表中进行双向遍历。与单向链表不同，双向链表的每个节点不仅包含指向下一个节点的指针，还包含指向前一个节点的指针。这使得在双向链表中可以更方便地进行插入、删除和遍历操作。

双向链表的基本结构

在C++中，双向链表的节点通常定义为一个结构体或类，包含以下成员：

• data：存储节点的数据。
• prev：指向前一个节点的指针。
• next：指向下一个节点的指针。

struct Node {
    int data;
    Node* prev;
    Node* next;
};

双向链表的实现

1. 创建节点

首先，我们需要一个函数来创建一个新节点。这个函数将分配内存并初始化节点的data、prev和next指针。

Node* createNode(int data) {
    Node* newNode = new Node();
    newNode->data = data;
    newNode->prev = nullptr;
    newNode->next = nullptr;
    return newNode;
}

2. 插入节点

在双向链表中，插入操作可以在链表的头部、尾部或任意位置进行。以下是几种常见的插入操作：

在链表头部插入节点

void insertAtHead(Node** head, int data) {
    Node* newNode = createNode(data);
    if (*head == nullptr) {
        *head = newNode;
    } else {
        newNode->next = *head;
        (*head)->prev = newNode;
        *head = newNode;
    }
}

在链表尾部插入节点

void insertAtTail(Node** head, int data) {
    Node* newNode = createNode(data);
    if (*head == nullptr) {
        *head = newNode;
    } else {
        Node* temp = *head;
        while (temp->next != nullptr) {
            temp = temp->next;
        }
        temp->next = newNode;
        newNode->prev = temp;
    }
}

在指定位置插入节点

void insertAtPosition(Node** head, int data, int position) {
    if (position == 1) {
        insertAtHead(head, data);
        return;
    }
    Node* newNode = createNode(data);
    Node* temp = *head;
    for (int i = 1; i < position - 1 && temp != nullptr; i++) {
        temp = temp->next;
    }
    if (temp == nullptr) {
        std::cout << "Position out of range" << std::endl;
        return;
    }
    newNode->next = temp->next;
    if (temp->next != nullptr) {
        temp->next->prev = newNode;
    }
    temp->next = newNode;
    newNode->prev = temp;
}

3. 删除节点

删除操作也可以在链表的头部、尾部或任意位置进行。以下是几种常见的删除操作：

删除链表头部节点

void deleteAtHead(Node** head) {
    if (*head == nullptr) {
        std::cout << "List is empty" << std::endl;
        return;
    }
    Node* temp = *head;
    *head = (*head)->next;
    if (*head != nullptr) {
        (*head)->prev = nullptr;
    }
    delete temp;
}

删除链表尾部节点

void deleteAtTail(Node** head) {
    if (*head == nullptr) {
        std::cout << "List is empty" << std::endl;
        return;
    }
    Node* temp = *head;
    while (temp->next != nullptr) {
        temp = temp->next;
    }
    if (temp->prev != nullptr) {
        temp->prev->next = nullptr;
    } else {
        *head = nullptr;
    }
    delete temp;
}

删除指定位置的节点

void deleteAtPosition(Node** head, int position) {
    if (*head == nullptr) {
        std::cout << "List is empty" << std::endl;
        return;
    }
    Node* temp = *head;
    for (int i = 1; i < position && temp != nullptr; i++) {
        temp = temp->next;
    }
    if (temp == nullptr) {
        std::cout << "Position out of range" << std::endl;
        return;
    }
    if (temp->prev != nullptr) {
        temp->prev->next = temp->next;
    } else {
        *head = temp->next;
    }
    if (temp->next != nullptr) {
        temp->next->prev = temp->prev;
    }
    delete temp;
}

4. 遍历链表

双向链表可以从前向后或从后向前遍历。以下是两种遍历方式的实现：

从前向后遍历

void traverseForward(Node* head) {
    Node* temp = head;
    while (temp != nullptr) {
        std::cout << temp->data << " ";
        temp = temp->next;
    }
    std::cout << std::endl;
}

从后向前遍历

void traverseBackward(Node* head) {
    Node* temp = head;
    while (temp->next != nullptr) {
        temp = temp->next;
    }
    while (temp != nullptr) {
        std::cout << temp->data << " ";
        temp = temp->prev;
    }
    std::cout << std::endl;
}

完整示例

以下是一个完整的双向链表实现示例：

#include <iostream>

struct Node {
    int data;
    Node* prev;
    Node* next;
};

Node* createNode(int data) {
    Node* newNode = new Node();
    newNode->data = data;
    newNode->prev = nullptr;
    newNode->next = nullptr;
    return newNode;
}

void insertAtHead(Node** head, int data) {
    Node* newNode = createNode(data);
    if (*head == nullptr) {
        *head = newNode;
    } else {
        newNode->next = *head;
        (*head)->prev = newNode;
        *head = newNode;
    }
}

void insertAtTail(Node** head, int data) {
    Node* newNode = createNode(data);
    if (*head == nullptr) {
        *head = newNode;
    } else {
        Node* temp = *head;
        while (temp->next != nullptr) {
            temp = temp->next;
        }
        temp->next = newNode;
        newNode->prev = temp;
    }
}

void insertAtPosition(Node** head, int data, int position) {
    if (position == 1) {
        insertAtHead(head, data);
        return;
    }
    Node* newNode = createNode(data);
    Node* temp = *head;
    for (int i = 1; i < position - 1 && temp != nullptr; i++) {
        temp = temp->next;
    }
    if (temp == nullptr) {
        std::cout << "Position out of range" << std::endl;
        return;
    }
    newNode->next = temp->next;
    if (temp->next != nullptr) {
        temp->next->prev = newNode;
    }
    temp->next = newNode;
    newNode->prev = temp;
}

void deleteAtHead(Node** head) {
    if (*head == nullptr) {
        std::cout << "List is empty" << std::endl;
        return;
    }
    Node* temp = *head;
    *head = (*head)->next;
    if (*head != nullptr) {
        (*head)->prev = nullptr;
    }
    delete temp;
}

void deleteAtTail(Node** head) {
    if (*head == nullptr) {
        std::cout << "List is empty" << std::endl;
        return;
    }
    Node* temp = *head;
    while (temp->next != nullptr) {
        temp = temp->next;
    }
    if (temp->prev != nullptr) {
        temp->prev->next = nullptr;
    } else {
        *head = nullptr;
    }
    delete temp;
}

void deleteAtPosition(Node** head, int position) {
    if (*head == nullptr) {
        std::cout << "List is empty" << std::endl;
        return;
    }
    Node* temp = *head;
    for (int i = 1; i < position && temp != nullptr; i++) {
        temp = temp->next;
    }
    if (temp == nullptr) {
        std::cout << "Position out of range" << std::endl;
        return;
    }
    if (temp->prev != nullptr) {
        temp->prev->next = temp->next;
    } else {
        *head = temp->next;
    }
    if (temp->next != nullptr) {
        temp->next->prev = temp->prev;
    }
    delete temp;
}

void traverseForward(Node* head) {
    Node* temp = head;
    while (temp != nullptr) {
        std::cout << temp->data << " ";
        temp = temp->next;
    }
    std::cout << std::endl;
}

void traverseBackward(Node* head) {
    Node* temp = head;
    while (temp->next != nullptr) {
        temp = temp->next;
    }
    while (temp != nullptr) {
        std::cout << temp->data << " ";
        temp = temp->prev;
    }
    std::cout << std::endl;
}

int main() {
    Node* head = nullptr;

    insertAtHead(&head, 10);
    insertAtHead(&head, 20);
    insertAtTail(&head, 30);
    insertAtPosition(&head, 40, 2);

    std::cout << "Forward traversal: ";
    traverseForward(head);

    std::cout << "Backward traversal: ";
    traverseBackward(head);

    deleteAtHead(&head);
    deleteAtTail(&head);
    deleteAtPosition(&head, 2);

    std::cout << "Forward traversal after deletion: ";
    traverseForward(head);

    return 0;
}

总结

双向链表是一种功能强大的数据结构，它允许在链表中进行双向遍历。通过实现双向链表，我们可以更灵活地处理数据的插入、删除和遍历操作。本文介绍了如何在C++中实现双向链表，并提供了完整的代码示例。希望这篇文章能帮助你更好地理解和使用双向链表。