This discussion is archived
1 2 Previous Next 16 Replies Latest reply: Oct 1, 2010 10:51 AM by 796440 RSS

Merge one LinkedList into one other at a specified position

Alessandro Rossi Journeyer
Currently Being Moderated
Hi everyone

I'm facing with a quite simple problem regarding LinkedList Class, but it seems that the features I need to solve it are hidden.

We know that a LinkedList is a Collection that stores element in a recursive structure composed by: a reference to the contained element, a reference to the structure that stores the next element and a reference for the structure that stores the preceding element.

The task I'd like to accomplish is quite simple: I have two LinkedList listA and listB and I want to include/merge listB into listA at a specified position with a method that could capitalize the fact that this operation can be done with a manipulation on the references for the next and preceding elements of the two lists without having to explicitly add all the elements of listB one at the time, that would be very inefficient for the reason at every insertion it loses time to find the element where to append the elements and to manipulate the references of the involved elements.

Thank you
Bye Alessandro
  • 1. Re: Merge one LinkedList into one other at a specified position
    Kayaman Guru
    Currently Being Moderated
    Check out if ListIterator has what you need.
  • 2. Re: Merge one LinkedList into one other at a specified position
    Alessandro Rossi Journeyer
    Currently Being Moderated
    Kayaman wrote:
    Check out if ListIterator has what you need.
    No, there's nothing there. I'm quite sure that this feature, that is theoretically possible, is not accessible by the public methods of LinkedList and correlated classes.
  • 3. Re: Merge one LinkedList into one other at a specified position
    Kayaman Guru
    Currently Being Moderated
    Are the lists sorted?

    I'd imagine a merge operation would work just fine with the ListIterator...just add() the required new elements while iterating both lists.

    Edited by: Kayaman on Sep 30, 2010 3:28 PM
  • 4. Re: Merge one LinkedList into one other at a specified position
    johndjr Newbie
    Currently Being Moderated
    Perhaps List.addAll() will do that.

    You would have to check the source code to know how it is implemented. It seems reasonable that it might do the addition in the manner in which you desire. (I've only thought about this for about 2 seconds so maybe it is not so reasonable).

    But I have to wonder why the implementation matters to you.
    Either it does what you need while using an acceptable level of reasources or it does not.
  • 5. Re: Merge one LinkedList into one other at a specified position
    Alessandro Rossi Journeyer
    Currently Being Moderated
    johndjr wrote:
    Perhaps List.addAll() will do that.
    Not in an efficient way, this is the source.

        public boolean addAll(int index, Collection<? extends E> c) {
            if (index < 0 || index > size)
                throw new IndexOutOfBoundsException("Index: "+index+
                                                    ", Size: "+size);
            Object[] a = c.toArray();
            int numNew = a.length;
            if (numNew==0)
                return false;
         modCount++;
    
            Entry<E> successor = (index==size ? header : entry(index));
            Entry<E> predecessor = successor.previous;
         for (int i=0; i<numNew; i++) {
                Entry<E> e = new Entry<E>((E)a, successor, predecessor);
    predecessor.next = e;
    predecessor = e;
    }
    successor.previous = predecessor;

    size += numNew;
    return true;
    }
    Edited by: Alessandro Rossi on 30-set-2010 15.10                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    
  • 6. Re: Merge one LinkedList into one other at a specified position
    johndjr Newbie
    Currently Being Moderated
    Alessandro Rossi wrote:
    johndjr wrote:
    Perhaps List.addAll() will do that.
    Not in an efficient way, this is the source.

    If I had thought about it for more than the aforementioned 2 seconds I might have realized that addAll() takes a Collection not a LinkedList, so it was not going to be splicing the new elements into "this".

    It the LinkedList implemenation really going to be a problem? It may not be.

    If it is, I guess you will have to extend LinkedList and add a splice(), or whatever, method.
  • 7. Re: Merge one LinkedList into one other at a specified position
    Alessandro Rossi Journeyer
    Currently Being Moderated
    If I had thought about it for more than the aforementioned 2 seconds I might have realized that addAll() takes a Collection not a LinkedList, so it was not going to be splicing the new elements into "this".
    If they wanted to handle it in that way they could use instanceof operator in the code.
    If it is, I guess you will have to extend LinkedList and add a splice(), or whatever, method.
    Now I pasted a modified version of LinkedList offering as method with such capability in the package where I need it. ...It seems the work!

        public boolean includeAt(int index, LinkedList<E> listb) {
             if (index < 0 || index > size) {
                  throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
             }
             Entry<E> successor = (index==size ? header : entry(index));
             Entry<E> predecessor = successor.previous;
    
             Entry<E> first = listb.header.next;
             Entry<E> last = listb.header.previous;
              
              predecessor.next = first;
              first.previous = predecessor;
              last.next = successor;
              successor.previous = last;
              size += listb.size;
            return true; 
        }
    I suppose that the main reason that pushed them to hide this capability regards the incoherency of listB after the operation.

    Edited by: Alessandro Rossi on 30-set-2010 16.58
  • 8. Re: Merge one LinkedList into one other at a specified position
    796440 Guru
    Currently Being Moderated
    Alessandro Rossi wrote:
    johndjr wrote:
    Perhaps List.addAll() will do that.
    Not in an efficient way, this is the source.
    How is that inefficient?

    If you have {a, b, c, d, e, f} and {W, X, Y , Z}, and you want to insert the second list into the first so that you get {a, b, c, W, X, Y, Z, d, e, f} then just repeatedly call the add method on the first list that takes an index while iterating over the second list.

    If you're thinking of something that will just manipulate the next and prev pointers on c, W, Z, and d, then no, there is no such method, as you can plainly see when you look at LinikedList's docs. Thank goodness.
  • 9. Re: Merge one LinkedList into one other at a specified position
    Kayaman Guru
    Currently Being Moderated
    Alessandro Rossi wrote:
    Now I pasted a modified version of LinkedList offering as method with such capability in the package where I need it. ...It seems the work!
    Was it worth it? How big are your lists?
  • 10. Re: Merge one LinkedList into one other at a specified position
    Alessandro Rossi Journeyer
    Currently Being Moderated
    jverd wrote:
    Alessandro Rossi wrote:
    johndjr wrote:
    Perhaps List.addAll() will do that.
    Not in an efficient way, this is the source.
    How is that inefficient?
    Don't you see it?

    I was not looking for a copy but for a sort of merge or however we want to call it!

    And it is inefficient (not wrong, just inefficient) in the same way as it is inefficient the way to move a file into a directory of the same file system copying all its bytes to a new location and then erase the old data instead of just changing some references on the file-system structures.

    That method is inefficient (for my task, not yours) because it performs a loop over all the elements of listB allocating useless memory. All that is not necessary when listB is not accessed anymore because it makes an useless duplicate.

    Having the chance to perform that task within a fixed time that doesn't completely depend on the size of the involved entities is a good thing in my opinion.
    If you have {a, b, c, d, e, f} and {W, X, Y , Z}, and you want to insert the second list into the first so that you get {a, b, c, W, X, Y, Z, d, e, f} then just repeatedly call the add method on the first list that takes an index while iterating over the second list.
    First of all that functionality is a native characteristic of any Linked List. If I wanted to do using C# or C++ STL or many other languages there were no problems.

    Having a class representing a data structure that doesn't offer some of its native functionality is strange in my opinion. I was surprised about it and then I wanted to ask if it was really like it seemed to me. After that I just wanted to see deeply how it was designed.

    If you're thinking of something that will just manipulate the next and prev pointers on c, W, Z, and d, then no, there is no such method, as you can plainly see when you look at LinikedList's docs.
    The documentation is really big, and probably the things we're looking for could be somewhere else. For example I know of some methods like the sort method working on LinkedList and the other classes implementing Collection not described in the LinkedList documentation and not even in the Collection page, but that are available from the Collections class.

    Thank goodness.
    I think that posts like yours are made just to start useless (ugly) discussions. It would nice, for somebody who doesn't have anything useful to say, to don't post anything.
  • 11. Re: Merge one LinkedList into one other at a specified position
    DrClap Expert
    Currently Being Moderated
    If there was a method in LinkedList which allowed other people's code to go and mess with the internal pointers, there would be a good chance that the other people's code would break the list in various ugly ways. So therefore, LinkedList being a well-designed library class, there isn't any such method.

    If this efficiency issue of yours is a real issue (i.e. it affects the run time of the code in a significant way as opposed to the strictly theoretical concern which is all I have seen so far) then I would advise writing your own implementation of List which does allow other people's code to hack around with the pointers.
  • 12. Re: Merge one LinkedList into one other at a specified position
    796440 Guru
    Currently Being Moderated
    Alessandro Rossi wrote:
    jverd wrote:
    Alessandro Rossi wrote:
    johndjr wrote:
    Perhaps List.addAll() will do that.
    Not in an efficient way, this is the source.
    How is that inefficient?
    Don't you see it?
    Don't you see that "inefficient" by itself means nothing? It's an O(N) operation. In and of itself it is neither efficient nor inefficient. Now, if you had said, "I tried it and found it to be an unacceptable bottleneck," that would be a different story.
    I was not looking for a copy but for a sort of merge or however we want to call it!

    And it is inefficient (not wrong, just inefficient) in the same way as it is inefficient the way to move a file into a directory of the same file system copying all its bytes to a new location and then erase the old data instead of just changing some references on the file-system structures.
    That's not "inefficient," just slower that certain other approaches.
    That method is inefficient (for my task, not yours) because it performs a loop over all the elements of listB allocating useless memory. All that is not necessary when listB is not accessed anymore because it makes an useless duplicate.
    Okay, and did you measure it and find it to be an unacceptable bottleneck? If not, then, once you get past a cursory, "Is there a faster way" glance at the docs, you're wasting your time pursuing this.

    If you did measure and find an unacceptable bottleneck, then, given that the docs clearly show that there is no such method, you have two choices: research 3rd party list implementations to see if somebody has done this, or create your own wrapper class. I'd imagine you'd want the wrapper to implement List, and to have its iterator first iterate L1 up to the merge point, then iterate all of L2, then pick up with L1 after the merge point.
    Having the chance to perform that task within a fixed time that doesn't completely depend on the size of the involved entities is a good thing in my opinion.
    Sure, all other things being equal, faster and cheaper is always better. I never said or implied otherwise.
    If you have {a, b, c, d, e, f} and {W, X, Y , Z}, and you want to insert the second list into the first so that you get {a, b, c, W, X, Y, Z, d, e, f} then just repeatedly call the add method on the first list that takes an index while iterating over the second list.
    First of all that functionality is a native characteristic of any Linked List. If I wanted to do using C# or C++ STL or many other languages there were no problems.
    Are you saying there's and addAll(index, Collection) method? If so, then use it, sure, but it's no different than the above, and if it didn't exist, it'd be trivial to create such a helper method. I was thinking there was only addAll(Collection), and couldn't be arsed to look it up.
    Having a class representing a data structure that doesn't offer some of its native functionality is strange in my opinion.
    The defining feature of a linked list is the pointers that link one node to the next. Supporting your desired form of insert/merge is just one of several optional flavors, just like being singly or doubly linked, being circular, etc.
    If you're thinking of something that will just manipulate the next and prev pointers on c, W, Z, and d, then no, there is no such method, as you can plainly see when you look at LinikedList's docs.
    The documentation is really big, and probably the things we're looking for could be somewhere else. For example I know of some methods like the sort method working on LinkedList and the other classes implementing Collection not described in the LinkedList documentation and not even in the Collection page, but that are available from the Collections class.
    If you're even passing familiar with the Collections Framework, it would have taken no more than 20 minutes to confirm that it doesn't exist in any of the reasonable places. If you'd indicated in your initial post where you'd searched, that would've been a different story.
    Thank goodness.
    I think that posts like yours are made just to start useless (ugly) discussions. It would nice, for somebody who doesn't have anything useful to say, to don't post anything.
    Yes, god forbid anybody have a view that differs from yours. You want the functionality, so therefore that is the One True And Correct Stance to have, and expressing a dissenting opinion is inherently wrong and not useful.
  • 13. Re: Merge one LinkedList into one other at a specified position
    johndjr Newbie
    Currently Being Moderated
    Alessandro Rossi wrote:
    If I had thought about it for more than the aforementioned 2 seconds I might have realized that addAll() takes a Collection not a LinkedList, so it was not going to be splicing the new elements into "this".
    If they wanted to handle it in that way they could use instanceof operator in the code.
    I'm not so sure that would be a good idea.
    Take this example:
    LinkedList myAList = ;  
       // assume listA has 10 elements
    List listB = methodReturningSomeList();  
       // assume listB has two elements
    
    myAList.addAll(1, listB);  
    // how many elements in listB now?
    The answer to the question in the comment would depend on what concrete type methodReturningSomeList returned.

    If it returns a LinkedList then listB has been modified and now has 11 elements.
    It it returns an ArrayList then listB is unchanged and still has 2 .
    It is unnecessarily confusing and a headache waiting to happen.

    I haven't even discussed what happens when you pass in a Map or s Set or something.

    Even in the case where you declared ListB as a LinkedList it would still be odd. I suspect that most people would expect addAll() to leave the Collection to be added alone.

    >
    I suppose that the main reason that pushed them to hide this capability regards the incoherency of listB after the operation.
    I'm not sure what you mean, maybe we are saying the same thing.
  • 14. Re: Merge one LinkedList into one other at a specified position
    Alessandro Rossi Journeyer
    Currently Being Moderated
    Don't you see that "inefficient" by itself means nothing? It's an O(N) operation. In and of itself it is neither efficient nor inefficient. Now, if you had said, "I tried it and found it to be an unacceptable bottleneck," that would be a different story.
    This is an important point in my opinion. O(N) in a ratio with O(0) gives infinite as result, that means that O(0) tends to be infinite times faster than O(N). If something proven to be infinite times slower than an optimal solution is efficient we're living in different world.
    That's not "inefficient," just slower that certain other approaches.
    That's whatever you want to call it, but it's not the way I wanted to do that task using a Linked List!
    Okay, and did you measure it and find it to be an unacceptable bottleneck? If not, then, once you get past a cursory, "Is there a faster way" glance at the docs, you're wasting your time pursuing this.
    My choose to use a LinkedList class was made to take advantage of the well known Linked List dynamic features.
    The defining feature of a linked list is the pointers that link one node to the next. Supporting your desired form of insert/merge is just one of several optional flavors, just like being singly or doubly linked, being circular, etc.
    What, you're talking about two different thing, a merge/insert method is an algorithm applicable to any kind of linked list, being double linked, circular or whatever is just a choice for the implementation of Linked List.
    Yes, god forbid anybody have a view that differs from yours. You want the functionality, so therefore that is the One True And Correct Stance to have, and expressing a dissenting opinion is inherently wrong and not useful.
    Whow what a hell.


    To be clear, I don't want to pretend to be better than anyone else. I just want to do my tasks.

    I could have waited a little more before asking the question, because if I went a little deeper in the analysis I would had find the answer without asking anybody.

    But I asked that question because I felt it was possible to expect the presence of such feature from a LinkedList. It is not possible for whatever reason, it's OK! But I know it now, Yesterday I didn't.

    Then I found a different solution not the best probably one of the laziest ways as possible, surely the quickest one to implement.

    But, in my opinion, who came here not for giving hints or showing acceptable alternatives to perform that task, did it just for trolling.

    I want to repeat again I just asked the question, I didn't ask for your comments about using the addAll method, also I think it shouldn't be used for that task, it performs a copy of the elements by definition and I was looking for a move. The reflection about the use of instanceof was just a little consideration (one line of comment in a post) made too early, then I pasted the code because I already downloaded the source to inspect the LinkedList class just to show it to a poster who told about it.

    Finally today I also corrected the methods I add to the class I pasted. And now the side effects caused by the references for the same elements by the two lists involved disappeared, listA will have all the elements and listB will became empty.

    It may be a dirty way, not purist, but but I see it as good trade-off between my expectation and a correct behavior.
        public static <E> void moveInto(LinkedList<E> source,int index, LinkedList<E> destination) {
             if (index < 0 || index > destination.size) {
                  throw new IndexOutOfBoundsException("Index: "+index+", Size: "+destination.size);
             }
             Entry<E> successor = (index==destination.size ? destination.header : destination.entry(index));
             Entry<E> predecessor = successor.previous;
             
              Entry<E> first = source.header.next;
              Entry<E> last = source.header.previous;
              
              predecessor.next = first;
              first.previous = predecessor;
              last.next = successor;
              successor.previous = last;
              destination.size += source.size;
              source.header.next = source.header.previous = source.header;
              source.size = 0;
        }
1 2 Previous Next

Legend

  • Correct Answers - 10 points
  • Helpful Answers - 5 points