I am writing the code in C++ for a doubly linked list. I'm a beginner to C++ so forgive me for asking this. I am populating the doubly linked list with numbers (1,2,3,...,n). I use the search function first and find the node that contains the value I want to remove. Then I call the remove function in order to remove the node. My remove function seems to be removing more than just one node and I have been wracking my head trying to figure it out. I think it might be because my DList class does not have a destructor but I'm not sure how to implement that as the structure I'm trying to delete is a ListNode. Any insight would be much appreciated. Thank you.
eg. test case n = 8
list before deletion: 1 2 3 4 5 6 7 8
list after deletion: 7
DLIST.H
#ifndef DLIST_H
#define DLIST_H
struct ListNode
{
/* define your list node type */
int val;
ListNode* next;
ListNode* prev;
};
class DList
{
public:
DList();
/* implement copy constructor, assignment, destructor if needed */
void add_to_front(int value);
void add_to_back(int value);
int first();
int last();
void remove(ListNode* node);
void display();
ListNode* previous(ListNode* node);
ListNode* next(ListNode* node);
ListNode* search_value(int value);
private:
/* declare your data */
ListNode* head;
ListNode* tail;
};
#endif
DLIST.CC
#include "dlist.h"
#include <cstddef>
#include <cstdlib>
#include <cstdio>
#include <iostream>
//ListNode* head;
//ListNode* tail;
DList::DList(){
head = NULL;
tail = NULL;
}
void DList::add_to_front(int value){
if (head != NULL){
//std::cout<<"addfront1\n";
ListNode *newhead = new ListNode();
newhead->val = value;
//std::cout<<"addfront1 val" << newhead->val << "\n";
newhead->next = head;
newhead->prev = NULL;
head->prev = newhead;
head = newhead;
}else{
//std::cout<<"addfront2\n";
ListNode *newhead = new ListNode();
newhead->val = value;
//std::cout<<"addfront2 val" << newhead->val << "\n";
newhead->prev = NULL;
newhead->next = NULL;
head = newhead;
tail = newhead;
}
}
void DList::add_to_back(int value){
if (tail != NULL){
//std::cout<<"addback1\n";
ListNode *newtail = new ListNode();
newtail->val = value;
//std::cout<<"addback1 val" << newtail->val << "\n";
newtail->next = NULL;
newtail->prev = tail;
tail->next = newtail;
tail = newtail;
}else{
//std::cout<<"addback2\n";
ListNode *newtail = new ListNode();
newtail->val = value;
//std::cout<<"addback2 val" << newtail->val << "\n";
newtail->prev = NULL;
newtail->next = NULL;
tail = newtail;
head = newtail;
}
}
int DList::first(){
return head->val;
}
int DList::last(){
return tail->val;
}
void DList::remove(ListNode* node){
std::cout << "want to del value is " << node->val << "\n";
ListNode *toDelete = new ListNode();
if (head == NULL || tail == NULL){
return;
}
if(head->val == node->val){
toDelete = head;
head = node->next;
if (head != NULL){
head->prev = NULL;
}
std::cout << "del1 value is " << toDelete->val << "\n";
delete(toDelete);
}else if(tail->val == node->val){
toDelete = tail;
tail = node->prev;
std::cout << "del2 newtail value is " << node->prev->val << "\n";
if (tail != NULL){
tail->next = NULL;
}
std::cout << "del2 value is " << toDelete->val << "\n";
delete(toDelete);
}else if (node != NULL){
std::cout << "node1 value is " << node->val << "\n";
node->prev->next = node->next;
node->next->prev = node->prev;
std::cout << "node2 value is " << node->val << "\n";
delete(node);
}
}
ListNode* DList::previous(ListNode* node){
if(node->prev != NULL){
return node->prev;
}else{
return node;
}
}
ListNode* DList::next(ListNode* node){
if(node->next != NULL){
return node->next;
}else{
return node;
}
}
ListNode* DList::search_value(int value){
//std::cout << "head.0\n";
//std::cout << "head value is " << head->val << "\n";
while(head->next != NULL){
//std::cout << "head.1\n";
if(head->next->val == value){
//std::cout << "head.2\n";
return head->next;
}else{
//std::cout << "head.3\n";
head = head->next;
}
}
if (head->next == NULL){
if (head->val == value){
return head;
}else{
//std::cout << "error\n";
}
}
}
void DList::display(){
std::cout<<"Element In The Linked List Are : ";
ListNode *disp= new ListNode;
disp = head;
while(disp!=NULL)
{
std::cout<<" "<<disp->val;
if(disp->next==NULL)
{
std::cout<<"\n";
break;
}
disp=disp->next;
}
}
DLIST_TEST.CC
#include <cassert>
#include <cstdlib>
#include <cstdio>
#include <ctime>
#include <iostream>
#include <iomanip>
#include "dlist.h"
using namespace std;
int main (int argc, char* argv[])
{
int N = -1;
if (argc == 2) {
N = atoi (argv[1]);
assert (N > 0);
}
//cout << "N is " << N << "\n";
DList testList = DList();
int i = 0;
while(i<N){
//cout << "i value is "<< i << "\n";
testList.add_to_back(i+1);
//cout << "second\n";
i++;
}
int randn = rand() % N + 1;// randn in the range 1 to N
cout << "randn is "<< randn <<"\n";
testList.display();
clock_t t1,t2;
t1=clock();
ListNode* loc = testList.search_value(randn);
cout << "loc value is "<< loc->val <<"\n";
testList.remove(loc);
t2=clock();
float diff ((float)t2-(float)t1);
float seconds = diff / CLOCKS_PER_SEC;
cout<<"\nTime taken by function: "<<seconds<<" seconds\n" << endl;
testList.display();
testList.add_to_front(N);
testList.display();
return 0;
}
ListNode *toDelete = new ListNode();has no business being in a "remove" function, especially since it is the start of what ultimately becomes a memory leak. - WhozCraigListNode *disp= new ListNode;bug is indisplay(). - drescherjmnodeto remove is in the middle of the list but it happens to have the same value as the head or the tail node, yourremove()will delete the wrong node from the list. That's another bug you will have to fix. And to figure out the reason for your bug, you need to use a debugger. Have you used a debugger, yet, to debug your program, and if not why not? - Sam Varshavchik