Adding a pointer to the end of a linked list

So I've been getting back into programming, making sure I get everything covered, but there's one problem that I have NEVER been able to figure out. I've been reading 'Beginning c++ through game programming' and on chapter 9 it has this following exercise which I haven't been able to figure out, nor have I found any clear info on.

The Lobby::AddPlayer() member function from the Game Lobby program is inefficient because it iterates through all of the player nodes to add a new player to the end of the line. Add an m_pTail pointer data member to the Lobby class that always points to the last player node in the line and use it to more efficiently add a player.

The code is here.

Code:

#include <iostream>
#include <string>

using namespace std;

class Player
{
public:
    Player(const string& name = "");
    string GetName() const;
    Player* GetNext() const;
    void SetNext(Player* next);

private:
    string m_Name;
    Player* m_pNext; // Pointer to next player in list
};

Player::Player(const string& name):
    m_Name(name),
    m_pNext(0)
{}

string Player::GetName() const
{
    return m_Name;
}

Player* Player::GetNext() const
{
    return m_pNext;
}

void Player::SetNext(Player* next)
{
    m_pNext = next;
}

class Lobby
{
    friend ostream& operator<<(ostream& os, const Lobby& aLobby);

public:
    Lobby();
    ~Lobby();
    void AddPlayer();
    void RemovePlayer();
    void Clear();

private:
    Player* m_pHead;
    Player* m_pTail;

};

Lobby::Lobby():
    m_pHead(0),
    m_pTail(0)
{}

Lobby::~Lobby()
{
    Clear();
}

void Lobby::AddPlayer()
{
    //create a new player node
    cout << "Please enter the name of the new player: ";
    string name;
    cin >> name;
    Player* pNewPlayer = new Player(name);

    //if list is empty make head of list this new player
    if (m_pHead == 0)
    {
        m_pHead = pNewPlayer;
    }

    //otherwise find the end of the list and add the player there
    else
    {
        Player* pIter = m_pHead;
        while (pIter->GetNext() != 0)
        {
            pIter = pIter->GetNext();
        }
        pIter->SetNext(pNewPlayer);
    }
}

void Lobby::RemovePlayer()
{
    if (m_pHead == 0)
    {
        cout << "The game lobby is empty.   No one to remove!\n";
    }
    else
    {
        Player* pTemp = m_pHead;
        m_pHead = m_pHead->GetNext();
        delete pTemp;
    }
}

void Lobby::Clear()
{
    while (m_pHead != 0)
    {
        RemovePlayer();
    }
}

ostream& operator<<(ostream& os, const Lobby& aLobby)
{
    Player* pIter = aLobby.m_pHead;

    os << "\nHere's who's in the game lobby:\n";
    if (pIter == 0)
    {
        os << "The lobby is empty.\n";
    }
    else
    {
        while (pIter != 0)
        {
            os << pIter->GetName() << endl;
            pIter = pIter->GetNext();
        }
    }

    return os;
}

int main()
{
    Lobby myLobby;
    int choice;

    do
    {
        cout << myLobby;
        cout << "\nGAME LOBBY\n";
        cout << "0 - Exit the program.\n";
        cout << "1 - Add a player to the lobby.\n";
        cout << "2 - Remove a player from the lobby.\n";
        cout << "3 - Clear the lobby.\n";
        cout << endl << "Enter choice: ";
        cin >> choice;

        switch (choice)
        {
            case 0: cout << "Good-bye.\n"; break;
            case 1: myLobby.AddPlayer(); break;
            case 2: myLobby.RemovePlayer(); break;
            case 3: myLobby.Clear(); break;
            default: cout << "That was not a valid choice.\n";
        }
    }
    while (choice != 0);

    return 0;
}

Anything you can tell me that could help me in the right direction (I've only added in the m_pTail variable).

Where is your attempt, and what is your question?

Have you considered that you will then also need to update the RemovePlayer function for the case when you delete the last item?

Originally Posted by iMalc

Where is your attempt, and what is your question?

Have you considered that you will then also need to update the RemovePlayer function for the case when you delete the last item?

I've not attempted, because, honestly, I don't know where to begin. FYI, it's not homework, I'm self-teaching. If I could know how to actually implement it in this specific program, it would be very helpful.

Also, yes to your second question. As this code only allows me to remove a player from the front of the list, and not from the end, but like I said.. I have no idea of even where to start besides just adding in the "m_pTail" pointer.

I've figured it out through painstakingly going through how the program itself works in the memory (keeping track of it in my mind I should add...). The biggest thing I had trouble with were the functions "GetNext()" and "SetNext()". Those functions, for some reason, were just a bit off-putting, (probably because of the order they were put in... just threw me off for a loop, no pun intended). It seems so simple now! SetNext's function was to assign the address of the newly created object into the m_pNext data member function, GetNext's function was to return the address value of m_pNext. After figuring that out I came up with this.

Code:

void Lobby::AddPlayer()
{
    //create a new player node
    cout << "Please enter the name of the new player: ";
    string name;
    cin >> name;
    Player* pNewPlayer = new Player(name);

    //if list is empty make head of list this new player
    if (m_pHead == 0)
    {
        m_pHead = pNewPlayer; // Assigns the first instance's address to the m_pHead data member
        m_pTail = m_pHead; // Assigns the first m_pTail to the address of the first instance's address
    }

    //otherwise find the end of the list and add the player there
    else
    {
        m_pTail->SetNext(pNewPlayer); // Since m_pTail was assigned to be the first instance's address, m_pTail can call the Player class' member functions
                                      // Assigns the new object's address to the prior object's m_pNext data member
        m_pTail = m_pTail->GetNext(); // Assigns m_pTail to the address of the new object's m_pNext's data member
    }
}

After figuring this out (the extra comments were typed in by me to remember the steps), and seeing if it would work and found that it did, I was surprised a little. I thought that using a member function outside of its class wasn't allowed. m_pTail is from the Lobby class, but when I did m_pTail->SetNext(pNewPlayer), I guess it's because m_pTail was assigned to m_pHead in the first created instance. ... After typing that out it seems to make sense now. A lot to keep track of, plus I now know more about the use of those kinds of assignments. Just another roadblock in my mind that set me back.

Edit: Edited my comments on the new added code above to reflect my new understanding. It really doesn't seem very intuitive in the slightest... :-/

Well done. :)

Originally Posted by Darkroman

I thought that using a member function outside of its class wasn't allowed.

Using a private member function generally isn't allowed. `GetNext()` and `SetNext()` are in the public section of the Player class, so it's perfectly fine.

Originally Posted by Darkroman

Edited my comments on the new added code above to reflect my new understanding. It really doesn't seem very intuitive in the slightest... :-/

Your expectations of yourself might be unreasonable. Understanding comes with time and use. Epiphanies are rare. :)

Originally Posted by Darkroman

Also, yes to your second question. As this code only allows me to remove a player from the front of the list, and not from the end, but like I said.. I have no idea of even where to start besides just adding in the "m_pTail" pointer.

Well first I have to say - well done. It's always more satisfying when you figure things out on your own.

Also, we're sort of both right about the need to change RemovePlayer. You're right in that it wont currently have any ill-efect considering the rest of the program as it currently stands. However, initialliy m_pHead and m_pTail are both NULL, then say you call AddPlayer once and then RemovePlayer once.
What values do those member variables have now?...
m_pHead is NULL, but m_pTail is not. This could very easily lead to a bug later on as you make further changes.

Originally Posted by iMalc

Well first I have to say - well done. It's always more satisfying when you figure things out on your own.

Also, we're sort of both right about the need to change RemovePlayer. You're right in that it wont currently have any ill-efect considering the rest of the program as it currently stands. However, initialliy m_pHead and m_pTail are both NULL, then say you call AddPlayer once and then RemovePlayer once.
What values do those member variables have now?...
m_pHead is NULL, but m_pTail is not. This could very easily lead to a bug later on as you make further changes.

I've done it, and more. I added the option of deleting it from either the head of the list, or the tail (depending on user choice). It may be a little ugly, but suffice to say, it works. Players get added, and deleted properly and allocate correctly. I pretty much figured this out on my own. It was an awesome brain exercise for me, and I feel like I'm a lot more comfortable with pointers than I have ever been. But again, there might be some mistakes in there, just let me know of anything I could improve upon.

Player Class:

Code:

class Player
{
public:
    Player(const string& name = "");
    string GetName() const;
    Player* GetNext() const;
    void SetNext(Player* next);
    Player* GetPrev() const;
    void SetPrev(Player* prev);

private:
    string m_Name;
    Player* m_pNext; // Pointer to next player in list
    Player* m_pPrev; // Pointer to previous player in list
};

Player::Player(const string& name):
    m_Name(name),
    m_pNext(0),
    m_pPrev(0)
{}

string Player::GetName() const
{
    return m_Name;
}

Player* Player::GetNext() const
{
    return m_pNext;
}

void Player::SetNext(Player* next)
{
    m_pNext = next;
}

Player* Player::GetPrev() const
{
    return m_pPrev;
}

void Player::SetPrev(Player* prev)
{
    m_pPrev = prev;
}

Lobby Class:

Code:

class Lobby
{
    friend ostream& operator<<(ostream& os, const Lobby& aLobby);

public:
    Lobby();
    ~Lobby();
    void AddPlayer();
    void RemovePlayer();
    void Clear();

private:
    Player* m_pHead;
    Player* m_pTail;
    Player* m_pCurrent;

};

Lobby::Lobby():
    m_pHead(0),
    m_pTail(0),
    m_pCurrent(0)
{}

Lobby::~Lobby()
{
    Clear();
}

void Lobby::AddPlayer()
{
    //create a new player node
    cout << "Please enter the name of the new player: ";
    string name;
    cin >> name;
    Player* pNewPlayer = new Player(name);

    //if list is empty make head of list this new player
    if (m_pHead == 0)
    {
        m_pHead = pNewPlayer;
        m_pTail = m_pHead;
    }

    //otherwise find the end of the list and add the player there
    else
    {
        m_pTail->SetPrev(m_pCurrent);
        m_pTail->SetNext(pNewPlayer);
        m_pCurrent = m_pTail;
        m_pTail = m_pTail->GetNext();
        m_pTail->SetPrev(m_pCurrent);
    }
}

void Lobby::RemovePlayer()
{
    int choice;

    cout << "Select from which position you'd like to delete\n";
    cout << "0 - Cancel\n";
    cout << "1 - From the Bottom\n";
    cout << "2 - From the Top\n";
    cout << endl << "Enter choice: ";
    cin >> choice;


    switch (choice)
    {
        if (m_pHead == 0)
        {
            cout << "The game lobby is empty.   No one to remove!\n";
        }

        else
        {
            case 0:
                cout << "Cancelling Request.\n";
            break;

            case 1:
                if ( (m_pTail == m_pHead) )
                {
                    delete m_pTail;
                    m_pCurrent = 0;
                    m_pHead = 0;
                    m_pTail = 0;
                }

                else
                {
                    Player* pTemp = m_pTail;
                    m_pTail = m_pCurrent;
                    m_pCurrent = m_pCurrent->GetPrev();
                    delete pTemp;
                }

            break;

            case 2:
                if ( (m_pTail == m_pHead) )
                {
                    delete m_pTail;
                    m_pCurrent = 0;
                    m_pHead = 0;
                    m_pTail = 0;
                }

                else
                {
                    Player* pTemp = m_pHead;
                    m_pHead = m_pHead->GetNext();
                    delete pTemp;
                }
        }

            break;

            default:
                cout << "That is not a valid choice!" << endl;
    }
}

void Lobby::Clear()
{
    while (m_pHead != 0)
    {
        if ( (m_pTail == m_pHead) )
        {
            delete m_pTail;
            m_pCurrent = 0;
            m_pHead = 0;
            m_pTail = 0;
        }

        else
        {
            Player* pTemp = m_pHead;
            m_pHead = m_pHead->GetNext();
            delete pTemp;
        }
    }
}

ostream& operator<<(ostream& os, const Lobby& aLobby)
{
    Player* pIter = aLobby.m_pHead;

    os << "\nHere's who's in the game lobby:\n";
    if (pIter == 0)
    {
        os << "The lobby is empty.\n";
    }
    else
    {
        while (pIter != aLobby.m_pTail->GetNext())
        {
            os << pIter->GetName() << endl;
            pIter = pIter->GetNext();
        }
    }

    return os;
}

Main:

Code:

int main()
{
    Lobby myLobby;
    int choice;

    do
    {
        cout << myLobby;
        cout << "\nGAME LOBBY\n";
        cout << "0 - Exit the program.\n";
        cout << "1 - Add a player to the lobby.\n";
        cout << "2 - Remove a player from the lobby.\n";
        cout << "3 - Clear the lobby.\n";
        cout << endl << "Enter choice: ";
        cin >> choice;

        switch (choice)
        {
            case 0: cout << "Good-bye.\n"; break;
            case 1: myLobby.AddPlayer(); break;
            case 2: myLobby.RemovePlayer(); break;
            case 3: myLobby.Clear(); break;
            default: cout << "That was not a valid choice.\n";
        }
    }
    while (choice != 0);

    return 0;
}

Also, I'm aware of stl::list and I'm also aware that the program is not a true linked list. Once I get into more advanced template class creation, I'll try my hand at it.