I'm currently working on a program with linked lists. The program asks you to enter five integers, and every time you enter one that integer is added to the front of the list. My issue is that for each input, i need to insert the node at the beginning of the list (which is working), but then i need to scan the rest of the list and delete all nodes that are less than that node value. I have the CompareNodes function that i'm currently using to do this, however I'm a bit confused and haven't made it work. If you have some advice please let me know.

#include <iostream>
#include <list>
#include <string>
#include "node.h"

using namespace std;

template <typename T>
void WriteLinkedList(node<T> *front, const string& separator = " ")
{
	//front points at first node. curr moves through the list
	node<T> *curr;
	curr = front;

	while (curr != NULL)
	{
		//output node value and move to the next node
		cout << curr->nodeValue << separator;
		curr = curr->next;
	}
}

template <typename T>
void CompareNodes(node<T> * & front, T& target)
{
	node<T> *curr = front, *prev = NULL;

	while (curr != NULL )
	{
		if (curr->nodeValue < target)
		{

			delete curr;
		}
		else
		{
			prev = curr;
			curr = curr->next;
		}
	}
}

int main()
{
	node<int> *front = NULL, *p;
	int i = 0, n = 0;

	int num1 = 0, num2 = 0, num3 = 0, num4 = 0, num5 = 0;

	cout << "Enter 5 numbers to be inserted into the list: " << endl;
	cin >> num1 >> num2 >> num3 >> num4 >> num5;

	p = new node<int>(num1, front);
	front = p;
	CompareNodes(front, num1);
	p = new node<int>(num2, front);
	front = p;
	CompareNodes(front, num2);
	p = new node<int>(num3, front);
	front = p;
	CompareNodes(front, num3);
	p = new node<int>(num4, front);
	front = p;
	CompareNodes(front, num4);
	p = new node<int>(num5, front);
	front = p;
	CompareNodes(front, num5);

	//CompareNodes(front);

	WriteLinkedList(front, " ");

	system("PAUSE");
	return(0);

}

this is my node class:

template <typename T>
class node
{
public:
	T nodeValue;	//data held by the node
	node<T> *next;	//next node in the list

	//default contructor with no initial value
	node() : next(NULL)
	{}


	//constructor. initialize nodeValue and next
	node(const T& item, node<T> *nextNode = NULL) :
		nodeValue(item), next(nextNode)

	{}
	
};

In your compareNode function you cannot just delete the node like that,

if (curr->nodeValue < target){
 delete curr; //No No No
}

Since this is a single linked list, what you need to do, is set the previous
pointer, that points to curr, to now point to curr.next. Then you can safely delete
curr without messing up the link. Otherwise, you will break the chain. So it should
be something like this :

if(curr->nodeValue < targetValue){
   removeNode(front,curr ); //removeNode fixes the chain, and removes the node from the list
}

void removeNode(node<T>*&front, node<T>*& nodeToRemove){
 node*& prev = findNodeBefore(nodeToRemove, front);
 prev.next = nodeToRemove.next; //fix the link by removing the nodeToRemove node
 delete nodeToRemove;
}

thanks for the help. I'm pretty new to linked lists though, and I'm not really sure how to go about creating the findNodeBefore function.

The findNodeBefore should return a reference to the node before the passed in node.
To do that, you need to transverse the node until, node.next equals the passed in node.

Edited 6 Years Ago by firstPerson: n/a

here's what i have so far.. i think i'm getting close, the program runs but doesn't work and doesn't give me a error, so i'm in the process of trying to figure it out.

#include <iostream>
#include <list>
#include <string>
#include "node.h"

using namespace std;

template <typename T>
void WriteLinkedList(node<T> *front, const string& separator = " ")
{
	//front points at first node. curr moves through the list
	node<T> *curr;
	curr = front;

	while (curr != NULL)
	{
		//output node value and move to the next node
		cout << curr->nodeValue << separator;
		curr = curr->next;
	}
}

template <typename T>
void CompareNodes(node<T> * & front, T& target)
{
	node<T> *curr = front, *prev = NULL;

	while (curr != NULL )
	{
		if (curr->nodeValue < target)
		{
			removeNode(front,curr);
			
		}
	}
}

template <typename T>
void removeNode(node<T> *& front, node<T> *& nodeToRemove)
{
	node<T> *prev = &findNodeBefore(front, nodeToRemove);
	prev->next = nodeToRemove->next;
	delete nodeToRemove;
}

template <typename T>
node<T> findNodeBefore(node<T> *& front, node<T> *& nodeToRemove)
{
	node<T> *temp = front;
	node<T> *prev = NULL;

	do{
		prev = temp;
		temp = temp->next;
	}while(temp->next != nodeToRemove);
	
	//return(0);
	return *prev;
}

int main()
{
	node<int> *front = NULL, *p;
	int i = 0, n = 0;

	int num1 = 0, num2 = 0, num3 = 0, num4 = 0, num5 = 0;

	cout << "Enter 5 numbers to be inserted into the list: " << endl;
	cin >> num1 >> num2 >> num3 >> num4 >> num5;

	p = new node<int>(num1, front);
	front = p;
	CompareNodes(front, num1);
	p = new node<int>(num2, front);
	front = p;
	CompareNodes(front, num2);
	p = new node<int>(num3, front);
	front = p;
	CompareNodes(front, num3);
	p = new node<int>(num4, front);
	front = p;
	CompareNodes(front, num4);
	p = new node<int>(num5, front);
	front = p;
	CompareNodes(front, num5);

	//CompareNodes(front);

	WriteLinkedList(front, " ");

	system("PAUSE");
	return(0);

}
This article has been dead for over six months. Start a new discussion instead.