C++

Forum

 
Destructor for singly linked list

mlholder (77)
Hi all,

I am trying implement a simple singly linked list and I am having a bit of trouble in my linked list deconstructor, or so I believe. The error occurs when the destructor for the Node class is called. Any ideas? Any and all help is greatly appreciated.

Class Node Interface File
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
#ifndef NODE_H
#define NODE_H

class Node
{
   public:
	Node();
	Node(int);
	Node(int, Node*);
	Node(const Node&);
	~Node();
	int getData() const;
	Node* getLink() const;
	void setData(int);
	void setLink(Node*);

   private:
	int data;
	Node *link;
};

#endif


Class Node Implementation File
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
 
#include <iostream>
#include "Node.h"

Node::Node() : data(0), link(nullptr)
{

}

Node::Node(int num) : data(num), link(nullptr)
{

}

Node::Node(int num, Node *ptr) : data(num), link(ptr)
{

}

Node::Node(const Node &node)
{

}

Node::~Node()
{
	delete link;
}

int Node::getData() const
{
	return (data);
}

Node* Node::getLink() const
{
	return (link);
}

void Node::setData(int num)
{
	data = num;
}

void Node::setLink(Node *ptr)
{
	link = ptr;
}


Class SLinkedList Interface File
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
 
#ifndef SLINKEDLIST_H
#define SLINKEDLIST_H

#include "Node.h"

namespace slinkedlist
{
   class SLinkedList
   {
      public:
         SLinkedList();
	 SLinkedList(const SLinkedList&);
	 ~SLinkedList();
	 bool empty() const;
	 Node* search(int);
	 Node *getHead() const;
	 friend std::ostream& operator<<(std::ostream &, const SLinkedList &);
	 void insertHead(int);
	 void insertAfter(int, int);
	 void insertBefore(int, int);
	 void append(int);
	 void removeHead();
	 void removeAfter(int, int);
	 void removeBefore(int, int);
	 void removeTail();
	 void reverse();
	 friend std::istream& operator>>(std::istream &, SLinkedList &);		
      private:
         Node *head;
   };
}

#endif


Class SLinkedList Implementation File
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
 
#include <iostream>
#include <string>
#include <cstdlib>
#include <cctype>
#include "SLinkedList.h"

namespace slinkedlist
{
   SLinkedList::SLinkedList() : head(nullptr)
   {
   }

   SLinkedList::SLinkedList(const SLinkedList &list)
   {

   }
	
   SLinkedList::~SLinkedList()
   {
      if(!empty())
      {
         Node *temp = head;

	 while(temp != nullptr)
	 {
	    Node *nodeToDelete = temp;
	    temp = temp->getLink();
	    delete nodeToDelete;
	 }
      }

	 //_CrtDumpMemoryLeaks();
   }

   bool SLinkedList::empty() const
   {
      return (head == nullptr);
   }

   Node* SLinkedList::search(int num)
   {
      Node *temp = head;

      while( (temp != nullptr) && (temp->getData() != num) )
         temp = temp->getLink();

      return (temp);
   }

   Node* SLinkedList::getHead() const
   {
      return (head);
   }

   std::ostream& operator<<(std::ostream &ostr, const SLinkedList &list)
   {
      using namespace std;
      for(Node *iterator = list.getHead(); iterator != nullptr; iterator =   iterator->getLink())
	  ostr << iterator->getData() << endl;

      return (ostr);
   }

   void SLinkedList::insertHead(int num)
   {
      Node *temp = new Node(num, nullptr);

      if(!empty())
        temp->setLink(head->getLink());

      head = temp;
   }

   void SLinkedList::insertAfter(int num1, int num2)
   {
      //TODO
   }

   void SLinkedList::insertBefore(int num1, int num2)
   {
      //TODO
   }

   void SLinkedList::append(int num)
   {
      if(empty())
      {
         insertHead(num);
      }
      else
      {
         Node *temp = new Node(num, nullptr), *iterator = head;
         while(iterator->getLink() != nullptr)
            iterator = iterator->getLink();
         iterator->setLink(temp);
      }
   }

   void SLinkedList::removeHead()
   {
      //TODO
   }

   void SLinkedList::removeAfter(int num1, int num2)
   {
      //TODO
   }

   void SLinkedList::removeBefore(int num1, int num2)
   {
      //TODO
   }

   void SLinkedList::removeTail()
   {
      //TODO
   }

   void SLinkedList::reverse()
   {
      //TODO
   }

   std::istream& operator>>(std::istream &istr, SLinkedList &list)
   {
      using namespace std;

      char ch;
      string num;

      cin.get(ch);
      while(ch != '\n')
      {
         if(isdigit(ch))
	 {
	    cin.putback(ch);
	    cin >> num;
	    list.append(atoi(num.c_str()));
	 }

	 cin.get(ch);
      }

      return (istr);
   }
}
JayhawkZombie (738)
Why delete just the node's link? Shouldn't you be deleting the entire node?
mlholder (77)
And that my friend is a good question. Honestly, I'm not real sure how to go about doing that. I had thought that by deleting the Node pointers (links) that the code so far would be "bomb proof", or at least to my satisfaction. However, the textbook I am currently working from is somewhat vague in parts. Any ideas on how to go about deleting the entire node as you say?
cire (8284)
1
2
3
4
 
Node::~Node()
{
	delete link;
}


This means that every node after the node being destructed will be deleted in a chain-like fashion. And this means that:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
   SLinkedList::~SLinkedList()
   {
      if(!empty())
      {
         Node *temp = head;

	 while(temp != nullptr)
	 {
	    Node *nodeToDelete = temp;
	    temp = temp->getLink();
	    delete nodeToDelete;
	 }
      }

	 //_CrtDumpMemoryLeaks();
   }

is wrong.

Why? Well, consider what happens on line 11. You delete a node. It's destructor will delete the node it is linked to. That nodes destructor will delete the node it is linked to, ad nauseum.

Which means that temp will be an invalid pointer.

Correct:
1
2
3
4
 
   SLinkedList::~SLinkedList()
   {
        delete head;  // using delete on a null pointer is perfectly fine.
    }


booradley60 (896)
I would say that the delete should be removed from the Node destructor and leave the linked list destructor as is. This will leave the linked list responsible for both the newing and the deleteing of Nodes.
JayhawkZombie (738)
I skimmed this too quickly to even notice that. You're right. You've set up your destructor in such a way that deleting one node will cause the deletion to chain down all the nodes after it.
mlholder (77)
And that would explain why I am getting garbage values in the debugger and pointers that are supposed to be valid, but, I have already deleted them. So, I should change my list destructor and remove the code inside the node destructor, thus basically doing what booradley60 has suggested. Also, thank you all for your time and help. I am sure that this will not be the last problem/error as I make my way through this project.
Topic archived. No new replies allowed.