插入到双链接列表

Question

我正在尝试为一个项目创建一个双链接列表容器。我不能使用任何std容器。必须对双链接列表进行排序。以下是我目前的代码：

#include <iostream>
using namespace std;

template <typename T>
class dll {
private:
    struct Node {
        Node* prev;
        Node* next;
        T data;
    };

    Node* head;
    Node* tail;

public:
    dll();
    ~dll();

    void insert(T value);

    bool empty() const { return head == tail; };
};

template <typename T> dll<T>::dll() {
    head = nullptr;
    tail = head;
}

template <typename T> dll<T>::~dll() {
    delete[] head;
}

template <typename T> void dll<T>::insert(T value) {
    Node *node = new Node;
    node->data = value;
    // Case 1: There are no nodes yet
    if (head == nullptr) {
        node->prev = nullptr;
        node->next = nullptr;
        head = node;
        tail = head;
    }
    else {
        // Case 2: There is more than one node
        Node *curr = head;
        if (curr->next != nullptr)
        {
            while (curr->next) {
                // If the value is less than the current value
                if (value < curr->data) {
                    Node *temp = new Node;
                    temp->data = curr->data;
                    temp->next = curr->next;
                    temp->prev = curr->prev;
                    node->next = temp;
                    node->prev = temp->prev;
                    curr->prev = node;
                }
                curr = curr->next;
            }
        }
        // Case 3: There is only one node
        else {
            node->prev = head;
            node->next = nullptr;
            tail = node;
        }
    }
}

int main() {
    dll<int> list;
    list.insert(10);
    list.insert(20);
    list.insert(15);
}

我遇到的问题是在我的插入函数中。我正在使用调试器，并在以下行插入代码：list.insert（10）；。

它正确地进入第一种情况，即head==nullptr并创建节点。当我进入下一行代码（list.insert（20））时，它会用这一行创建一个节点：node*node=newnode；但它正在创建具有head指向的内存地址的节点。

我在头变量上放了一个手表，节点变量和内存地址是相同的。基本上，它正在创建与上次插入相同的节点。

我不知道如何获取该行：Node*code=newnode；创造新事物。我在这里使用的新关键字是错误的吗？

Answer 1

首先，析构函数无效。此声明

delete[] head;

表示头部是一个数组。然而，head不是数组。它是指向Node类型的单个对象的指针。必须删除析构函数中列表的所有节点。析构函数可以如下所示

template <typename T> 
dll<T>::~dll() 
{
    while ( head )
    {
        Node *tmp = head;
        head = head->next;
        delete tmp;
    }
}

至于insert方法，它看起来非常简单。例如

template <typename T> 
void dll<T>::insert( const T &value ) 
{
    Node *current  = head;
    Node *previous = nullptr;

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

    Node *node = new Node { previous, current, value };

    if ( previous == nullptr ) head = node;
    else previous->next = node;

    if ( current  == nullptr ) tail = node;
    else current->prev = node;
}

并且没有任何需要和理由向结构节点添加构造函数。当它是一个集合体时更好。

这里有一个测试程序

#include <iostream>

template <typename T>
class dll 
{
private:
    struct Node 
    {
        Node *prev;
        Node *next;
        T data;
    };

    Node *head;
    Node *tail;

public:
    dll();
    ~dll();

    void insert( const T &value);

    bool empty() const { return head == tail; };

    void print() const;
};

template <typename T> 
dll<T>::dll() 
{
    head = tail = nullptr;
}

template <typename T> 
dll<T>::~dll() 
{
    while ( head )
    {
        Node *tmp = head;
        head = head->next;
        delete tmp;
    }
}

template <typename T> 
void dll<T>::insert( const T &value ) 
{
    Node *current  = head;
    Node *previous = nullptr;

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

    Node *node = new Node { previous, current, value };

    if ( previous == nullptr ) head = node;
    else previous->next = node;

    if ( current  == nullptr ) tail = node;
    else current->prev = node;
}

template <typename T> 
void dll<T>::print() const
{
    for ( Node *current = head; current; current = current->next )
    {
        std::cout << current->data << ' ';
    }
}

int main() 
{
    dll<int> list;

    list.insert( 10 );
    list.insert( 20 );
    list.insert( 15 );

    list.print();
    std::cout << std::endl;

    return 0;
}

输出是

10 15 20 

Answer 2

为了使Node的初始化更容易，让我们添加一个合理的构造函数，将prev和Next成员初始化为null。这使得以后的代码更容易。

struct Node {
    Node* prev;
    Node* next;
    T data;
    Node() : prev(nullptr), next(nullptr)
    {

    }
};

链表问题中总有四种情况需要注意。你得到了一些。插入到空列表中。在列表的前面插入，在列表的末尾插入，在列表的中间插入。

template <typename T> void dll<T>::insert(T value) {
    Node *node = new Node;
    node->data = value;

    // Case 1: There are no nodes yet
    if (head == nullptr) {
        head = node;
        tail = head;
        return;
    }


    // case 2 - inserting at the head of the list
    if (node->data < head->data)
    {
        node->next = head;
        head = node;
        return;
    }

    // case 3 - inserting at the end of the list
    if (node->data >= tail->data)
    {
        node->prev = tail;
        tail->next = node;
        tail = node;
        return;
    }

    // general case - inserting into the middle
    Node* probe = head;
    while (probe && (node->data >= probe->data))
    {
        probe = probe->next;
    }
    if (probe)
    {
        node->next = probe;
        node->prev = probe->prev;
        probe->prev->next = node;
        probe->prev = node;
        return;
    }

    // error - we shouldnt' reach this point. If we did, it meant the list was out of order to begin with.
    return;
}