delete[] operator

[leahloughran]

Hello, I'm having an issue with delete[]. I have class LinkedList, and I'm trying to work with an array of Linked Lists here. When I call delete[] on my array, I get a seg fault, and valgrind basically tells me that there's a lot of invalid reads/deletes. I think it has something to do with the fact that my LinkedList destructor (called implicitly because my Linked Lists are on the stack) already deleted some of the stuff that delete[] is trying to delete... but I can't seem to find anything wrong with my Linked List destructor.

Here is main:

#include "mylinkedlist.h"
#include <iostream>
#include <string>

using namespace std;

int main ()
{
 
  LinkedList<string>* array = new LinkedList<string>[4];
  
  LinkedList<string> listOne;
  LinkedList<string> listTwo;

  listOne.pushFront("two"); //L1: 1 2
  listOne.pushFront("one");

  listTwo.pushFront("four"); //L2: 3 4
  listTwo.pushFront("three");

  array[0] = listOne;
  array[1] = listTwo;

  for (int i = 0; i < 4; i++) //go through array
    {
      cout << "array[i] : " << i << endl;
      if (!array[i].empty())
        {
      cout << (array[i].print()) << endl;
        }
    }

  delete[] array;
}

Here is my Linked List destructor:

  ~LinkedList()
    {
      if (size == 0)
        return;

      Node* temp = head;
      while (temp != NULL)
        {
          head = head->next;
          delete temp;
          temp = head;
          }
    }

Thank you!

[Zhuge]

What do the constructor and pushFront() look like?

[IceThatJaw]

You haven't posted enough code to find the seg fault but as a precaution you can always check a pointer before you try to access it to narrow things out because simple things like that CAN cause a seg fault.

For example:

  ~LinkedList()
    {
      if (size == 0)
        return;

      Node* temp = head;
      while (temp != NULL)
        {
          head = head->next;   // can cause seg fault 
          delete temp;
          temp = head;
          }
    }

I might be extra paranoid but I always check a pointer before accessing it unless I am 100% sure it's valid so I would try:

if (head)
head = head->next;


This is doesn't look like it's the problem and I am probably just too cautious but still. I honeslty dont even use C++ that much anymore but when I do I make sure to be careful, even if it reduces efficiency. Seg faults suck, even with debugging programs.

[cire]

Erm... temp is equal to head.

Temp is not equal to null, therefore head is not equal to null.

He does check.

[IceThatJaw]

I realize that this is not the problem but he might be trying trying to access a null pointer somewhere else. When people wonder why they have seg faults I like to remind them that something as simple as accessing a pointer can be the culprit.

He thinks it's the delete but deleting a null pointer does not cause a seg fault.

[bluecoder]

Where exactly do you get the seg fault while debugging ?

[leahloughran]

Sorry it took so long to post again; I've been gone for the weekend. Here is the constructor and pushFront:

template <typename T>

  LinkedList ()
    {
      head = NULL;
      tail = NULL;
      size = 0;
    }

  void pushFront (const T& item)
  {
    if (size == 0)
      {
        head = new Node (item, NULL, NULL);
        tail = head;
        size++;
        return;
      }
    head->prev = new Node (item, head, NULL);
    head = head->prev;
    size++;
    return;
  }

[doug4]

I think the problem may be in your copy constructor. The lines

array[0] = listOne;
array[1] = listTwo;

probably do shallow copies, so array[0] and listOne refer to the same data. The delete[] may work just fine, but when listOne and listTwo go out of scope, the data in the lists get deleted again, and the core dump occurs.

[leahloughran]

@doug -- that makes a lot of sense but I still don't really know how I can fix it? Thank you for your response.

[doug4]

Without seeing your LinkedList class template, I can't say for sure, but I suspect you did not write a copy constructor. You should. If you didn't, the default copy constructor will copy listOne to array[0] field by field. Unfortunately, your fields head and tail are pointers to dynamically allocated memory, so when the fields are copied, you have 2 lists pointing to the same dynamic memory locations.

Your copy constructor should do a deep copy--not copy the head and tail pointers, but traverse the actual linked lists and make dynamically allocated copies each of the elements. Then the head and tail elements should be assigned to the head and tail of the new linked lists.

That's the correct way to do it. If you are looking for a quick and dirty way to verify that the copy constructor is your problem, just pushFront on array[0] and array[1] and get rid of listOne and listTwo. If the core dump disappears, it will show that the copy constructor is your problem.

[bluecoder]

can you post Node class also .. there might be problem with node class also ..
i also agree with doug4 .

[leahloughran]

Yeah, I don't have a copy constructor so that's probably it. Thanks very much for the tip. Here's the code for my entire list:

#pragma once

#include <sstream>

using namespace std;

template <typename T>

class LinkedList
{
 public:
  class Node
  {
  public:
    T item;
    Node* next;
    Node* prev;

    Node (T item0, Node* next0, Node* prev0)
      {
        item = item0;
        next = next0;
        prev = prev0;
      }

    ~Node()
      {}
  };
  
  //list
  Node* head;
  Node* tail;
  int size;

  LinkedList ()
    {
      head = NULL;
      tail = NULL;
      size = 0;
    }

  ~LinkedList()
    {
      if (size == 0)
        return;

      while (!this->empty())
        this->pop();

    }

  LinkedList& operator = (const LinkedList& list)
    {
      head = list.head;
      tail = list.tail;
      size = list.size;
    }

  int getSize ()
  {
    return this->size;
  }

  void pushFront (const T& item)
  {
    if (size == 0)
      {
        head = new Node (item, NULL, NULL);
        tail = head;
        size++;
        return;
      }
    head->prev = new Node (item, head, NULL);
    head = head->prev;
    size++;
    return;
  }

  T getFront()
  {
    if (head != NULL)
      return head->item;
  }

  void pop ()
  {
    if (size == 0)
      return;
    Node* temp = tail;
    tail = tail->prev;
    delete temp;
    size--;
    return;
  }

  T end ()
  {
    T def;
    if (tail != NULL)
      return tail->item;
    else
      return def;
  }

  T popFront () //pop that removes & returns the front item
  {
    if (head != NULL)
      {
        T item = head->item;
        Node* temp = head;
        head = head->next;
        delete temp;
        size--;
        return item;
      }
  }

  bool empty ()
  {
    return (size == 0);
  }

  void remove (const T item)
  {
    if (head == NULL)
      return;
    for (Node* spot = head; spot->next != NULL; spot = spot->next)
      {
        if (spot->item == item)
          {

            if (spot->prev != NULL)
              spot->prev->next = spot->next;
            else
              head = spot->next; //need to reset head
            if (spot->next != NULL)
              spot->next->prev = spot->prev;
            else
              tail = tail->prev; //reset tail
            size--;
            delete spot;
            return;
          }
      }
  }

  bool find (const T item)
  {
    bool b = false;
    for (Node* spot = head; spot != NULL; spot = spot->next)
      {
        if (spot->item == item)
          b = true;
      }
    return b;
  }

  string print ()
  {
    stringstream ss;
    //Node* spot = head;
    /*while (spot != NULL)
      {
        ss << spot->item;
        if (spot != tail)
          ss << " ";
        spot = spot->next;
      }*/
    for (Node* spot = head; spot != NULL; spot = spot->next)
      {
        ss << spot->item;
        if (spot != tail) //if it's not the last thing
          ss << " ";
      }
    string s = ss.str();
    return s;
  }

};

Also, I know there is something wrong with my remove method but I can't quite seem to figure out what's wrong with it...

[doug4]

A quick look at your code.

Everything I said earlier about a copy constructor needs to be said about the assignment operator. Your code actually uses the assignment operator (I frequently confuse the two in my mind). You actually wrote an assignment operator, but it needs to use deep copy semantics.

Write a function that does a deep copy. The copy constructor will call this new function. The assignment operator, on the other hand, will first check to make sure the lists aren't identical (&list != this), and if not identical will delete its own data and then call the deep copy function.

With dynamically allocated member data, you need a copy constructor (you don't have this), an assignment operator (needs to be fixed) and a destructor (you have this).

I noticed something in your getFront() function. If you have no elements in your list, it doesn't return anything meaningful. You might want to change the prototype to something like
bool getFront (T& retVal);
Or else you need to return an empty T value or something like you did in end(). Realize this only works for data types that have default constructors (no arguments).

[leahloughran]

Thanks very much! That really helped me understand what's going on; I appreciate it. Also, if you happen to see anything wrong with my remove method, feel free to let me know as that's what I'm now having trouble with. It doesn't seem to be properly setting head and tail as it should.

[doug4]

I didn't see anything in your Remove function. How are the head and tail getting messed up?

Also, you might want to change the argument to remove() and find() to constant references rather than constant values.

[leahloughran]

I got it to work; I'm not sure what was happening but it works now! Okay, thanks so much for your help.

[cire]

In your remove function:

for (Node* spot = head; spot->next != NULL; spot = spot->next)

If there is only one Node in the list, spot->next will be NULL, and the body of the for loop will never execute. if the item you're trying to remove is the only item in the list, it will not be removed.

If there is more than one Node in the list, the tail will never be checked because the tail's next pointer is equal to NULL, and the body of the for loop will not execute for the tail.

changing to:

for (Node* spot = head; spot != NULL; spot = spot->next)

will allow you to get rid of the if (head == NULL) check before the loop, as the body of the loop will never execute if head == NULL.