c++ - 将项目添加到双向链表的后面时遇到问题

Question

我是双向链表的新手。我正在处理几段代码:一个函数在前面添加一个项目，另一个在后面添加一个项目，以及从前到后和从后到前输出链表的正向和反向显示方法，分别。
我在试图理解的输出中遇到了一个错误。看来我的 addFront 和显示功能正在运行，但我的 addBack 可能是我的错误所在。我在这篇文章的底部发布了我的输出以及它显示的内容。 到目前为止，这是我的代码。

#include<iostream>
using namespace std;

class doubleLinkedList
{
private:
    class node
    {
    public:
        int data;
        node* next;
        node* prev;
        node(int x)
        {
            data = x;
            next = NULL;
            prev = NULL;
        }
    };
public:
    node* head;
    node* tail;
    int count;



    doubleLinkedList();        //default constructor
    ~doubleLinkedList();      //destructor

    void displayForward();    //display items from front to back
    void displayBackward();   //display items from back to front

    void addFront(int);      //add item to front of linked list
    void addBack(int);       //add item to back of linked list

    int removeFront();       //remove item from front of linked list
    int removeBack();        //remove item from back of linked list
};

//constructor
doubleLinkedList::doubleLinkedList(){
    head = tail = NULL;
    count = 0;
}


//destructor
doubleLinkedList::~doubleLinkedList(){
    node* current = head;

    while(current != NULL)
    {
        node* previous = current;
        current = current->next;
        delete previous;
    }

    head = tail = NULL;
    count = 0;
}


//display items in linked list from front to back
void doubleLinkedList::displayForward(){
    node* pCurrent = head;
    while (pCurrent != NULL)
    {
        cout << pCurrent->data << " ";
        pCurrent = pCurrent->next;
    }
    cout << count;
}


//display items in linked list from back to front
void doubleLinkedList::displayBackward(){
    node* pCurrent = tail;
    while (pCurrent != NULL)
    {
        cout <<pCurrent->data << " ";
        pCurrent = pCurrent->prev;
    }
    cout << count;
}


//add item to front of linked list
void doubleLinkedList::addFront(int x){

    node* n = new node(x);
    n->next = head;
    n->prev = NULL;

    if (head != NULL)
        head->prev = n;
        head = n;
        count++;

    if (tail == NULL)
        tail = n;
}

void doubleLinkedList::addBack(int x){
    node* n = new node(x);

    n->next = NULL;
    n->prev = tail;
    tail = n;

    count++;
}

///////////////////我的测试代码:///////////////////

int main()
{
    doubleLinkedList list;

    list.addBack(40);
    list.addBack(50);
    list.addBack(60);
    list.addFront(30);
    list.addFront(20);
    list.addBack(70);
    list.addBack(80);
    list.addFront(10);

    list.displayForward();  //10 20 30 8   (the 8 value is the count/size i'm keeping track of)
        cout << endl;
    list.displayBackward(); //80 70 60 50 40 8
        cout << endl;

        system("pause");
        return 0;
        }

我的输出应该显示 10 20 30 40 50 60 70 80 和 80 70 60 50 40 30 20 10
但是我的 displayForward 显示我添加到前面的项目，我的 displayBackward 显示我添加到后面的项目。

Answer 1

您忘记将旧尾部下一个指针设置为新尾部。因此，当遍历列表时，倒数第二个节点仍将指向 NULL。

此外，添加到后面时你没有检查 head 是否为 null，所以添加到后面时，你只更新了尾端，结果得到了两个单独的列表。

因此您将 40、50、60 添加到“末尾”，因此相应地设置并更新了尾部指针，但是直到您将 30 添加到列表中才创建头部，继续往前面添加元素，指针也随之更新，结果头尾实际上并没有连起来。

void doubleLinkedList::addBack(int x){       
    node* n = new node(x);

    if (head == nullptr)
        head = n; //this was your main problem!

    if (tail != nullptr)
        tail->next = n;

    n->next = nullptr;
    n->prev = tail;
    tail = n;

    count++;
}

由于您似乎在编写 C++ 代码，我建议您也习惯使用 nullptr 而不是 NULL。

http://www.codeproject.com/Articles/570638/Ten-Cplusplus11-Features-Every-Cplusplus-Developer