C++从单向链表变为双向链表

Question

我使用单链表编写了这段代码。现在我想把它改成双向链表。我尝试了一些不同的东西，但一切都搞砸了。我的代码中几乎没有无用的行，但它基本上是一个单链表。将其更改为双向链表的正确方法是什么？

#pragma once

#include "Exhibit.h"

struct Node
{
    Exhibit exhibit;
    Node *next;
};

class Museum
{
private:
    Node *p;
    Node *d;
    Exhibit *Ex;
    int n;
    int nmax;
public:
    Museum();
    ~Museum();

    void Start() { d = p; }
    bool HasNext() { if (d == NULL) return false;  return true; }
    void Next() { d = d->next; }
    Exhibit GetExhibit() const { return d->exhibit; }
    int GetN() { return n; }

    void Sort();
    void AddExhibit(Exhibit e);
    void RemoveExpensive(int p); //Removes elements more expensive than int p
};

Museum::Museum()
{
    p = NULL;
    d = NULL;

}

Museum::~Museum()
{
    Node * element;
    while (p)
    {
        element = p;
        p = p->next;
        delete element;
    }
    p = NULL;
    d = NULL;

}

void Museum::AddExhibit(Exhibit e)
{
    Node *element = new Node;

    element->exhibit = e;
    element->next = p;
    p = element;
}

int CountExhibits(string CDfv)
{
    string line;
    int count = 0;
    ifstream fd(CDfv.c_str());
    while (!fd.eof())
    {
        getline(fd, line);
        count++;
    }
    fd.close();
    return count;
}

void Museum::Sort()
{
    // traverse the entire list
    for (Node *list = p; list->next != NULL; list = list->next)
    {
        // compare to the list ahead
        for (Node *pass = list->next; pass != NULL; pass = pass->next)
        {
            // compare and swap
            if (list->exhibit.Date() > pass->exhibit.Date())
            {
                // swap
                Exhibit temp = list->exhibit;
                list->exhibit = pass->exhibit;
                pass->exhibit = temp;
            }
        }
    }
}

void Museum::RemoveExpensive(int pr)
{
    Node *pPre = NULL, *pDel = NULL;


    pPre = p;
    pDel = p->next;

    /* traverse the list and check the value of each node */
    while (pDel != NULL) {
        if (pDel->exhibit.Price() > pr) {
            /* Update the list */
            pPre->next = pDel->next;
            /* If it is the last node, update the tail */
            if (pDel == d) {
                d = pPre;
            }
            delete pDel; /* Here only remove the first node with the given value */
            pDel = pPre;
             /* break and return */
        }
        pPre = pDel;
        pDel = pDel->next;
    }


    /* Check whether it is the head node?
    if it is, delete and update the head node */
    if (p->exhibit.Price() > pr) {
        /* point to the node to be deleted */
        pDel = p;
        /* update */
        p = pDel->next;
        delete pDel;

    }
}

编辑：我的新 AddExhibit() 方法：

void Museum::AddExhibit(Exhibit e)
{
    Node *element = new Node;

    element->exhibit = e;

    if (p == NULL)
        p = d = element;
    else
    {
        p->prev = element;
        element->next = p;
        p = element;

    }
    //element->next = p;
    //p = element;
}

Answer 1

我用这个 AddExhibit() 方法解决了我的问题：

void Museum::AddExhibit(Exhibit e)
{
    Node *element = new Node;

    element->exhibit = e;

    element->next = p; 
    element->prev = NULL;
    if (p == NULL)
        d = element;
    else
        p->prev = element;
    p = element;
}

我不知道它是否完全正确，但它适合我的情况。

C++从单向链表变为双向链表

C++ Changing from singly linked list to doubly linked list

c++

linked-list

singly-linked-list

doubly-linked-list