非循环的双链表

非循环的双向链表是一种数据结构，它可以在每个节点中存储数据，同时包含指向前一个节点和后一个节点的指针。该链表的头节点指向第一个节点，尾节点指向最后一个节点。

非循环的双向链表相比于单向链表有更多的优点，例如可以在O(1)的时间内访问前一个节点，而不需要遍历整个链表。此外，它还可以在O(1)的时间内在任意位置插入或删除节点。

以下是一个简单的非循环的双向链表的实现：

#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node* prev;
    Node* next;
};

class DoublyLinkedList {
private:
    Node* head;
    Node* tail;
public:
    DoublyLinkedList() {
        head = NULL;
        tail = NULL;
    }

    void addNode(int data) {
        Node* newNode = new Node();
        newNode->data = data;
        newNode->prev = NULL;
        newNode->next = NULL;

        if (head == NULL) {
            head = newNode;
            tail = newNode;
        }
        else {
            tail->next = newNode;
            newNode->prev = tail;
            tail = newNode;
        }
    }

    void display() {
        Node* current = head;
        if (head == NULL) {
            cout << "List is empty" << endl;
            return;
        }
        while (current != NULL) {
            cout << current->data << " ";
            current = current->next;
        }
        cout << endl;
    }

    void reverse() {
        Node* current = head;
        Node* temp = NULL;

        while (current != NULL) {
            temp = current->prev;
            current->prev = current->next;
            current->next = temp;
            current = current->prev;
        }

        if (temp != NULL) {
            head = temp->prev;
        }
    }
};

int main() {
    DoublyLinkedList dll;
    dll.addNode(1);
    dll.addNode(2);
    dll.addNode(3);
    dll.addNode(4);
    dll.addNode(5);

    cout << "Original list: ";
    dll.display();

    dll.reverse();
    cout << "Reversed list: ";
    dll.display();

    return 0;
}

在上面的代码中，我们定义了一个名为Node的类来表示链表的节点。然后，我们定义了一个名为DoublyLinkedList的类来表示非循环的双向链表。

该类具有三个成员变量：头指针head，尾指针tail和一个整数变量data。addNode方法用于在链表的末尾添加一个新节点，display方法用于显示链表中所有节点的值，reverse方法用于反转链表中所有节点的顺序。

在主函数中，我们创建了一个名为dll的DoublyLinkedList对象，并在其中添加了5个节点。然后，我们先打印原始链表，然后调用reverse方法反转链表，并再次打印链表。