リンクリストの最後から削除

Question

6つの乱数を生成し、それらをリンクリストに入れて出力するプログラムを作成しています。次に、6つの数字をすべて取得した後、最初のノードを削除して残りの5を出力し、最後のノードを削除し、残っている4を出力します。とにかくリンクリストとストアノードを作成して出力することができ、毎回最初のノードを削除することができますが、最後のノードを削除する方法を見つけることはできません。最後のノードを削除する方法についての助けがあれば幸いです。私はあなたがよくあなたのMCVE（入力、出力、挿入など）の残りの部分を完了した

#include <iostream> 
#include <ctime> 
#include <cstdlib> 
#include "SortedLinkedList.h" 

using namespace std; 

struct node 
{ 
    int data; 
    node *next; 
}; 

node *head = NULL; 

void push_sorted(int value) 
{ 
    node *newNode = new node; 
    newNode->data = value; 
    newNode->next = NULL; 
    if(head == NULL) 
    { 
     head = newNode; 
    } 
    else 
    { 
     node *newNode_2 = head; 
     while(newNode_2->next != NULL) 
     { 
      newNode_2 = newNode_2-> next; 
     } 
     newNode_2->next = newNode; 
    } 
} 

void pop_front() 
{ 
    node *temp; 
    temp = head; 
    head = head->next; 
    free(temp); 
} 

void pop_back() 
{ 
} 

bool isEmpty(int count) 
{ 
    if(count == 0) 
    { 
     return false; 
    } 

    else 
    { 
     return true; 
    } 

} 

void print() 
{ 
    node* current = head; 
    while(current != NULL) 
    { 
     cout << current-> data << " "; 
     current = current->next; 
    } 
    cout << endl; 
} 
int main() 
{ 
    int count = 6; 
    const int NUMS = 6;  //insert elements into the sorted linked list in an ascending order 
    const int RANGE = 21; //each element is in the range [-10, 10] 
    /*SortedLinkedList mylist;*/ 
    srand(time(0)); 
    for (int i = 0; i < NUMS; i++) 
    { 
     int data = (rand() % RANGE) - 10; 
     cout << "Adding " << data << " to the sorted linked list: " << endl; 
     push_sorted(data); 
     print(); 
    } 

    while ((isEmpty(count) == true)) 
    { 
     cout << "Removing from front..." << endl; 
     pop_front(); 
     print(); 
     count --; 
     cout << "Removing from back..." << endl; 
     pop_back(); 
     print(); 
     count --; 
    } 
    system("pause"); 
    return 0; 
} 

Answer 1

...最後のノードを削除するには、関数pop_backを使用しています。 （ただし、構造体内のメソッドを移動することをお勧めします）

私は以下の再帰的なソリューションを提供することに決めました。たった1回のテストで、動作するようです。

再帰を理解できない場合は、ループ反復のアプローチに取り組むことをお勧めします。あなたが再発見を理解しているならば、ループ反復アプローチに取り組まなければなりません。

void pop_back() 
{ 
    bool isLast = false; 
    if(nullptr != head) // does list have any elements? 
    { 
     // use the recursive form to find last, and 
     // return a bool to find the next to last 
     isLast = head->pop_backR(); // recurse to last element 

     if (isLast) // i.e. only 1 element in list, the head 
     { 
     delete (head); // remove it 
     head = nullptr; 
     } 
    } 

    // note: on std::list, calling pop_back when container empty is undefined. 
    // tbd - throw underflow? your choice here 
} 


bool pop_backR() 
{ 
    if(nullptr == next) 
     return true; // last node found, return feedback to previous node 

    // last node not found, continue search 
    bool nxtIsLast = next->pop_backR(); 

    // check - did we find the last element yet? 
    if (nxtIsLast) 
    { 
     // at this point we know next is last 
     delete (next); // so delete last 
     next = nullptr; // remove it from list 
     return false; // we are done, now decurse with no more deletes 
    } 
    else // previous recursion did not find it 
     return false; 
} 

これはうまくいくようですが、十分にテストされていません。私のシステムで

出力 -

Adding -9 to the sorted linked list: 
-9 
Adding 0 to the sorted linked list: 
-9 0 
Adding -6 to the sorted linked list: 
-9 0 -6 
Adding 10 to the sorted linked list: 
-9 0 -6 10 
Adding -8 to the sorted linked list: 
-9 0 -6 10 -8 
Adding -3 to the sorted linked list: 
-9 0 -6 10 -8 -3 
Removing from front... 
0 -6 10 -8 -3 
Removing from back... 
0 -6 10 -8 
Removing from front... 
-6 10 -8 
Removing from back... 
-6 10 
Removing from front... 
10 
Removing from back...