Linked list, delete node at x position

[darego]

Hi guys,

I am working on a linked list to try and understand them a bit better. I currently have a function to insert a node into the list, display the list and delete the most recent node in the list. I am having trouble with a function which takes an int pos as an argument and deletes the int found in the pos position of the list

I would appreciate it if someone could fill me in on how to go about implementing this function in the ListOfInts classes (psuedo code or functional code)

  // ListOfInts.h
#ifndef LISTOFINTS_H
#define LISTOFINTS_H
#include "NodeOfInt.h"

class ListOfInts
{
	friend class NodeOfInt;
public:

	ListOfInts();
	~ListOfInts();

	void insertInt(int);
	void displayList();
	int deleteMostRecent();
	int deleteInt(int);

private:

	NodeOfInt* head;
};

typedef NodeOfInt* ListNodePtr;

#endif


// ListOfInts.cpp
#include "pch.h"
#include <iostream>
#include "ListOfInts.h"
using namespace std;

ListOfInts::ListOfInts()
{
	head = NULL;
}

ListOfInts::~ListOfInts()
{

}
void ListOfInts::insertInt(int x)
{
	NodeOfInt* newNode = new NodeOfInt(x);
	newNode->next = head;
	head = newNode;
}

void ListOfInts::displayList() 
{
	ListNodePtr tempPtr = head;
	while (tempPtr != NULL)
	{
		cout << tempPtr->data << " ";
		tempPtr = tempPtr->next;
	}
}


int ListOfInts::deleteMostRecent()
{
	int temp; 
	ListNodePtr tempPtr = head;
	head = head->next;
	temp = tempPtr->data;
	delete tempPtr;
	return temp;

}

int ListOfInts::deleteInt(int pos)
{
	
}


//NodeOfInt.h
#ifndef NODEOFINT_H
#define NODEOFINT_H

class NodeOfInt
{
	friend class ListOfInts;
public:
	NodeOfInt(int);

private:
	int data;
	NodeOfInt* next;
};
typedef NodeOfInt* ListNodePtr;

#endif

//NodeOfInt.cpp
#include "pch.h"
#include <iostream>
#include "NodeOfInt.h"
using namespace std;

NodeOfInt::NodeOfInt(int d)
{
	data = d;
}

//main.cpp
#include "pch.h"
#include <iostream>
#include "ListOfInts.h"
#include "NodeOfInt.h"
using namespace std;


int main()
{
	ListOfInts int1;
	int1.insertInt(5);
	int1.insertInt(7);
	int1.insertInt(3);

	// cout << int1.deleteMostRecent();
	int1.displayList();
}

[Repeater]

Again, you need to think first about the logic.

Draw a diagram. That'll help you a lot with this sort of thing.

It's not just that you need to delete a node somewhere in the list.

You need the list to still work afterwards.

So if you have the nodes in the list like this:

1 -> 2 ->3 ->4 ->5

and you want to delete node 3, when you're done the list needs to look like this:

1 -> 2 -> 4 -> 5

So you need to find the right node, make the node before point to the node after, and then delete.

[Repeater]

Don't forget to handle the special cases where the first or last node is being deleted.

[Repeater]

While I'm here, at some point you're going to have to write the destructor so that you don't leak memory. By the time the list has been destroyed, everything that was allocated using new must have been deallocated using delete.

[darego]

i was going to try the following code, but since i have gone past the node before, how do i link it with the node after.. before deleting the node in pos

int ListOfInts::deleteInt(int pos)
{
	ListNodePtr tempPtr = head;
	int count = 0;

	while (tempPtr != NULL)
	{
		if (count == pos)
		{
			return tempPtr->data;
			//delete node code
		}
		count++;
		tempPtr = tempPtr->next;
	}
}

[Repeater]

As you go through the list, looking for the node to delete, you need to keep track of the node before.

int ListOfInts::deleteInt(int pos)
{
	ListNodePtr tempPtr = head;
	int count = 0;

        ListNodePtr nodeBefore = nullptr;

	while (tempPtr != NULL)
	{
		if (count == pos)
		{
                    // in here, make the nodeBefore point at the node after 
                   //   then delete this node that you have found is the right node to delete

                   return someValue;

		}
		count++;

                nodeBefore = tempPtr;
		tempPtr = tempPtr->next;
	}
}

[Repeater]

I must say, I don't see any benefit to this:
typedef NodeOfInt* ListNodePtr;

It's not shorter to write and it obscures the actual type.

[darego]

Thanks a lot Repeater! You've been very helpful again.. code below works perfect and now i understand a lot more about linked lists as a whole.

Regarding typedef, our lecturer told us to use it as it saves us from typing in the pointer * every time, although this is not a lot to type so i can't see the benefit either. maybe he was just trying to introduce us to what we can do with typedef

int ListOfInts::deleteInt(int pos)
{
	ListNodePtr tempPtr = head;
	int count = 0;

	ListNodePtr nodeBefore = nullptr;

	while (tempPtr != NULL)
	{
		if (count == pos)
		{
			int data = tempPtr->data;
			nodeBefore->next = tempPtr->next;
			delete tempPtr;
			return data;
		}
		count++;

		nodeBefore = tempPtr;
		tempPtr = tempPtr->next;
	}
}