Add Linked List to the End of Another Linked List in Java

Question

This is using the Java Linked List. I have 2 linked lists. I would like to add them together by linking the last node in the 0th list to the 0th node in the 1st list. Currently I can append them together by iterating through the second list and adding every element in it like so:

LinkedList<HashSet<Integer>> ll = someList;//Some random list
LinkedList<HashSet<Integer>> subSetLl = getSubsets(inSetSub);//Also some list
for (HashSet<Integer> set : subSetLl){
 ll.add(set);
}

However, since these are Linked Lists, there should be a more efficient way to add them together, by pointing the end of one to the beginning of the next. Does such a thing exist?

EDIT FOR CLARITY: The current method runs in O(n) where n is the length of the 1st Linked List. Is there a O(1) method to accomplish this if both elements are Linked Lists?

• willeM_ Van Onsem: The problem is: what if you want to modify the last linked list later? In that case it will have impact on the appended linked list...
• Gyro Gearless: see java.util.List.addAll()
• willeM_ Van Onsem: @GyroGearless: performance-wise that's exactly the same.

Answer 1

I think the only way to do it is to copy the implementation of the LinkedList class and then change the addAll method to recognize if the collection being passed is of the same class. Also you have to be aware that if you add list to the end - it is unsafe because potentially the change in one list will cause the change in another. And if you copy the memory and make it safe there is no way to improve efficiency since you are looping through the elements anyway.

Answer 2

From the javadoc for LinkedList:

addAll(Collection c) Appends all of the elements in the specified collection to the end of this list, in the order that they are returned by the specified collection's iterator.

public boolean addAll(Collection c)

Appends all of the elements in the specified collection to the end of this list, in the order that they are returned by the specified collection's iterator. The behavior of this operation is undefined if the specified collection is modified while the operation is in progress. (Note that this will occur if the specified collection is this list, and it's nonempty.)

Parameters:

c - collection containing elements to be added to this list

Returns:

true if this list changed as a result of the call

• WarSame: The problem is that this does the exact same thing - it iterates through the 1st list and adds items one by one. I'm hoping for some more efficient solution that abuses the fact that my two items are Linked Lists.
• Avihoo Mamka: This function is from the official javadoc, hence it's the safest solution in my opinion.

Answer 3

LinkedList.addAll(index, Collection)

Inserts all of the elements in the specified collection into this list, starting at the specified position. Shifts the element currently at that position (if any) and any subsequent elements to the right (increases their indices). The new elements will appear in the list in the order that they are returned by the specified collection's iterator.

• WarSame: This has the same problem, though - it simply iterates through the 1st list and adds elements to the 0th list one at a time. I'm hoping for something more efficient.