Jump to content
  • Advertisement
Sign in to follow this  
adam23

Question about Linked Lists

This topic is 4339 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I am working on a project, where I believe adding items to a linked list will be the most efficient. What I am planning on doing is creating items on the free store and then adding them to the Linked List. For example LinkedList<Asteroids> *m_roids; m_roids = new LinkedList<Asteroids>; Asteroids *small = new Asteroids(SMALL); m_roids->Add(small); Now in the Linked List I have a function Empty.
	void Empty()
	{
		while( m_last != NULL )
		{
			m_temp = m_last;
			m_last = m_last->prev;
			if(m_temp != NULL) delete m_temp;
		}
		m_first = m_last = m_iterate = m_temp = NULL;
		m_totalElements = 0;
	}

As long as when I get done with the list I call the Empty function will this take care of restoring all of the memory, or do I need to keep track of all of the objects I have added to the list and destroy them separately? Thanks in advance.

Share this post


Link to post
Share on other sites
Advertisement
Without knowing more about your linked list implementation it's impossible to say.

However, you should consider using std::list<> and not worrying about the linked list implementation.

Share this post


Link to post
Share on other sites
If I used the std::list would that remove me from having to worry about information that I created on the free store. Would I be better off not creating memory on the free store and just create it like this.

Asteroid small(SMALL);

m_roids->Add(small);

I may do it this way so I don't have to worry about memory leaks. Then all I have to do is destroy my list.

Share this post


Link to post
Share on other sites
In your linked list are you storing objects or pointers to objects? Take a look at how the C++ Standard Library does it. std::list<Asteroids> for example would deallocate all the memory, but std::list<Asteroids*> would only deallocate memory taken up by pointers, not Asteroids objects.

std::list::push_back() inserts a copy of an object not the actual object. You may find it useful in your LinkedList design. Also, is there a particular reason why you are using a custom LinkedList class and not the std::list?

Share this post


Link to post
Share on other sites
Quote:
Original post by adam23
If I used the std::list would that remove me from having to worry about information that I created on the free store.


No, std::list<Object*> doesn't help you with deallocation. You will have to go through and manually delete each object yourself.

Quote:
Original post by adam23
Would I be better off not creating memory on the free store and just create it like this.

Asteroid small(SMALL);

m_roids->Add(small);

I may do it this way so I don't have to worry about memory leaks. Then all I have to do is destroy my list.


This will work only if your LinkedList is storing a copy of the original object. If it's storing a reference, then you are in trouble. What happens when small gets out of scope?

EDIT: Try boost::ptr_list. It's a linked list container designed to hold pointers. It deallocates memory automatically.

Share this post


Link to post
Share on other sites
Quote:
Original post by adam23
If I used the std::list would that remove me from having to worry about information that I created on the free store. Would I be better off not creating memory on the free store and just create it like this.

Asteroid small(SMALL);

m_roids->Add(small);

I may do it this way so I don't have to worry about memory leaks. Then all I have to do is destroy my list.


Use the std::list, in this manner. You will have no memory management work to do. This basically only fails to work when you have a polymorphic Asteroid and need to store subclasses (then you do need a std::list of some kinds of pointers or handles, and will need to do the appropriate memory management; however, wrappers exist to simplify the process, and you can make a very simple wrapper too if the "ownership" policy is straightforward), or when Asteroid objects are expensive to copy. But yes, the std container classes are really designed for use with instances rather than pointers.

Share this post


Link to post
Share on other sites
Well, doing asteroid_list.push_back(Asteroid(SMALL)) would be more likely to optimize away the temporary, but either way, as long as the std::list is parameterized with the Asteroid type, the std::list<Asteroid> will keep track of all the relevant memory for you.

Share this post


Link to post
Share on other sites
Quote:
Original post by Zahlman
Use the std::list, in this manner. You will have no memory management work to do. This basically only fails to work when you have a polymorphic Asteroid and need to store subclasses (then you do need a std::list of some kinds of pointers or handles, and will need to do the appropriate memory management; however, wrappers exist to simplify the process, and you can make a very simple wrapper too if the "ownership" policy is straightforward), or when Asteroid objects are expensive to copy. But yes, the std container classes are really designed for use with instances rather than pointers.



Thank you, this really answers my question. I will use std::list instead of my LinkedList and see how that goes. My goal is if one big asteroid is hit, I'll add 3 medium in its place (each with a different direction). Then if a medium asteroid is hit, the medium will be removed and two small ones will be added. I am going to sit down tomorrow and start working on the UML design.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!