You are here:

C++/Creating a 'Y'-list from two std::list or std::forward_list objects


A colleague came across the frequently-asked C interview question "Imagine you have a singly-linked list L1 (of integers, for simplicity) with values 0 to 9. There is another singly-linked list L2 (again, of integers) with values 0 to 5. As expected, the next-pointers of the last nodes of both the lists point to NULL. Now, I modify the next-pointer of the last node of L2 to point to the 7th node of L1 (which has the integer 6 in it). We now have a 'Y' : two lists which merge into one. How would you find the node where the two lists merge?"

The problem is not difficult. However, my colleague came up with the question "How would one _create_ such a 'Y' from two std::list or two std::forward_list objects in C++?". The constraint is that one _must_ use the STL list/forward_list and other STL functions only. He can't figure it out and neither can I :-(

I agree that creating such a 'Y' would be inviting trouble but still, how would one do it if one wanted to? I tried to google for "combining/merging/joining multiple lists" but the usual answers (splice, std::move, etc) don't seem to help.

[UPDATE at end of original answer text]

TL;DR : Store pointers to the data objects in the list nodes rather than the data object values.

C++ standard library container types store data by value - that is they copy (or move or directly construct in C++11) objects that they store and the container then owns the (copied/moved/constructed) object.

Hence you cannot have the same object in two std::lists. You either have to make a copy from one list to the other or, since C++11 you have to move an object from one list to the other, invalidating the original (note: not all types are or should be movable).

Many other linked list implementations do not make copies of the object passed to the list for inclusion - they just store the object's pointer. You can probably see that with this type of list implementation you can easily create the 'Y' you were after.

Hence the way to replicate this using a std::list is to use a list of pointers to data objects: std::list<T*> rather than list<T>. However doing this using raw pointers leads to all sorts of problems. Firstly, std::list<> objects delete each node's object when the list is destroyed. However deleting a raw pointer does _not_ delete the object it points to so the list items need to be deleted manually before destroying the list. Secondly in this case as some nodes' data objects are going to be shared between lists - how do you know when to delete list items? Maybe a node is still used on one or more other lists.

Both problems can be taken care of by using a suitable smart pointer. In this case std::shared_pointer (for C++11 implementations) would be such a smart pointer type or std::tr1::shared_pointer for mid-naughties implementations or look at boost::shared_pointer if neither of the others two are available. In fact you should use the associated make_shared function to create objects referred to by a shared_pointer. You might wish to look up further information on smart pointers, such as:

A shared_pointer will keep a count of references to the pointer it manages, or rather the object it manages via its pointer. When the reference count goes to zero the object is deleted.

This solves both the problems mentioned above with std::list<T*>. A std::list<std::shared_pointer<T>> (or equivalent earlier/alternative of std::shared_pointer) will not require us to manually delete the object in the list and each shared pointer knows how many lists - and possibly other things - are referring to the pointed to object and will delete that object only when there is nothing left to refer to it.

Hope this helps.

It occurred to me a while after I posted my answer (and sorry some life stuff distracted me from getting this update out sooner!) that I did not make it clear that although using (smart) pointers will allow you to create a sort of Y-shaped effect you cannot do exactly as I think the question you were querying about implied as std::list (and in C++11 and later std::forward_list - a singly linked list type) will not let you mess around with their node data (i.e. the link pointers)* in the way the question was asking about. You will still have two distinct lists with distinct nodes, with nodes at the end of each list that just happen to have node-data that refers (points to) the same data. You can still manipulate the two lists separately so that the Y shape no longer exists or is changed.


* OK you could work out the node structure of a specific std::list implementation and do all sorts of under handed things to mess with a list's nodes - C++ only helps protect you from mistakes not malice!  


All Answers

Answers by Expert:

Ask Experts


Ralph McArdell


I am a software developer with more than 15 years C++ experience and over 25 years experience developing a wide variety of applications for Windows NT/2000/XP, UNIX, Linux and other platforms. I can help with basic to advanced C++, C (although I do not write just-C much if at all these days so maybe ask in the C section about purely C matters), software development and many platform specific and system development problems.


My career started in the mid 1980s working as a batch process operator for the now defunct Inner London Education Authority, working on Prime mini computers. I then moved into the role of Programmer / Analyst, also on the Primes, then into technical support and finally into the micro computing section, using a variety of 16 and 8 bit machines. Following the demise of the ILEA I worked for a small company, now gone, called Hodos. I worked on a part task train simulator using C and the Intel DVI (Digital Video Interactive) - the hardware based predecessor to Indeo. Other projects included a CGI based train simulator (different goals to the first), and various other projects in C and Visual Basic (er, version 1 that is). When Hodos went into receivership I went freelance and finally managed to start working in C++. I initially had contracts working on train simulators (surprise) and multimedia - I worked on many of the Dorling Kindersley CD-ROM titles and wrote the screensaver games for the Wallace and Gromit Cracking Animator CD. My more recent contracts have been more traditionally IT based, working predominately in C++ on MS Windows NT, 2000. XP, Linux and UN*X. These projects have had wide ranging additional skill sets including system analysis and design, databases and SQL in various guises, C#, client server and remoting, cross porting applications between platforms and various client development processes. I have an interest in the development of the C++ core language and libraries and try to keep up with at least some of the papers on the ISO C++ Standard Committee site at


©2017 All rights reserved.