Delete Node

[JohnIsNotAMayor]

This week in my class my professor assigned a project where we have to create a program that reads a txt file and using add, delete, and animation turns it into a print manager. My professor helped me write code for add and I've got several ideas for animation but I have no idea how I would write delete. I would appreciate any help! Please Let me know if more information is needed.

The text in the txt file would be something like this:

A 0 P1 10
A 1 P2 20
A 0 P3 30
A 1 P2
A 1 P4 40
A 1 P5 50
A 2 P6 60
D 2 P6

  
#include <iostream>
#include <string> 
#include <fstream>

using namespace std;

class Node
{
public:
	int x, y;
	string jobName;
	int jobTime;
	Node* next;

	Node() { jobName = ""; jobTime = -1; next = nullptr; };
	Node(string jn, int jt)
	{
		jobName = jn; jobTime = jt; next = nullptr;
	}
};

void Displaypm(Node pm[])
{
	for (int i = 0; i < 5; i++)
	{
		cout << "Location" << i << ": ";
		Node* t;
		t = &pm[i];
		while (t->next != nullptr)
		{
			cout << t->next->jobTime << " ";
			t = t->next;
		}
		cout << endl;
	}
}

void main()
{
	string command, jobName;
	int location, jobTime;
	Node pm[5];
	bool done = false;

	ifstream input("c:\\temp\\input.txt");

	while (!input.eof())
	{
		input >> command;
		if (command == "A")
			input >> location >> jobName >> jobTime;
		else if (command == "B")
			input >> location >> jobName;

		Node* ptr = new Node(jobName, jobTime);
		if (pm[location].next == nullptr)
		{
			pm[location].next = ptr;
		}
		else
		{
			Node* T;
			T = &pm[location];
			done = false;
			while (T->next != nullptr)
			{
				if (T->next->jobTime < ptr->jobTime)
				{
					T = T->next;
				}
				else
				{
					ptr->next = T->next;
					T->next = ptr;
					done = true;
					break;
				}
			}
			if (!done)
				T->next = ptr;
		}
	}
	Displaypm(pm);
	input.close();
}

[Duthomhas]

When dealing with linked lists, the best way to wrap your head around them is to get out a piece of construction paper and some crayons and draw some pictures.

I’m being serious here.
^{_{The construction paper and crayons just make it more fun!}}

[ElusiveTau]

Do you understand how the code works? pm is an array of sorted linked lists (ascending, according to jobTime).

In the input file example, D 2 P6 is probably a command to delete print job (location=6, jobName = P6), which was added when the A 2 P6 60 input line was processed.

Given the code you've posted:
1. What happens when the program sees an "A", "B", or "D" command?
2. How do you locate the right Node to delete? Does the command give you enough information to find the right Node?
3. If the Node that should be deleted, call it Node Y, is between two Nodes i.e., some other Node X points to Y and Y points to Z, how should the node chain look after you delete Y?

Pictorally: X --> Y --> Z. If you delete Y, the node structure should look like: X --> Z. Right?
4. Do you remember how to clean up/delete objects that have been created on the heap using the new keyword?

[seeplus]

Well there's so many issues I just refactored the code to get a working program for additions:

#include <iostream>
#include <string>
#include <fstream>

constexpr size_t NoLists {5};

class Node {
public:
	std::string jobName;
	int jobTime {-1};
	Node* next {};

	Node() {};
	Node(const std::string& jn, int jt) : jobName(jn), jobTime(jt) {}
};

void Displaypm(Node* const pm[NoLists]) {
	for (size_t i {}; i < NoLists; ++i)
		if (pm[i]) {
			std::cout << "Location " << i << ": ";

			for (const auto* t {pm[i]}; t; t = t->next)
				std::cout << t->jobTime << ' ';

			std::cout << '\n';
		}
}

void add(Node*& pm, const std::string& jn, int jobTime) {
	auto* const ptr {new Node(jn, jobTime)};

	if (!pm) {
		// Create new list
		pm = ptr;
		return;
	}

	if (ptr->jobTime < pm->jobTime) {
		// Add to front
		ptr->next = pm;
		pm = ptr;
		return;
	}

	auto* n {pm};

	// Add to middle or end
	for (; n->next && n->next->jobTime < ptr->jobTime; n = n->next);
	ptr->next = n->next;
	n->next = ptr;
}

void remove(Node*& pm, const std::string& jn) {
	// TO DO
}

int main() {
	std::ifstream input("input.txt");

	if (!input)
		return (std::cout << "Cannot open file\n"), 1;

	std::string command, jobName;
	size_t location {};
	Node* pm[NoLists] {};

	while (input >> command >> location >> jobName)
		if (command == "A") {
			int jobTime {};

			// Add to list
			input >> jobTime;
			add(pm[location], jobName, jobTime);
		} else
			if (command == "D")
				// Remove from list
				remove(pm[location], jobName);
			else
				std::cout << "Invalid command found\n";

	Displaypm(pm);

	// Free memory
	for (size_t i {}; i < NoLists; ++i)
		for (auto* n {pm[i]}; n; ) {
			const auto l {n->next};

			delete n;
			n = l;
		}
}

Location 0: 10 30
Location 1: 20 40 50
Location 2: 60

given file containing:

A 0 P1 10
A 1 P2 20
A 0 P3 30
D 1 P2
A 1 P4 40
A 1 P5 50
A 2 P6 60
D 2 P6 

[JohnIsNotAMayor]

Thank you guys for responding! I'm sorry for the delay.

1. An "A" adds a node, I believe "B" adds a new node, and "D" deletes.
2. A temp pointer would allow us to move from node to node and delete them.
3. Once a node is deleted you have to make sure that the previous node is linked to the next node and the next node is linked to the previous.

[JohnIsNotAMayor]

I was able to write some delete code but I've been having a bug where delete works but its deleting the node before the one that it is supposed to. For example, I gave it the instructions of A 0 P1 10
A 1 P2 20
A 0 P3 30
A 1 P4 40
D 1 P4
A 1 p5 50
A 2 p6 60

and A 1 P2 was deleted instead. Any reason why this might be happening? (My code will be down below)

#include <iostream>
#include <string> 
#include <fstream>

using namespace std;

class Node
{
public:
	int x, y;
	string jobName;
	int jobTime;
	Node* next;

	Node() { jobName = ""; jobTime = -1; next = nullptr; };
	Node(string jn, int jt)
	{
		jobName = jn; jobTime = jt; next = nullptr;
	}
};

void DisplayPm(Node pm[])
{
	for (int i = 0; i < 5; i++)
	{
		cout << "Location" << i << ": ";
		Node* t;
		t = &pm[i];
		while (t->next != nullptr)
		{
			cout << t->next->jobTime << " ";
			t = t->next;
		}
		cout << endl;
	}
}

void main()
{
	string command, jobName;
	int location, jobTime;
	Node pm[5];
	int count[5] = { 0,0,0,0,0 };
	bool done = false;

	ifstream input("c:\\temp\\input.txt");

	system("cls");

	while (!input.eof())
	{
		input >> command;
		if (command == "A")
			input >> location >> jobName >> jobTime;
		else if (command == "D")
			input >> location >> jobName;

		if (command == "A")
		{
			Node* ptr = new Node(jobName, jobTime);
			ptr->y = location * 10;
			count[location]++;
			ptr->x = count[location] * 10;


			if (pm[location].next == nullptr)
			{
				pm[location].next = ptr;
			}
			else
			{
				Node* T;
				T = &pm[location];
				done = false;
				while (T->next != nullptr)
				{
					if (T->next->jobTime < ptr->jobTime)
					{
						T = T->next;
					}
					else
					{
						ptr->next = T->next;
						T->next = ptr;
						done = true;
						break;
					}
				}

				if (!done)
					T->next = ptr;
			}
		}
		else if (command == "D")
		{
			Node* T;
			Node* DelPtr;

			T = &pm[location];
			done = false;
			while (T->next != nullptr)
			{
				if (T->next->jobName == jobName);
				{
					if (T->next->next == nullptr)
					{
						DelPtr = T->next;
						T->next = nullptr;
						delete(DelPtr);
						done = true;
						break;
					}
					else
					{
						DelPtr = T->next;
						T->next = T->next->next;
						delete(DelPtr);
						done = true;
						break;
					}
				}
				T = T->next;
			}
		}
	}
	DisplayPm(pm);
	input.close(); 
}

[seeplus]

What debugging of your code have you done? Have you use the debugger to trace through the code, watch the contents of variables and see where the execution deviates from that expected from your design?

Note that L50 your while loop isn't correct. See my code above...

[TheIdeasMan]

void main()

is a sacrilegious crime :+|

[seeplus]

Yeah - obviously hasn't read/understood my code above...

[dhayden]

I feel like you're playing peekaboo with the assignment. Please post the actual text of the assignment. It's hard to tell if you're doing it right or wrong without know exactly what you're supposed to do. In particular, there may be details in the assignment that seem irrelevant but actually affect how it should be coded.

For example, what time should be used for this line?

A 1 P2

[seeplus]

[I assumed this was a mistake above and should have been D 1 P2 ....]

[ElusiveTau]

		else if (command == "D")
			input >> location >> jobName;

This doesn't make sense. Did you just change "B" to "D" for no reason? It seems to me like "B" is just another way to add a print job (i.e., without specifying a job time). Whoever gave you the assignment needs to be asked whether a default value should be used or a different Node array should be used to store print jobs without job time. That's not for you to guess but it is your job to ask for clarification.

			while (T->next != nullptr)
			{
				if (T->next->jobName == jobName);
				{

You have a dangling ; on this line. Note that you can surround code with the braces and create "scope". Memory for objects created inside this scope (i.e., in between the braces) will be released after the closing brace. For example:

int main()
{
    cout << "An if statement that ends prematurely.\n";
    {
    int i = 0; 
    cout << i; // Ok. i is defined in this scope.
    } // After this brace, memory for objects created within the scoping operator is released. 
    cout << i; // Compiler error. Identifer "i" is undefined.
}

I copy-pasted your solution into Visual Studio and the Visual C++ compiler (VC++) issued a warning about it. Handy right?

[seeplus]

To include remove, then possibly:

#include <iostream>
#include <string>
#include <fstream>

constexpr size_t NoLists {5};

class Node {
public:
	std::string jobName;
	int jobTime {-1};
	Node* next {};

	Node() {};
	Node(const std::string& jn, int jt) : jobName(jn), jobTime(jt) {}
};

void Displaypm(Node* const pm[NoLists]) {
	for (size_t i {}; i < NoLists; ++i)
		if (pm[i]) {
			std::cout << "Location " << i << ": ";

			for (const auto* t {pm[i]}; t; t = t->next)
				std::cout << t->jobTime << ' ';

			std::cout << '\n';
		}
}

void add(Node*& pm, const std::string& jn, int jobTime) {
	auto* const ptr {new Node(jn, jobTime)};

	if (!pm) {
		// Create new list
		pm = ptr;
		return;
	}

	if (ptr->jobTime < pm->jobTime) {
		// Add to front
		ptr->next = pm;
		pm = ptr;
		return;
	}

	auto* n {pm};

	// Add to middle or end
	for (; n->next && n->next->jobTime < ptr->jobTime; n = n->next);
	ptr->next = n->next;
	n->next = ptr;
}

void remove(Node*& pm, const std::string& jn) {
	for (Node *ptr {pm}, *prev {}; ptr; prev = ptr, ptr = ptr->next)
		if (ptr->jobName == jn) {
			if (!prev)
				pm = pm->next;
			else
				prev->next = ptr->next;

			delete ptr;
			return;
		}

	std::cout << "Not found for deletion\n";
}

int main() {
	std::ifstream input("input.txt");

	if (!input)
		return (std::cout << "Cannot open file\n"), 1;

	std::string command, jobName;
	size_t location {};
	Node* pm[NoLists] {};

	while (input >> command >> location >> jobName)
		if (command == "A") {
			int jobTime {};

			// Add to list
			input >> jobTime;
			add(pm[location], jobName, jobTime);
		} else
			if (command == "D")
				// Remove from list
				remove(pm[location], jobName);
			else
				std::cout << "Invalid command found\n";

		Displaypm(pm);

		// Free memory
		for (size_t i {}; i < NoLists; ++i)
			for (auto* n {pm[i]}; n; ) {
				const auto l {n->next};

				delete n;
				n = l;
			}
}

A 0 P1 10
A 1 P2 20
A 0 P3 30
D 1 P2
A 1 P4 40
A 1 P5 50
A 2 P6 60
D 2 P6 

Location 0: 10 30
Location 1: 40 50