Jump to content
  • Advertisement
Sign in to follow this  

linking linked lists together

This topic is 3583 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

Sorry, I couldn't think of a better way of wording the title... Let's say I've got 2 linked lists, called list1 and list2, and I want to create another list called masterList which is basically a combination of the two lists, and I want to do it without incurring the overhead of copying the elements across one by one. So, I want to do something like this (pseudocode - assume that list1 and list2 have already been set up with stuff):
masterList->firstElement = list1->firstElement;
masterList->lastElement = list2->firstElement;
With the intention that I should be able to iterate through masterList, starting with the first element, and have it go through all the values stored in list1, then list2, before hitting the NULL terminator. 1 - Is there a way to do this with an std::list in C++? I've been going through the documentation and examples, and I can't find an example of how to hook lists together like this with the STL containers. 2 - Presumably if this is possible using std::list, a side-effect will be that if I later go to iterate through list1, it'll end up iterating through list2 as well, list masterList does? If I want to avoid this, what's the best way? I presume it's to store a pointer to the last element of list1, and set its next pointer back to NULL once I've finished using masterList, but I might be barking up the wrong tree here...

Share this post

Link to post
Share on other sites
I don't see how insert could hook two lists together by setting the pointers. The only way I can see of using insert would be to iterate through all of the elements in list1 and insert them into masterList, and then iterate through list2 and insert those into masterList as well. Whilst this would work, it involves copying values from one list into another one by one, which is the thing I'm trying to avoid.

I suppose what I'm really asking is whether or not there's a way to explicitly get the "next" pointer of an element in one std::list to point at an element in a different list, or whether messing about with pointers in an std::list can only be done implicitly by using insert, erase, remove, or push_/pop_ back/front.

I'm looking for something like merge (http://www.cplusplus.com/reference/stl/list/merge.html) but which doesn't empty out the "source" list, just amends the last pointer of the "target" list to point at the beginning of the "source" list. If that makes sense... :s

EDIT: Just saw your link to splice - again, it's close, but it removes the contents of the list that's being spliced in.

Share this post

Link to post
Share on other sites
You need to write custom iterator, which iterates over first list, when it reaches the end it continues to iterate over the second.

It's fairly trivial, quite simple even for arbitrary number of lists, but requires some verbose typedefs which I'm not currently in the mood for.

Share this post

Link to post
Share on other sites
You could splice the contents of one into the other then once operations are complete splice it back, its a bit quick and dirty though.

I have no development PC at the moment so I can't really do any code.

std::list<int> list1;
std::list<int> list2;

//create lists....

list<int>::iterator it = list1.end();

//move all of list2 to the end of list one
list1.splice( list1.end(),list2 )

// do operations on list1...

//move all the elements from the orignal end of list1 back to list2.
//need to check that this inserts at the start and not one after the start, I am unsure
list2.splice( list2.begin(),list1, it, list1.end() )

Remember I have no compiler so its hard for me to proof it :|

I am unfamiliar with custom iterators maybe its the way to go.

[Edited by - Guthur on January 22, 2009 8:53:45 PM]

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.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!