Deleting nodes in a linked list with recursion

Thanks in advance for your assistance!

Problem: I am learning how to use recursion in my code. This particular project is a linked list class with a function (pair of functions, actually) that are supposed to delete the list recursively, starting from the tail, if I understand what I'm doing. They mostly do that, but leave two nodes with garbage values. Additionally, on exiting my driver program, I receive an error:

free(): double free detected in tcache 2
Aborted

Additionally, the way I've implemented this is probably pretty ugly. If anyone has any pointers (Pun only kind of intended), I would appreciate it!

Specific Functions:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void List::delrecur()
     {
          delrecur2(headptr);
          return;
     }

     void List::delrecur2(Node* temp)
     {
          
          if (temp == NULL)
          {
               return;
          }
          delrecur2(temp->getlink());
          free(temp);
          return;
     }


Header 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
class List
     {
     public:
          List();
          ~List();
          
          class Node
          {
          public:
               Node(const int& newdata, Node* newlink = NULL){data = newdata, link = NULL;}
               void setdata(const int newdata){data = newdata;}
               void setlink(Node* newlink) {link = newlink;}
               
               int getdata() {return data;}
               Node* getlink() {return link;}
          
          private:
               int data;
               Node* link;
          };
          void insert(Node*& headptr, const int entry){headptr = new Node(entry);}
          void inserthead(const int);
          int get_top() {return headptr->getdata();}
          void headremove();
          bool search(int);
          void drop(int);
          void printList();
          bool empty() const;
          void delrecur();
          void delrecur2(Node*);
          void insertnew(const int&);
          
             
     private:
         
          Node* headptr;
          int used;
     };    
}
#endif 


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
List::List()
     {
          used = 0;
          headptr = NULL;
         // cout << "headptr link:  " << headptr->getlink() << endl;
     }

     List::~List()
     {
          while(!empty())
          {
               headremove();
          }
     }

     bool List::empty() const {return headptr == nullptr;}

     void List::inserthead(int newdata) {headptr = new Node(newdata, headptr);}


     void List::insertnew(const int& entry)
     {
          if (headptr == NULL)
          {
               inserthead(entry);
          }
          else
          {
               Node* tempptr = new Node(entry);
               tempptr->setlink(headptr);
               tempptr->setdata(entry);
               headptr = tempptr;
          }
          used++;
          cout << "headptr link:  " << headptr->getlink() << endl;
          return;
     }

     void List::headremove()
     {
         
          if(!empty())
          {
               Node* temp = headptr;
               headptr = headptr->getlink();
               delete temp;
          }
          return;
     }

     void List::delrecur()
     {
          delrecur2(headptr);
          return;
     }

     void List::delrecur2(Node* temp)
     {
          
          if (temp == NULL)
          {
               return;
          }
          delrecur2(temp->getlink());
          free(temp);
          return;
     }

     bool List::search(int target)
     {
          bool found = false;
          assert (used > 0);

          Node* tempptr;
          for (tempptr = headptr; tempptr->getlink() != NULL; tempptr = tempptr->getlink())
          {
               if (tempptr->getdata() == target)
               {
                    found = true;
                    break;
               }
               
          cout << "Test line \n";        
          }
          return found;
     }

     void List::drop(int target)
     {
          assert (used > 0);
     
          Node *prev, *curr;
          prev = NULL;
          curr = headptr;

          while (curr != NULL)
          {
               if (curr->getdata() == target)
               {
                    prev->setlink(curr->getlink());
                    free(curr);
                    cout << "Target removed!" << endl;
                    used--;
                    break;
               }
               
               {
                    curr = curr->getlink();
                    prev = prev->getlink();
               }
          }
               
          
          return;
     }

     void List::printList()
     {
          if(headptr == NULL)
          {
               cout << "List is empty. \n";
          }
          else
          {
               Node* tempptr;
               tempptr = headptr;
               int counter = 1;
               while (tempptr != NULL)
               { 
                    cout << "Node " << counter << ":  " << tempptr->getdata() << endl;
                    tempptr = tempptr->getlink();
                    counter++;
               }
          }
          return;
     }
                                




Expected output (Following entry of Nodes holding 11, 22, 33, 44, 55, then calling delrecur, printList functions:
List is empty
Actual output:
Node 1: (garbage value)
Node 2: (garbage value)
On exit:
free(): double free detected in tcache 2
Aborted
Last edited on
In delrecur() you need to set headptr = NULL, otherwise you have a list with deleted nodes.
Aha! Thank you!
Registered users can post here. Sign in or register to post.