Console crashes when creating linked list class

[GCGsauce]

All the code barring the "remove" function in LinkedL seems to work. When I try to remove a node from the linked list, the console crashes. Can anyone help me solve this problem because no explicit error is thrown which makes me think its a runtime issue as it compiles OK.

#ifndef NODE_H
#define NODE_H

template <typename T>
class Node
{
private:
	T m_Data;
	Node<T>* m_Next;
	Node<T>* m_Prev;
public:
	Node();
	Node(const T& m_Data);
	~Node();

	Node<T>* getNext() const;
	Node<T>* getPrev() const;
	T& getData();

	void setNext(Node<T>* n);
	void setPrev( Node<T>* p);
	void setData(const T& data);
};

template <typename T>
Node<T>::Node()
{
	m_Data = T();
	m_Next = 0;
	m_Prev = 0;
}

template <typename T>
Node<T>::Node(const T& data)
{
	m_Data = data;
	m_Next = 0;
	m_Prev = 0;
}

template <typename T>
Node<T>::~Node()
{
	delete m_Next;
	delete m_Prev;

	m_Next = 0;
	m_Prev = 0;
}

template <typename T>
Node<T>* Node<T>::getNext() const {
	return m_Next;
}

template <typename T>
Node<T>* Node<T>::getPrev() const {
	return m_Prev;
}

template <typename T>
void Node<T>::setNext(Node<T>* n) {
	m_Next = n;
}

template <typename T>
void Node<T>::setPrev(Node<T>* p) {
	m_Prev = p;
}

template <typename T>
void Node<T>::setData(const T& data) {
	m_Data = data;
}

template <typename T>
T& Node<T>::getData() {
	return m_Data;
}


#ifndef LINKEDLIST_H
#define LINKEDLIST_H
#include "Node.h"
#include <iostream>

using namespace std; 

template <typename T>
class LinkedL
{
public:
	LinkedL();
	~LinkedL();

	bool isEmpty();
	void insertFirst(const T& data);
	void insertLast(const T& data);
	void insertAfter(const T& key, const T& data);
	int getSize()const;
	Node<T>* getNode(int i) const;
	bool remove(int i);

	T& operator[](int i);

private:
	Node<T>* m_First;
	Node<T>* m_Last;
	int m_Size;
};

template <typename T>
LinkedL<T>::LinkedL()
{
	m_First = 0;
	m_Last = 0;
	m_Size = 0;
}

template <typename T>
LinkedL<T>::~LinkedL()
{
	if (m_First != 0) {
		Node<T>* current = m_First;
		while (current != 0) {
			Node<T>* oldNode = current;
			current = current->getNext();
			delete oldNode;
			oldNode = 0;
		}
	}
}

template <typename T>
bool LinkedL<T>::isEmpty() {
	if (m_First == 0) {
		return true;
	} return false; 
}

template <typename T>
void LinkedL<T>::insertFirst(const T& data) {
	Node<T>* newNode = new Node<T>(data);
	if (isEmpty()) {
		m_First = newNode;
		m_Last = newNode;
	}
	else {
		m_First->setPrev(newNode);
		newNode->setNext(m_First);
		m_First = newNode;
	}
	m_Size;
}

template <typename T>
void LinkedL<T>::insertAfter(const T& key, const T& data) {
	if (isEmpty()) {
		return;
	} 
	Node<T>* current=0;
	for (int i = 0; i <= this->getSize(); i++) {
		if (this->operator[](i) == key) {
			current = this->getNode(i);
		}
	}
	Node<T>* newNode = new Node<T>(data);
	if (current == 0) {
		cout << "Node could not be found." << endl;
		return;
	}
	else if (current==m_Last) {
		
		m_Last = newNode;
		newNode->setNext(0);
	}
	else {
		current->getNext()->setPrev(newNode);
		newNode->setNext(current->getNext());
	}
	current->setNext(newNode);
		newNode->setPrev(current);
}

template <typename T>
int LinkedL<T>::getSize() const{
	return m_Size;
}

template <typename T>
void LinkedL<T>::insertLast(const T& data) {
	Node<T>* newNode = new Node<T>(data);
	if (isEmpty()) {
		m_Last = newNode;
		m_First = newNode;
	}
	else {
		m_Last->setNext(newNode);
		newNode->setPrev(m_Last);
		m_Last = newNode;
	}
	m_Size++;
}

template <typename T>
T& LinkedL<T>::operator[](int i) {
	int counter = 0;
	Node<T>* current = m_First;

	while (true) {
		if (counter == i) {
			return current->getData();
		}
		current = current->getNext();
		counter++;
	}
}

template <typename T>
Node<T>* LinkedL<T>::getNode(int i) const{
	int counter = 0;
	Node<T>* current = m_First;
	if (i<0 && i>this->getSize()) {
		return nullptr;
	}
	while (true) {
		if (counter == i) {
			return current;
		}
		current = current->getNext();
		counter++;
	}
}

template <typename T>
bool LinkedL<T>::remove(int i) {

	if (isEmpty() || i<0 || i>getSize()) {
		cout << "No nodes to remove in specified index" << endl;
		return false;
	}
	else if (getNode(i - 1) != 0 && getNode(i + 1) != 0) {
		getNode(i)->getPrev()->setNext(getNode(i)->getNext());
		getNode(i)->getNext()->setPrev(getNode(i)->getPrev());
		delete getNode(i);
		return true;
	}
	else if (i==0) { //remove first element
		getNode(i + 1)->setPrev(0);
		m_First = getNode(i + 1);
		delete getNode(i);
		return true;
	}
	else {//remove last element
		getNode(i - 1)->setNext(0);
		m_First = getNode(i - 1);
		delete getNode(i);
		return true;
	}
}

#endif // !LINKEDLIST_H


#include <iostream>
#include "LinkedL.h"

using std::cout;
using std::endl;



int main() {

	LinkedL<int> list;
	list.insertFirst(31);
	list.insertLast(23);
	list.insertAfter(23, 67);
	list.insertAfter(23, 45);
	list.remove(1);
	cout << list[0] <<endl;
	system("PAUSE");
}	

[coder777]

The problem in the remove(...) function is the use of getNode(i).

The point is that getNode(i) searches an existing node. As soon as you remove the node from the list (line 243) it cannot not be found and the wrong node (line 245) will be deleted.

[GCGsauce]

ahhhh i get it. thanks. could you suggest a solution?

I was thinking of this:

bool LinkedL<T>::remove(int i) {
	Node<T>* prev = getNode(i - 1);
	Node<T>* next = getNode(i + 1);

	if (isEmpty() || i<0 || i>getSize()) {
		cout << "No nodes to remove in specified index" << endl;
		return false;
	}
	else if (prev != 0 && next != 0) {
		delete getNode(i);
		prev->setNext(next);
		next->setPrev(prev);
		return true;
	}

But this doesnt work either

I jsut want to see if I can make a solution with my current functions

[coder777]

The next problem is this:

template <typename T>
Node<T>::~Node()
{
	delete m_Next;
	delete m_Prev;

	m_Next = 0;
	m_Prev = 0;
}

Once you delete a single node you delete the whole list recursively.

[GCGsauce]

Ok that does make sense. It's because it literally keeps on deleting the next pointers to nodes.
I think I have a good idea on how to execute the remove method as you can apparently set the getNode(i) equal to a node ptr variable and deleting the node ptr variable will delete the shared memory as well.

But what should i do with the destructor? Like I would need to delete the node and free memory but then deleting the nodes deletes all the next/prev elements.

[GCGsauce]

I'm looking to approach it like in this document:

http://faculty.cs.niu.edu/~mcmahon/CS241/Notes/doubly_linked.html

But I'm wondering how the dtor of node would look like because as you said it would recursively delete the whole list.

I solved the problem like this:

	Node<T>* iNode = getNode(i);

	if (isEmpty() || i<0 || i>getSize()) {
		cout << "No nodes to remove in specified index" << endl;
		return false;
	}
	else if (getNode(i-1) != 0 && getNode(i+1) != 0) {
		getNode(i - 1)->setNext(getNode(i + 1));
		getNode(i + 1)->setPrev(getNode(i - 1));
		iNode->setNext(T());
		iNode->setPrev(T());
		delete iNode;

but I have a feeling this isnt a good solution as the delete should be able to do all the work.

[coder777]

But I'm wondering how the dtor of node would look like because as you said it would recursively delete the whole list.

It doesn't make sense to have a destructor for node at all. You could make Node a private class of LinkedL because it is not used anywhere else.

I would suggest that you remove the public setter/getter of Node and make the member variables public because otherwise you have just overhead without gain.

Further i would suggest that you use getNode(...) only once at the beginning. The rest can be done with Prev/Next.