删除LinkedList类中的指针 [英] Deleting a pointer in a LinkedList class

问题描述

我试图在C ++中实现我的第一个LinkedList类，我有删除指针的麻烦。

LinkedList.h：

  #pragma once 
 
 #ifndef LINKEDLIST_H 
 #define LINKEDLIST_H 
 
 #include< iostream> 
 #includeListNode.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.cpp：

  LinkedList :: LinkedList（）：size {0}，head {nullptr}，tail {nullptr} {
} 
 
 
 //析构函数：需要遍历整个列表并逐个删除
 LinkedList ::〜LinkedList（）{
 if（！empty（）） {
 cout<< 毁坏列表< 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）; 
 
 //如果List为空，头和尾将指向一个节点
 if（empty（））
 head = tail = ln; 
 
 else {
（* tail）.setNext（* ln）; 
（* ln）.setPrev（* tail）; 
 tail = ln; 
} 
 aSize ++; 
} 
 
 void LinkedList :: pop_front（）{
 if（empty（））
 return; 
 else {
 ListNode * tempPtr = head; 
 
 if（head == tail）//如果列表中只有一个节点
 head = tail = nullptr; 
 
 else 
 head = head-> next; 
 
 delete tempPtr; 
} 
 // theSize--; 
} 
  

ListNode.h：

  #pragma once 
 
 #ifndef LISTNODE_H 
 #define LISTNODE_H 
 
＃include< iostream> 
 #includeLine.h
 // using namespace :: std; 
 
 class ListNode 
 {
 
 friend class LinkedList; 
 private：
行数据; 
 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（）方法只是删除了LinkedList中的第一个节点：

  void LinkedList :: pop_front（）{
 if（empty（））
 return; 
 else {
 ListNode * tempPtr = head; 
 
 if（head == tail）//如果列表中只有一个节点
 head = tail = nullptr; 
 
 else 
 head =&（（* tempPtr）.getNext（））; // getNext（）返回一个Node& 
 
 // delete tempPtr; 
} 
} 
  

在我的主要我创建一个LinkedList并添加几个节点，这很好。 pop_front（）方法工作正常，直到我在结尾包括delete语句，在这个时候我得到一个运行时错误。我似乎不明白为什么它不工作。这是一个双向链表。

解决方案

你的代码很混乱，但由于这是你的第一个链表，帮助您实施。在以后的帖子中，发布所有的代码，因为我看不到一个方法返回，它是更多的猜测，没有人可以帮助你。

 ＃include< stdio.h> 
＃include< iostream> 
 
 
使用namespace std; 
 
 
 struct LinkedListItem 
 {
 LinkedListItem（int c）：content（c），next（nullptr）
 {
} 
 
 int content; 
 LinkedListItem * next; 
}; 
 
 struct LinkedList 
 {
 
 LinkedList（）：Start（nullptr），End（nullptr）//将其初始化为null，tgis比body b $ b {} 
 
〜LinkedList（）
 {
 //删除
 
 LinkedListItem * ptrtodelete; 
 
 while（开始）
 {//有一些东西
 
 //存档当前第一个元素
 ptrtodelete = Start; 
 
 
 //我们移动到下一个项目
 Start = Start  - >下一个; 
 
 
 delete ptrtodelete; 
 
 //我可以销毁Start（通过移动它），因为这是析构函数
} 
 //是paranoid 
 Start = End = nullptr; 
} 
 void AddItem（int i）
 {
 if（！Start）//或如果Start == nullptr 
 {
 Start = new LinkedListItem （一世）; 
 End =开始; //都指向一个元素
 return; 
} 
 
 LinkedListItem * newelement = new LinkedListItem（i）; 
 End  - > next = newelement; //让最后一个项指向这个
 
 End = newelement; //让结束点指向最后一个项目
} 
 LinkedListItem * Start; / **<指向第一个元素的指针* / 
 LinkedListItem * End; / **<指向最后一个元素的指针* / 
}; 
 
 
 int main（）
 {
 LinkedList l; 
 l.AddItem（5）; 
 l.AddItem（980）; 
 
 return 0; 
} 
  

现在这个工作很有用。
你可以考虑稍后将它转换为模板：]

当我编译它并把它放到valgrind，输出

  user @ Horse：〜/ Desktop / tmp / AAA $ valgrind ./a.out 
 == 11699 == Memcheck，内存错误检测器
 == 11699 ==版权所有（C）2002-2013，以及GNU GPL'd，由Julian Seward等人
 == 11699 ==使用Valgrind-3.10.1和LibVEX;重新运行-h版权信息
 == 11699 ==命令：./a.out 
 == 11699 == 
 == 11699 == 
 == 11699 == HEAP摘要：
 == 11699 ==在退出时使用：0字节在0块
 == 11699 ==总堆使用：2分配，2释放，16字节分配
 == 11699 == 
 == 11699 ==所有堆块被释放 - 没有泄漏
 == 11699 == 
 == 11699 ==对于检测到的和抑制的错误计数，重新运行与：-v 
 == 11699 == ERROR摘要：0个上下文中的0个错误（抑制：0从0）
 user @ Horse：〜/ Desktop / tmp / AAA $ 
  

现在看看为什么...？

我的列表中的每个项目都有一个指向另一个元素的指针。最后一个节点的指针设置为null，如果list为空，

 开始
  
 $ b 
现在
  void AddItem（int i）
  
 
 
必须检查一个特殊情况。如果列表中没有项目。 
然后，我创建新项目，并返回，因为添加完成。 （我将解释
 结束
  
稍后）
 
 
 
如果一个节点存在，已经在理论上，我必须遍历所有的节点，到最后一个节点，能够链接到新的元素。 
这将需要我N个步骤，假设我们在列表中有N项。在最坏的情况下，这被称为复杂性，被称为O（n），它代表Omikron数学函数。
 
 
 
它只是告诉你：如果我选择最差的一个，那么metdos会带我N步，但这是最大。很糟糕，对吧？ 
想象一下，在里面有milion项目... f。 
 
 
 
所以我做了，这是我创建了一个
 结束
  
变量，指向链接列表中的最后一个项目。 
像这样，我只是将新项目链接到最后一个节点，
  End  - > next = newelement; //让最后一个项指向这个
  
将End变量设置为新添加的项，wich是最后
  End = newelement; //让结束点指向最后一个项目
  
 
 
现在，复杂性现在是O（1）。理论上，对于方法中的任何操作，它都是+1，所以O（4），但是被称为O（1）。
 
 
 
删除链表。 
 〜
 LinkedList（）
  
因为我们不再需要一个ponter到第一个元素，我可以开始增加它。因此，虽然开始元素不为null，
  while（开始）
  pre> 
 
 
我们保存指针 - 开始。
  ptrtodelete = ; 
  
让我们开始指向下一个项目，然后删除我们存档的项目
 
 
 
理论上，End可以改为ptrtodelete保存一个变量（指针为4或8个字节）
 
 
 
现在我会问你...这是什么复杂性...？如果你回答了O（n），其中n是项数，你是正确的
 
 
 
最后，你可以看到在构造函数
  LinkedList（）：开始（nullptr），结束（nullptr）
  
我初始化双点后的变量。为什么不喜欢这个...？
  LinkedList（）
 {
 Start = nullptr; 
 End = nullptr; 
} 
  
原因是，看看上面的代码：创建一个新的Listitem，转到构造函数。
 
 
 
开始和结束变量设置为随机值。这只是会发生什么。 
然后，我们在body中将它们改为null（4个操作）。
 
 
 
但是考虑上面的例子，
创建ListItem，并且为开始和结束的值分配为nullptr。 
这两个操作。
 
 
 
它不会节省你太多，但有巨大的项目，游戏也许，在里程碑分配，它可以节省一些东西。 p> 
 
 
这是我们在我的教师学到的令人难以置信的事情，我喜欢它，因为当我环顾四周，我没有在互联网上找到这个。现在我和你们分享：] 
 
I am trying to implement my first LinkedList class in C++ and I'm having trouble with deleting a pointer. 

LinkedList.h:
#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
part of LinkedList.cpp:
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&);

};
The pop_front() method simply removes the first Node in the LinkedList:
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;
    }
}
In my main I create a LinkedList and add a few nodes, which works well. The pop_front() method works fine until I include the delete statement at the end, in which time I get a run time error. I can't seem to understand why it is not working. This is for a doubly linked list.
解决方案
Well your code is confusing, but since this is your first linked list, let me help you in implementation. In future posts, post all your code, since I can not see what a method returns, and it is more guessing, no one can help you then.
# 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;
}
Now this is working, can be helpful.
You might consider later on turning it to a template :]

When I compiled it and put to valgrind, this is output
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$
Now lets see why...? And how this works...?

Each item in my list has a pointer to another element. Last node has pointer set to null, and, if list is empty, 
Start
variable is null.

Now in 
void AddItem(int i)
I have to check for one special case. If there are no items in list.
Then, I create new item, and return, as adding is done. (I will explaing 
End
later)

If a node is there, already, in theory, I would have to traverse all the nodes up to end, to get to last node, being able to link there new element.
That would take me N steps, assuming we have N items in list. That is called complexity in the worst case, and is called O(n) wich stands for Omikron mathematic function.

It simply tells you: From all situations that can happen, if I choose the worst one, then the metdos will take me N steps, but that is maximum. Pretty bad, right?
Imagine having milion items in there...f. example in a game...

So what I did, it that I created a 
End
variable, pointing to last item in a linked list.
Like that, I just link new item to this last node, 
End -> next = newelement; //let last item point to this one
And set the End variable to the newly added item, wich is last
End = newelement; //let end point to the last item
Now, the complexity now, is O(1). In theory, it would be +1 for any operation in method, so O(4), but that is called as O(1).

Now I also have to delete the linked list. It can be done in more ways, there is one more way wich is elegant, but I am ok with this cycle.
~LinkedList()
Since we will no longer need a ponter to first element, I can start increasing it. So While the Start element is not null,
while(Start)
we save the pointer - Start.
ptrtodelete = Start;
Let start point to next item, and then delete the item we archived

In theory, End can be used instead ptrtodelete to save one variable (4 or 8 bytes for the pointer)

Now I will ask you...what is complexity of this...? If you answered O(n) where n is number of items, you were correct

Last thing, you can see that in constructor
LinkedList() : Start(nullptr), End(nullptr)
I initialize the variables after double-dot. Why not like this...?
 LinkedList()
{
Start = nullptr; 
End = nullptr;
}
The reason is, looking at code above: A new Listitem is created, code goes to constructor.

A Start and End variables are set to random values. That just is what happens.
Then, we in body change them to null (4 operations).

But considering the example above this one, 
A ListItem is created, and values to Start and End are assigned nullptr.
Those are 2 operations.

It wont save you too much, but having huge project, game maybe, at milion allocations, it can save something.

This is incredible thing we were learnt at my faculty, and I love it, because as I looked around, I did not find this yet anywhere on internet. Now I am sharing it with you guys :]

                        
这篇关于删除LinkedList类中的指针的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！