Adding a pointer to the end of a linked list

This is a discussion on Adding a pointer to the end of a linked list within the C++ Programming forums, part of the General Programming Boards category; So I've been getting back into programming, making sure I get everything covered, but there's one problem that I have ...

  1. #1
    Registered User
    Join Date
    Aug 2011
    Posts
    35

    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).

  2. #2
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,293
    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?
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  3. #3
    Registered User
    Join Date
    Aug 2011
    Posts
    35
    Quote Originally Posted by iMalc View Post
    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.

  4. #4
    Registered User
    Join Date
    Aug 2011
    Posts
    35
    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... :-/
    Last edited by Darkroman; 02-03-2013 at 01:44 AM.

  5. #5
    msh
    msh is offline
    Novice
    Join Date
    Jul 2009
    Posts
    568
    Well done. :)

    Quote Originally Posted by Darkroman View Post
    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.

    Quote 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. :)
    Disclaimer: This post shows my ignorance at the time of its making. I claim ownership of but not responsibility for all errors in it. Reference at your own peril.

  6. #6
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,293
    Quote Originally Posted by Darkroman View Post
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  7. #7
    Registered User
    Join Date
    Aug 2011
    Posts
    35
    Quote Originally Posted by iMalc View Post
    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.
    Last edited by Darkroman; 02-06-2013 at 08:48 AM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. adding to linked list
    By camel-man in forum C Programming
    Replies: 15
    Last Post: 10-09-2011, 02:13 PM
  2. Adding a node to linked list
    By laurenlb in forum C Programming
    Replies: 1
    Last Post: 04-14-2011, 07:05 PM
  3. help with adding item to linked list in C
    By omega666 in forum C Programming
    Replies: 6
    Last Post: 04-04-2011, 09:46 PM
  4. Adding nodes to a linked list
    By bluescreen in forum C Programming
    Replies: 4
    Last Post: 11-09-2006, 12:59 AM
  5. Adding a node to a linked list
    By slopeski007 in forum C Programming
    Replies: 2
    Last Post: 02-01-2003, 11:31 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21