c++ - Deleting a pointer in a LinkedList class

Question

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.

Answer 1

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 :]