merge linked list

[mithuncm]

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?

[JosAH]

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

[weaknessforcats]

It does help on a merge if each list is already sorted. Unless you do that, the merge cuold get very complicated.

[Ganon11]

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.

[mithuncm]

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.

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

[vmpstr]

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.