Doubly Linked List 방법의 올바른 구현

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 
} 

머리말에서 마지막 노드까지 반전시킬 수 있습니다. 이제는 목록을 종이에 적어보고 어떻게 할 수 있는지 그리고 얼마나 많은 포인터가 필요한지 생각하십시오. 행운을 빌어 요 :-)