2

I have two LinkedLists in Java and I would like to prepend all elements of one list to another. Is there a native way to do this in O(1) time? I know all that needs to be done is set the last pointer of the first list to the first of the second list, but there doesn't seem to be a native method to do this.

Also, to add to the complexity of this, I need a way to prepend the list to another one and not append it. I have list A and B, and I need all elements of B to be prepended to list A. I can't just add the elements of A to the end of B because I want to list A to be modified.

Is there a way to do this without having to implement my own LinkedList?

ThomasFromUganda
  • 380
  • 3
  • 17
  • But it would be O(n) to get to the end of the first list correct? – Tyler Feb 14 '20 at 21:41
  • 1
    No, this is not possible. I mean, maybe you could use reflection to access and manipulate the private internal data structure, but don't do that. If you need this performance characteristic, write your own linked list. – kaya3 Feb 14 '20 at 21:44
  • 1
    @Tyler `LinkedList` is a double linked list and `getLast()` is O(1), you can see the source code. – Karol Dowbecki Feb 14 '20 at 21:45
  • @KarolDowbecki thanks – Tyler Feb 14 '20 at 21:45
  • This has ( sort of ) been asked before. "Concatenate two java.util.LinkedList in constant time" Look here: https://stackoverflow.com/questions/38303986/concatenate-two-java-util-linkedlist-in-constant-time – Gonen I Feb 14 '20 at 22:12
  • Oh, and this one: Is there a fast concat method for linked list in Java? "https://stackoverflow.com/questions/2494031/is-there-a-fast-concat-method-for-linked-list-in-java/2494884" – Gonen I Feb 14 '20 at 22:15
  • Ok, it has been asked before ALOT. :) Here's another: https://stackoverflow.com/questions/2237308/merge-two-lists-in-constant-time-in-java/2237387 – Gonen I Feb 14 '20 at 22:33

1 Answers1

1

There is no predefined method to do it in O(1) time. You can however do it in O(N) using LinkedList.add(index, Collection) method by using 0 index:

LinkedList<Integer> source = new LinkedList<>();
source.add(1);
source.add(2);
LinkedList<Integer> target = new LinkedList<>();
target.add(3);
target.add(4);

target.addAll(0, source);
System.out.println(target); // [1, 2, 3, 4]

Above is O(source N) because addAll will iterate over data in the collection parameter.

Karol Dowbecki
  • 43,645
  • 9
  • 78
  • 111