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

banderson

I wrote this code using singly linked list. Now I want to change it to doubly linked list. I have tried few different things but everything messed up. There are few useless lines in my code, but it is basically a singly linked list. What is the proper way to change it to a doubly linked list?

#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;

    }
}

Edit: My new AddExhibit() method:

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;
}
banderson

I solved my problem with this AddExhibit() method:

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;
}

I don't know if it is totally correct or not but it works fine for my case.

Collected from the Internet

Please contact [email protected] to delete if infringement.

edited at
0

Comments

0 comments
Login to comment

Related