如何在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）刪除最後一個元素。您必須從頭開始查看整個列表以查找倒數第二個元素。

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不釋放內存，你必須明確地將其刪除：

delete mFront->data;