merge linked list

Collapse
X
 
  • Time
  • Show
Clear All
new posts
  • mithuncm
    New Member
    • Oct 2008
    • 5

    merge linked list

    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
    Recognized Expert MVP
    • Mar 2007
    • 11453

    #2
    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

    Comment

    • weaknessforcats
      Recognized Expert Expert
      • Mar 2007
      • 9214

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

      Comment

      • Ganon11
        Recognized Expert Specialist
        • Oct 2006
        • 3651

        #4
        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.

        Comment

        • mithuncm
          New Member
          • Oct 2008
          • 5

          #5
          Originally posted by 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.

          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

          Comment

          • vmpstr
            New Member
            • Nov 2008
            • 63

            #6
            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.

            Comment

            Working...