By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
440,117 Members | 2,178 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 440,117 IT Pros & Developers. It's quick & easy.

merge linked list

mithuncm
P: 5
hai all,
any one, can you say how to merge two different linked list. I have 2 linked list where datas, & of corresponding time that datas send. I have to sort out datas according to time, to a single linked list. Do you have any idea?
Nov 25 '08 #1
Share this Question
Share on Google+
5 Replies


Expert 10K+
P: 11,448
You have to be able to compare two elements (each in its own list) and move the first element of a list to another list.

kind regards,

Jos
Nov 25 '08 #2

weaknessforcats
Expert Mod 5K+
P: 9,197
It does help on a merge if each list is already sorted. Unless you do that, the merge cuold get very complicated.
Nov 25 '08 #3

Ganon11
Expert 2.5K+
P: 3,652
You could always be lazy and merge the lists first, then sort it (such a merging would be as simple as pointing the tail of one list to the head of the other list), but weaknessforcats is right: keeping each list sorted internally will make the merging much easier to do while keeping the lists sorted.
Nov 25 '08 #4

mithuncm
P: 5
@Ganon11

i had already used 3 linked list 1st for gathering all scattered data read from 500 mB .cap file , 2nd sorted according to IP and port , acknowledgment is checked and sorted to 3 rd one.. ..
2 & 3 linked list are sorted and done to a single one as 4th linked list..
according to time of data received but the problem is iteration of the linked list .. the application become slower and slower.
if i can merge it to 2nd or 3 rd it will keep much more speed , i hve also tried thread. Do you have any idea or any doc or books to reffer?
else my problem is solved.
thank you all
Nov 26 '08 #5

P: 63
You can just keep the first linked list sorted, and insert items into the correct positions according to ordering. I mean, it is still a fairly slow operation. You can try using a balanced binary tree to insert things, that should speed things up a bit. In the end, because of the size of your data, it will still be fairly slow.

A good reference for more advanced data structures like red-black trees is
Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein (clrs)

If you just want the code, then I know that there is
Algorithms in C by Robert Sedgewick... there's probably a C++ version, but I'm not sure.
Nov 26 '08 #6

Post your reply

Sign in to post your reply or Sign up for a free account.