Правильная реализация методов двусвязного списка

Question

Во-первых, извините за мой плохой английский.

Я пытаюсь реализовать Двусвязный список, но я не уверен, что некоторые его методы работают правильно. На самом деле, clear(), remove(const short DATA) - который удаляет все элементы, которые сравниваются равными DATA, unique() а также reverse() не работает правильно. Я не нашел ни одной книги, видео или статьи, которая была бы хороша. Я мог бы реализовать их по-своему, но я придерживаюсь формального пути (если есть), и решение для более опытного человека будет более эффективным, чем мое

void DLList::clear()
{
    Node *pCurr = mHead;
    while (pCurr != nullptr)
    {
        mHead = pCurr->mNext;
        delete pCurr;
        pCurr = mHead;
    }
}

void DLList::remove(const short DATA)
{
    Node *pCurr = mHead;
    while (pCurr != nullptr)
    {
        if (pCurr->mData == DATA)
        {
            if (pCurr == mHead)
            {
                mHead = pCurr->mNext;
                delete pCurr;
                pCurr = mHead;
            }
            else
            {
                Node *pPrev = pCurr->mPrev;
                pPrev->mNext = pCurr->mNext;
                delete pCurr;
                pCurr = pPrev->mNext;
            }
        }
        else
            pCurr = pCurr->mNext;
    }
}

void DLList::unique()
{
    Node *pCurr = mHead;
    while (pCurr != nullptr)
    {
        Node *pNextDistinct = pCurr->mNext;
        while (pNextDistinct != nullptr && pNextDistinct->mData == pCurr->mData)
        {
            pNextDistinct = pNextDistinct->mNext;
            delete pCurr->mNext;
            pCurr->mNext = pNextDistinct;
            pNextDistinct->mPrev = pCurr;
        }
        pCurr = pNextDistinct;
    }
}

void DLList::reverse()
{
    Node *pPrev = nullptr;
    Node *pCurr = mHead;
    while (pCurr != nullptr)
    {
        pCurr->mPrev = pCurr->mNext;
        pCurr->mNext = pPrev;
        pPrev = pCurr;
        pCurr = pCurr->mPrev;
    }
    mHead = pPrev;
}

Answer 1

Я исправил ваши методы, чтобы они хорошо работали. Пожалуйста, сравните ваши ошибки, а также прочитайте мой комментарий в коде. При кодировании структуры данных всегда используйте бумагу и ручку и сначала запишите структуру дерева или списка, которая поможет вам сначала спроектировать алгоритм, а затем код. Пожалуйста, дайте мне знать, если вам нужна дополнительная помощь.

//In the below method you are deleting unique nodes
void DLList::unique()
{
    Node *pCurr = mHead;
    Node *temp = NULL;
    int data = 0;
    while (pCurr != NULL)
    {
       data = pCurr->mData;
       temp = pCurr;
       while(temp != NULL)
       {
           temp = temp->mNext;
           if(temp->mData == data)
           {
              //delete the duplicate node
              temp->mPrev->mNext = temp->mNext;
              if(temp->mNext != NULL)
                  temp->mNext->mPrev = temp->mPrev;
              delete(temp);
           }
       }
      pCurr = pCurr->mNext; 
    }
}


void DLList::reverse()
{
    Node *temp = NULL, *q = NULL;
    while (temp->mNext != NULL)
      temp = temp->mNext;
    //now temp is pointing to the last node of the list
    //Assume that mHead->mPrev == null, because I dont know whether it is null or address of Head itself
    //if Head node mPrev is holding the address of head then you must store the address of head in a pointer
    //to check whether you reach head node or not
    //as I assume it is null so I don't need a temporary pointer here
    mHead = temp; //now head is pointing to the last node
    q = temp->mPrev;//pointer q is pointing to the previous node of the last node
    temp->mPrev = NULL;//as last node is now first node make it's previous pointer as NULL
    while(q!=NULL)// now traverse toward the old head node who's prev pointer is set as NULL
    {
       temp->mNext = q;
       q->mPrev = temp;
       temp = q; //move temp to the old previous node
       q = q->mPrev;// Move q to the previous node
    }
    //Now temp is pointing to the old head node
    temp->mNext = NULL;//Your list is reversed finally
}

Реверс может быть выполнен и от головы до последнего узла. Теперь вы просто записываете список на бумаге и думаете, как вы можете это сделать и сколько указателей вам нужно для этого. Удачи:-)