C++のリンクリストに前のポインタを作成する方法は？

Question

私は、リストの最初の要素を削除する関数と、リストの最後の要素を削除する関数を持つLinkedListクラスを作成しました。最初のものは簡単です、要素を削除した後、次の要素を指すように設定します。よく働く。しかし、最後の要素を削除すると、リストの前の要素を指し示す必要があります。この要素は、その時点で最後の要素になります。私はこれを行う方法を理解することはできません。お知らせ下さい。

void LinkedList::pop_front() 
{ 
    mFront->data = NULL; 
    mFront = mFront->next; 
} 

最後の要素を削除して新しいテールを指すようにリセットするにはどうすればよいですか？

void LinkedList::pop_back() 
{ 
mBack->data = NULL; 
... 
} 

class LinkedList 
{ 
    public: 

     // Default Constructor 
     // Purpose: Initializes an empty list 
     // Parameters: none 
     // Returns: none 
     LinkedList(); 

     // The push_front function 
     // Purpose: add an item to the front of the list 
     // Parameters: a int item for the front 
     // Returns: none   
     void push_front(int data); 

     // The push_back function 
     // Purpose: insert an item into the back of the list 
     // Parameters: int item to add the the back 
     // Returns: none     
     void push_back(int data); 

     // The pop_front function 
     // Purpose: delete the item in the front of the list 
     // Parameters: none 
     // Returns: none 
     void pop_front(); 

     // the pop_back function 
     // Purpose: remove the item at the end of the list 
     // Parameters: none 
     // Returns: none   
     void pop_back(); 

     // The getFirst function 
     // Purpose: print the first item in the list 
     // Parameters: none 
     // Returns: none 
     void getFirst(); 

     // the GetLast function 
     // Purpose: return the last item in the list 
     // Parameters: none 
     // Returns: none 
     void getLast(); 

     void printList(); 

     // the clear function 
     // Purpose: clear the list, free memory 
     // Parameters: none 
     // Returns: none 
     void clear(); 

     // Destructor 
     // Purpose: clear up memory 
     // Parameters: none 
     // Returns: none 
     ~LinkedList(); 

    private: 

      LinkedList *mFront; // point to the front of our list 
      LinkedList *mBack; // point to the back of our list 
      LinkedList *next; // the next node 
      LinkedList *previous; // the previous node 
      int data; // our list data manipulator 

Answer 1

単一リンクリストでは、最後の要素のO（1）削除は提供されません。最後から2番目の要素を見つけるには、最初からリスト全体を実行する必要があります。

Node* i = mFront; 
while (i->next != mBack) i = i->next; 
mBack = i; 

Answer 2

リストがリンクされ二重にされていない場合、あなたは最後のものを見つけるために、最初の要素で開始する必要があります：

void LinkedList::pop_back() 
{ 
    mBack->data = NULL; 
    current = mFront; 
    do{ 
     current = current->next 
    } while (current->next); 
    mBack = current; 
} 

非常に重要 - dataがあるように思われるので、ポインタを使用すると、メモリリークが発生する可能性があります。ただ、メモリを解放しませんdata = NULLを設定するには、明示的にそれを削除する必要があります：あなたは要素のO（1）削除したい場合は

delete mFront->data;