Pointers Linked List

This code is from a example in Jumping Into C++ and I understand the example. But it is a practice problem that is to write a program to remove an element from a linked list; the remove function should take just the element to be removed.

Code:

---

#include <iostream>


using namespace std;


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


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 = NULL;
    return p_ship;
}


void updateShip(EnemySpaceShip *p_ship)
{
    p_ship->x_coordinate += 10;
    p_ship->y_coordinate += 10;
    p_ship->weapon_power += 20;


    cout << "X: " << p_ship->x_coordinate << endl;
    cout << "Y: " << p_ship->y_coordinate << endl;
    cout << "Weapon Power: " << p_ship->weapon_power << endl;
}


int main()
{
    EnemySpaceShip *getShip = getNewEnemy();
    updateShip(getShip);
    return 0;
}

---

If I got this right I will create a pointer that points to the first SHIP (getNewEnemy) and the other one will not be printed out.

The example doesn't actually create a linked list at all. It makes a single EnemySpaceShip, then calls updateShip on that single ship. The structure does have a next pointer which is set to NULL, but that in itself doesn't make it a linked list. The updateShip() function isn't going to magically follow the list and apply to other elements in the linked list. So if you're trying to make a remove() function, maybe you should first create an insert() function?... What exactly is your question?

I have seen the code example and I know that it isn't creating a linked list. But I have no idea of how to write a program that removes a element from a linked list. Is it any website or something exaplaining linked list. Or hints that somebody can give to help me? It is one of the practice problems in Jumping Into C++ and I want to do all of them so you really can understand how pointers work

The way to remove a singly linked list node is to point the previous node's next link to the node after the one you delete. If the remove function can only take a pointer to the node to delete, the linked list should be a doubly linked list. As a singly linked list, remove(node *removeMe) can't work: there is no way to access the previous node to the deleted node without a pointer to it.

Making the linked list doubly linked also makes the removal more complicated. You have to set the previous nodes next link to point to the next node, and the next node's prev link to point to the previous node. In exchange though, remove(node *removeMe) does work.

Once you reset the previous and next links, you can safely release the memory of the old node.

Quote:

---

Originally Posted by whiteflags

As a singly linked list, remove(node *removeMe) can't work: there is no way to access the previous node to the deleted node without a pointer to it.

---

Well, of course you can. You just have to search through the list from the beginning for the node whose next pointer equals the one to delete. Possible, but only in linear time, of course.

For many kind of problems, it often helps to look it visually. So draw an easy picture of the node to delete, and the node before and after it. Draw lines that connects the next/prev members (the links), so you can easily see what you must do. It might also help if you draw a picture of how it's supposed to look AFTER a node is deleted.

Elysia, may I direct you to reread the OP's post.

Quote:

---

Originally Posted by DecoratorFawn82

the remove function should take just the element to be removed.

---

An extra parameter, a pointer to the list, is not allowed, AFAICT.

It is unclear from the context if the function that removes an element would know the head of the list. In a traditional linked list, it would. In this example, I just don't know (I don't have access to the book and this doesn't exactly look like a linked list in any traditional sense).
If it's a traditional list, it's possible. If it doesn't have access to the head, then I am inclined to agree with you.

A common solution is to allow deleting from a singly lined list is to use a pointer to the element prior to the one you need as the iterator, instead of a pointer to the node itself. It's ugly, but it saves on the algorithmic complexity of iterating through the list to delete an element.