LinkedListクラスのポインタを削除する

Question

C++で最初のLinkedListクラスを実装しようとしていますが、ポインタの削除に問題があります。

LinkedList.h：LinkedList.cppの

#pragma once 

#ifndef LINKEDLIST_H 
#define LINKEDLIST_H 

#include <iostream> 
#include "ListNode.h" 


class LinkedList 
{ 
private: 
    int theSize; 
    ListNode* head; 
    ListNode* tail; 

public: 
    LinkedList(); 
    ~LinkedList(); 
    LinkedList(const LinkedList&); 
    const LinkedList& operator=(const LinkedList&); 
    void push_front(const Line&); 
    void push_back(const Line&); 
    void pop_front(); 
    void pop_back(); 
    int const size(); 
    bool const empty(); 
    void insert(const Line&, int); 
    void remove(int); 
    void print(); 
    void print(int); 
}; 

#endif //!LINKEDLIST_H 

部：

LinkedList::LinkedList() : theSize{ 0 }, head{ nullptr }, tail{ nullptr } { 
} 


//Destructor: Need to go through entire list and delete one by one 
LinkedList::~LinkedList() { 
    if (!empty()) { 
     cout << "Destroying List" << endl; 

     ListNode* currPtr{ head }; 
     ListNode* tempPtr{ nullptr }; 

     while (currPtr != nullptr) { 
      tempPtr = currPtr; 
      currPtr = currPtr->next; 
      delete tempPtr; 
     } 
    } 
} 


//LinkedList::LinkedList(const LinkedList& ll) { 
// 
//} 

//const LinkedList& LinkedList:: operator=(const LinkedList& ll) { 
// 
//} 

void LinkedList::push_front(const Line& l) { 
    ListNode* ln = new ListNode(l); 

    if (empty()) 
     head = tail = ln; 
    else { 
     ln->setNext(*head); 
     (*head).setPrev(*ln); 
     head = ln; 
    } 
    theSize++; 
} 

void LinkedList::push_back(const Line& l) { 
    ListNode* ln = new ListNode(l); 

    //If List is empty, head and tail will point to one node 
    if (empty()) 
     head = tail = ln; 

    else { 
     (*tail).setNext(*ln); 
     (*ln).setPrev(*tail); 
     tail = ln; 
    } 
    theSize++; 
} 

void LinkedList::pop_front() { 
    if (empty()) 
     return; 
    else { 
     ListNode* tempPtr = head; 

     if (head == tail) //If there is only one Node in the List 
      head = tail = nullptr; 

     else    
      head = head->next; 

     delete tempPtr; 
    } 
    //theSize--; 
} 

ListNode.h：

#pragma once 

#ifndef LISTNODE_H 
#define LISTNODE_H 

#include<iostream> 
#include"Line.h" 
//using namespace::std; 

class ListNode 
{ 

    friend class LinkedList; 
private: 
    Line data; 
    ListNode* next; 
    ListNode* prev; 

public: 
    ListNode(); 
    ~ListNode(); 
    ListNode(const Line&); 
    ListNode(const Line&, ListNode*, ListNode*); 

    Line& getData(); 
    ListNode& getNext(); 
    ListNode& getPrev(); 

    void setData(const Line&); 
    void setNext(ListNode&); 
    void setPrev(ListNode&); 

    friend ostream& operator<<(ostream&, const ListNode&); 
    friend istream& operator>>(istream& input, ListNode&); 

}; 

pop_front（）メソッドは、単純に最初のノードを削除リンクされたリスト：

void LinkedList::pop_front() { 
    if (empty()) 
     return; 
    else { 
     ListNode* tempPtr = head; 

     if (head == tail) //If there is only one Node in the List 
      head = tail = nullptr; 

     else    
      head = &((*tempPtr).getNext()); //getNext() returns a Node& 

     //delete tempPtr; 
    } 
} 

私のメインでは、LinkedListを作成し、いくつかのノードを追加しています。これはうまくいきます。 pop_front（）メソッドは、最後にdeleteステートメントを含めるまで正常に動作します。このとき、実行時エラーが発生します。なぜそれが動作していないのか分かりません。これは二重にリンクされたリストです。

Answer 1

あなたのコードは混乱しますが、これは最初にリンクされたリストなので、実装にお役立てください。将来の投稿では、メソッドが返すものを見ることができないので、すべてのコードを投稿してください。それは推測の余地があります。誰もあなたを助けることはできません。

# include <stdio.h> 
# include <iostream> 


using namespace std; 


struct LinkedListItem 
{ 
    LinkedListItem(int c) : content(c), next(nullptr) 
    { 
    } 

    int content; 
    LinkedListItem * next; 
}; 

struct LinkedList 
{ 

    LinkedList() : Start(nullptr), End(nullptr) //initialize it to null, tgis is faster than in body 
    {} 

    ~LinkedList() 
    { 
     //to delete 

     LinkedListItem * ptrtodelete; 

     while(Start) 
     {//while there is something 

      //archive the current first element 
      ptrtodelete = Start; 


      //we move to next item 
      Start = Start -> next; 


      delete ptrtodelete; 

      //i can afford destroying Start (by moving it) because this is destructor 
     } 
     //be paranoid 
     Start = End = nullptr; 
    } 
    void AddItem(int i) 
    { 
     if(!Start) //or if Start == nullptr 
     { 
      Start = new LinkedListItem(i); 
      End = Start; //both point to the one element 
      return; 
     } 

     LinkedListItem * newelement = new LinkedListItem(i); 
     End -> next = newelement; //let last item point to this one 

     End = newelement; //let end point to the last item 
    } 
    LinkedListItem * Start; /**< Pointer to first element */ 
    LinkedListItem * End; /**< Pointer to last element */ 
}; 


int main() 
{ 
    LinkedList l; 
    l.AddItem(5); 
    l.AddItem(980); 

    return 0; 
} 

これが機能しています。参考になります。 あなたがテンプレートにそれを回すには、後に検討するかもしれない：私はそれをコンパイルし、valgrindのに置くとき]

、これは出力

user@Horse:~/Desktop/tmp/AAA$valgrind ./a.out 
==11699== Memcheck, a memory error detector 
==11699== Copyright (C) 2002-2013, and GNU GPL'd, by Julian Seward et al. 
==11699== Using Valgrind-3.10.1 and LibVEX; rerun with -h for copyright info 
==11699== Command: ./a.out 
==11699== 
==11699== 
==11699== HEAP SUMMARY: 
==11699==  in use at exit: 0 bytes in 0 blocks 
==11699== total heap usage: 2 allocs, 2 frees, 16 bytes allocated 
==11699== 
==11699== All heap blocks were freed -- no leaks are possible 
==11699== 
==11699== For counts of detected and suppressed errors, rerun with: -v 
==11699== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0) 
user@Horse:~/Desktop/tmp/AAA$ 

は今、なぜ見ることができますが...？そしてこれはどういう仕組みですか？

私のリストの各項目には、別の要素へのポインタがあります。最後のノードのポインタはnullに設定され、リストが空の場合は

Start 

変数はnullです。

今

void AddItem(int i) 

に私は1つの特殊なケースをチェックしなければなりません。リストに項目がない場合。 次に、新しいアイテムを作成して、追加が完了するとリターンします。ノードが存在する場合、理論的には、すでに、

を（私は

End 

後でexplaingます）、私がリンクすることができるという、最後のノードに到達するために、最後までのすべてのノードを通過しなければなりません新しい要素があります。 N個の項目がリストにあると仮定すると、N個のステップが必要になります。それは最悪の場合複雑さと呼ばれ、Omikronの数学関数を表すO（n）と呼ばれます。

これは単純に言います：起こり得るすべての状況から、私が最悪のものを選択すると、metdosはNステップを取るが、それは最大である。かなり悪いですよね？ そこにミリオンアイテムがあると想像してください... f。ゲームの例...

だから私は何をしたか、それ私がリンクリストの最後の項目を指し、

End 

変数を作成したこと。そのような 、私は、この最後のノードに

End -> next = newelement; //let last item point to this one 

を新しいアイテムをリンクし、新しく追加された項目に終了変数を設定し、ウィッヒは今

End = newelement; //let end point to the last item 

最後で、複雑さは今、Oであります（1）。理論的には、これはO（4）のようにメソッド内の任意の操作に対して+1になりますが、O（1）と呼ばれます。

リンクされたリストも削除する必要があります。それはもっと多くの方法で行うことができますが、エレガントなもう一つの方法がありますが、私はこのサイクルで大丈夫です。

~LinkedList() 

最初の要素にポンターが必要なくなったので、私はそれを増やすことができます。開始要素がヌルではない間に、

私たちはポインタを保存します。

ptrtodelete = Start; 

次の項目にポイントを起動し、我々は理論的には

をアーカイブした項目を削除させ、エンドではなく、一つの変数（ポインタのための4または8バイト）を保存するためにptrtodelete使用することができます

今私はあなたに質問します...これの複雑さは何ですか？あなたはO（n）を答えた場合、nはアイテムの数である、あなたは

最後正しかった、あなたはコンストラクタ

LinkedList() : Start(nullptr), End(nullptr) 

でそれを見ることができ、私は二重ドットの後に変数を初期化します。なぜこれが好きではない...？

LinkedList() 
{ 
Start = nullptr; 
End = nullptr; 
} 

理由は、上のコードを見てください。新しいListitemが作成され、コードがコンストラクタに移動します。

開始変数と終了変数はランダムな値に設定されています。それはまさに何が起こるかです。 次に、それらをヌルに変更します（4つの操作）。

上記の例を考慮すると、 ListItemが作成され、開始値と終了値にnullptrが割り当てられます。 これは2つの操作です。

それはあなたをあまり保存しませんが、巨大なプロジェクト、ゲーム、多分、milion割り当てで、それは何かを保存することができます。

これは私が私の学部で学んだ信じられないことであり、私はそれを気に入っています。今すぐあなたと共有しています：]