0

リストの最初の要素を削除する関数と、リストの最後の要素を削除する関数を持つ 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
4

2 に答える 2

4

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

Node* i = mFront;
while ( i->next != mBack ) i = i->next;
mBack = i;
于 2012-04-18T21:01:12.533 に答える
1

リストが二重にリンクされていない場合、最初の要素から始めて最後の要素を見つける必要があります。

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

非常に重要-dataポインタのように見えるため、メモリ リークが発生している可能性があります。設定するだけでdata = NULLはメモリが解放されないため、明示的に削除する必要があります。

delete mFront->data;
于 2012-04-18T21:03:04.683 に答える