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