Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Merge two lists in constant time in Java

Tags:

java

merge

Does anyone know if it's possible to merge two lists (or any collection) in constant time in Java ?

http://www.cppreference.com/wiki/stl/list/splice

It's so easy to do that using linked lists in C...

Thanks,

like image 683
Damien Avatar asked Feb 10 '10 14:02

Damien


People also ask

What is the time complexity of merging two lists?

Time Complexity: O(N+M) where N and M are the sizes of linked lists. Space Complexity: O(N+M), creating dummy nodes.

Can we merge two Java lists?

The addAll() method to merge two lists The addAll() method is the simplest and most common way to merge two lists.

How do you link two linked lists together?

(1) Create a new head pointer to an empty linked list. (2) Check the first value of both linked lists. (3) Whichever node from L1 or L2 is smaller, append it to the new list and move the pointer to the next node. (4) Continue this process until you reach the end of a linked list.


1 Answers

The classes in the JDK library don't support this, as far as I know.

It's possible if you build your own implementation of List - which you're free to do, it's perfectly legal. You could use LinkedLists and recognize the special case that the collection to be added is also a LinkedList.

In documenting your class, you'd need to point out that the added object becomes part of the new object, in other words a lot of generality is lost. There's also lots of potential for error: Altering either of the original lists (if they're mutable) after joining would allow you to create a list with a gap in it, or with two tails. Also, most other operations wouldn't benefit from your hacked-up class. In other words, at first blush it seems like a crazy idea.

Note that "merging" lists usually has different connotations; when merging sorted lists, for example, one would expect the resultant list to have the same ordering. What you're talking about with joining two Linked Lists is really better termed as "splicing". Or maybe just "joining."

like image 152
Carl Smotricz Avatar answered Oct 06 '22 04:10

Carl Smotricz