如何在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;