C++

Forum

 
Deleting a Linked List

jhykima (125)
Hello and I hope all is well. I am trying to remove the third node from the linked list and then linking the second and fourth nodes together. However, I'm not sure how to accomplish this.

Here is my line of reasoning:
1. Traverse to the third linked list.
2. Delete it.
3. Change the second linked list's pointer to point to the address of the first element in the fourth linked list.

First, I'm not sure how to delete the third linked list... I tried using the delete syntax but it didn't work. Or maybe, I just don't know how to write it correctly.
Second, I have no idea how to accomplish the third step. Haha...

Any suggestions? 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
 
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std; 

struct EnemySpaceShip
{
	int x_coordinate; 
	int y_coordinate; 
	int weapon_power;
	EnemySpaceShip *p_next_enemy; 	
};

EnemySpaceShip *p_enemies = NULL; 

EnemySpaceShip *getNewEnemy ()
{
	EnemySpaceShip *p_ship = new EnemySpaceShip;
	p_ship->x_coordinate = 0; 
	p_ship->y_coordinate = 0; 
	p_ship->weapon_power = 20; 
	p_ship->p_next_enemy = p_enemies; 
	p_enemies = p_ship; 
	return p_ship; 
}

void upgradeWeapons (EnemySpaceShip *p_ship)
{
	p_ship->weapon_power += 10; 
} 

void deleteEnemy (EnemySpaceShip *p_enemy)
{
	delete p_enemy; 
}

int main () 
{ 
	EnemySpaceShip *p_enemy = getNewEnemy (); 
	cout << p_enemy->weapon_power << endl;

	p_enemy = getNewEnemy ();
	upgradeWeapons (p_enemy);
	cout << p_enemy->weapon_power << endl;

	p_enemy = getNewEnemy ();
	p_enemy->weapon_power = 40; 
	cout << p_enemy->weapon_power << endl;

	p_enemy = getNewEnemy ();
	p_enemy->weapon_power = 50; 
	cout << p_enemy->weapon_power << endl;

	p_enemy = getNewEnemy ();
	p_enemy->weapon_power = 60; 
	cout << p_enemy->weapon_power << endl;

	cout << endl;
	
	//traverse to the third node. 
	for (int i = 0; i < 2; i++)
	{
		p_enemies = p_enemies->p_next_enemy; 
	}

	cout << p_enemies->weapon_power; 

    return 0; 
}
coder777 (8444)
Those three steps are the way to remove a node from the singly linked list. You should use the term node instead of list since you have just one list with several nodes.

1
2
3
4
5
6
7
8
9
10
11
 
	EnemySpaceShip *prev_enemy = nullptr; // This will be the second node later
	//traverse to the third node. 
	for (int i = 0; i < 2; i++)
	{
		prev_enemy = p_enemies; // Keep this
		p_enemies = p_enemies->p_next_enemy; 
	}
	// Now prev_enemy is the second node and p_enemies the third
	prev_enemy->p_next_enemy = p_enemies->p_next_enemy; // This unlinks the third node -> The fourth node is now the next of the second node.
	delete p_enemies; // Since p_enemies is no longer in the list it can be safely deleted.
jhykima (125)
@coder777

Awesome! Thank you for the response. I will make sure to change my terminology. Now, how would I check if the node was actually deleted and the second and fourth nodes are now connected?

I would assume you would have to traverse back to the first node and then cout each node from there?
Last edited on
coder777 (8444)
I would assume you would have to traverse back to the first node and then cout each node from there?
No, within a singly linked list you cannot traverse back, only top down.

Hence you need to preserve the head of the list (p_enemies) when traversing the list:
1
2
3
4
5
6
 
	EnemySpaceShip *cur_enemy = p_enemies; // Note: don't modify p_enemies
	while(cur_enemy)
	{
		cout << ... enemy data ...
		cur_enemy = cur_enemy->p_next_enemy; 
	}


When deletiing the node you have to preserve the head as well (except when you delete the head of course)
jhykima (125)
@coder777

I see. Thank you so much for the help! Clarified a ton for me. Thank you!!!

Best regards,
Jae Kim
Topic archived. No new replies allowed.