一种用于双向链表C++的插入方法

双向链表的插入方法

基础概念

双向链表（Doubly Linked List）是一种链式数据结构，其中每个节点包含三个部分：数据域、前驱指针（指向前一个节点）和后继指针（指向后一个节点）。这种结构允许从任意节点向前或向后遍历链表。

插入方法的优势

灵活性：双向链表允许在任何位置插入或删除节点，而不需要移动其他节点。
高效查找：虽然链表的查找效率不如数组，但双向链表可以通过前驱和后继指针快速定位前后节点。
内存利用率：链表的节点可以动态分配内存，不需要预先分配固定大小的数组。

插入方法的类型

头插法：在链表头部插入新节点。
尾插法：在链表尾部插入新节点。
中间插法：在链表的任意位置插入新节点。

应用场景

双向链表广泛应用于需要频繁插入和删除操作的场景，例如：

LRU缓存：最近最少使用的缓存淘汰算法。
双向链表栈：结合栈和链表的优点，实现高效的入栈和出栈操作。
图和树的遍历：在某些遍历算法中，双向链表可以用于存储路径或状态。

插入方法的实现

以下是一个C++实现双向链表插入方法的示例代码：

#include <iostream>

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

// 定义双向链表类
class DoublyLinkedList {
public:
    DoublyLinkedList() : head(nullptr), tail(nullptr) {}

    // 头插法
    void insertAtHead(int value) {
        Node* newNode = new Node(value);
        if (!head) {
            head = tail = newNode;
        } else {
            newNode->next = head;
            head->prev = newNode;
            head = newNode;
        }
    }

    // 尾插法
    void insertAtTail(int value) {
        Node* newNode = new Node(value);
        if (!tail) {
            head = tail = newNode;
        } else {
            newNode->prev = tail;
            tail->next = newNode;
            tail = newNode;
        }
    }

    // 中间插法
    void insertAtPosition(int value, int position) {
        if (position <= 0) {
            insertAtHead(value);
            return;
        }

        Node* newNode = new Node(value);
        Node* current = head;
        int count = 0;

        while (current && count < position - 1) {
            current = current->next;
            count++;
        }

        if (!current) {
            insertAtTail(value);
        } else {
            newNode->next = current->next;
            newNode->prev = current;
            if (current->next) {
                current->next->prev = newNode;
            } else {
                tail = newNode;
            }
            current->next = newNode;
        }
    }

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

private:
    Node* head;
    Node* tail;
};

int main() {
    DoublyLinkedList list;
    list.insertAtHead(1);
    list.insertAtTail(3);
    list.insertAtPosition(2, 2);
    list.printList(); // 输出: 1 2 3
    return 0;
}