Linked Lists: deleting an element

[Micard]

Hey, could you please correct this code for me? I tried like tens of different ways to re-write it and it either doesn't work or gives me a memory-leak error.

// Removes the last passenger
void removePassenger(Passenger *&head, Passenger *&last)
{
	if(isEmpty(head))	// Simple check if the list is empty
		printf("Error: The list is already empty!\n");	// If empty - displays an error
		else if (head == last)
		{
			delete head;				//
			head = NULL;				// A way to delete if there's only 1 passenger 
			last = NULL;				//
		}
					
		else 
		{
			Passenger *temp = head;		// A way to delete if there's more than 1 passenger
			head = head -> next;		// with moving pointer to next passenger
			delete temp;				//
			cout << "\nPassenger has been successfully removed!\n";
		}
}

Oh, the way shown above WORKS and deletes the first element in the list, but how do I delete the LAST element and set the previous element to be the last after deleting it. It's a "one way" list so yeah, I know it makes it more difficult.

I tried temp = last; delete temp - memory leak. I get why, but I don't know how to fix it.

And then, what if I want to search for an element, which is okay, I cant do it, but then how do I delete it? Just by creating new temp and then deleting temp after equaling it to whatever I need? I think that'll cause a memory leak.

[ats15]

You need to check not if the current element is last, but if the next is last. So you traverse the list as
*current=head;
*currentPlus1=current->next;
Then you loop current=currentPlus1 until currentPlus1==last. When you exit the loop you have currentPlus1=last, and current->next=last. So you can delete last, and you must set current->next to NULL

[Micard]

Yep, works! Thank you! So I decided to modify it a little bit. It's pretty self-explanatory, so please take a look. When I choose 'y' and enter the name it gives me a memory leak error:

void removePassenger(Passenger *&head, Passenger *&last)
{
	string n_name, f_name, l_name;
	Passenger *n_temp = new Passenger;
	n_temp = head;
	Passenger *tempPlus1 = new Passenger;
	tempPlus1 = n_temp -> next;
	char ans;
	cout << "Do you want to remove a specific passenger? Answer (Y/N): ";
	cin >> ans;
	switch(ans)
	{
		case 'n':
	if(isEmpty(head))	// Simple check if the list is empty
		printf("Error: The list is already empty!\n");	// If empty - displays an error
		else if (head == last)
		{
			delete head;				//
			head = NULL;				// A way to delete if there's only 1 passenger 
			last = NULL;				//
		}
					
		else 
		{	
			Passenger *current = new Passenger; 
			current = head;
			
			while(current -> next != last)
			{
				current = current -> next;
			}
			
			delete last;
			current -> next = NULL;
			cout << "\nPassenger has been removed!\n";
		}
		break;
			case 'y':
				if(isEmpty(head)) {	// Simple check if the list is empty
				printf("Error: The list is empty!\n");	// If empty - displays an error
				break; 
				}
				
				cout << "\nFirst name: ";
				cin >> f_name;	
				cout << "\nLast name: ";
				cin >> l_name;
				n_name = f_name + " " + l_name;
				
				while(tempPlus1 != last)
				{
					if(tempPlus1 -> name != n_name)
					{
						n_temp = n_temp -> next;
					} else if (tempPlus1 -> name == n_name)
						{
							delete tempPlus1;
							n_temp -> next = NULL;
						} else cout << "\nError: Passenger not found!\n";
				}

			cout << "\nPassegner " << n_name << " has been removed!\n";
			break;
			default:
			cout << "\nPlease enter Y for \'yes\' and N for \'no\'!\n";
	}
}

[Micard]

Up

[TarikNeaj]

Bump*

[doug4]

Why are you calling new in lines 5, 7 and 26? You are dynamically allocating memory which is never deleted.

You are trying to make things too complicated. In the general case, you need 2 pointers that act like this:

General Case:

         |------|-----|   |------|-----|
  ... -->| data |next |-->| data |next |-->{another node or NULL}
         |------|-----|   |------|-----|

         ^                ^
         |                |
         |                |
current --                |
                          |
currentPlus1---------------

When you want to delete currentPlus1, make sure you assign current-> next the value that currentPlus1->next is before you do the delete. When you are done, check to see if current->next is NULL. If it is, current is your new "last".

The special case where you want to delete the head of the list is similar:

Remove Head of List

         |------|-----| 
 first-->| data |next |-->{another node or NULL}
         |------|-----|

         ^
         |
current --

In this case, merely make sure you assign "first" the value that current->next contains before you do the delete. Check to see if "first" is NULL, and if it is, the list is empty and you can set "last"=NULL.

[Micard]

doug4, yep. Got it rolling. Thank you! ats15, thanks to you too!