I am mostly looking for someone to confirm the following is correct.
- It is trivially obvious that joining two linked lists (singly or doubly) into one linked list "tail to head" can be done in O(1) time.
If we do not have a reference to the tail of the first list, then it is O(n) time where n is the length of the first list, but the important part is that the step where we add the two linked lists together consists of 1 step (linking the tail of the first list to the head of the second)
- The java utility class LinkedList is an implementation of a the List interface, which internally uses a doubly linked list.
However, because the public interface is that of a List, specific operations that manipulate the nodes and connections are not possible.
It is not quite correct to say that LinkedList is the same as the doubly linked list ADT
As such, if our "linked list" is an instance of java.util.LinkedList it is not possible to join lists in O(1).
Work I have done so far: a. I have written my own singly linked list class and used this to demonstrate the O(1) linking behaviour. The behaviour for a doubly linked list is almost identical. I can post this if requested.
b. I have read the oracle documentation for the LinkedList: https://docs.oracle.com/javase/8/docs/api/java/util/Collection.html
c. I have looked through the source code of how LinkedLists is actually working:
As far as I can see, there is nothing here that checks if the two things being combined are both LinkedLists and implements the O(1) adding that I have described above.
CodePudding user response：
Is there any way to join two Java LinkedLists in O(1)?
No. Unlike C std::list::splice(), Java's native linked list does not have the ability to move nodes within a list or between two lists. With C , std::list::splice() can move all nodes from a second list to a first list, in O(1) time, using begin() or end() or user iterators to specify where to insert or append the second list's nodes to within the first list.
Another is is Java's implementation of iterators. Unlike C , they can't be shallow copied. If you assign an iterator to a second iterator, both will reference the same iterator object. If you insert or delete any nodes in a Java linked list, it will invalidate all iterators (except for an iterator used as a parameter to insert or delete).
I only know some of the history, that early some in the Java community wanted C compatibility, and there were some versions made, but that was abandoned, and ended up with what Java is now.
CodePudding user response：
Is there any way to join two Java LinkedLists in O(1)?
No.
You also want to confirm this statement:
It is trivially obvious that joining two linked lists (singly or doubly) into one linked list "tail to head" can be done in O(1) time.
This is not true, in general. It is true is some cases, not in others.
It is not true in general for list data structures that are encapsulated within an API, such as LinkedList. For encapsulated lists, the API will determine whether this is possible. For LinkedList it is not possible. The APIs do not allow it ...
However, you could design an ADT in which O(1) list splicing was possible. The "catch" is that when you splice the second list to the end of the first, it is no longer a "first class" list. The semantics are harder to reason about; e.g. the 2nd list can change as a result of operations on the 1st one. Not all operations will change it. (This kind of thing is why the standard Java List implementations don't support splicing.)
It is also not true in general for non-encapsulated lists. For example, if you (just) have the heads of two singly linked lists, you need to traverse to the tail of the first list before you can splice the second one to the end of it. The splice is O(1) but getting the tail of the first list is O(N).
However, if you implement your linked list in a way that the list object has a link to the head node and the tail node, you don't need the O(N) step.