3

If I have a linked list of objects and I want the sublist from index 2 to 5. Is this operation o(1)? All you would need to do is null the reference to prev on the node at index 2, and return the node at index 2, correct? Does this require copying the contents of the linked list into another one and returning that or just setting the head to be the node at index 2?

Improve this question
6
  • Do you mean java.util.LinkedList? If so, subList is a view onto the original list, and it would be O(n). Commented Oct 27, 2017 at 17:47
  • docs.oracle.com/javase/8/docs/api/java/util/…, Commented Oct 27, 2017 at 17:47
  • @AndyTurner how could it be O(n) if it's a simple view over the original list. It's O(1). All it does is create an object referencing the original list and storing the from and to indices. Commented Oct 27, 2017 at 17:49
  • @JBNizet because you've got to iterate to the start node, and the end node. No? I mean, I suppose you could just .get(i + start) internally when you call .get(i) on the sublist... but wouldn't that be really inefficient? Commented Oct 27, 2017 at 17:50
  • @JBNizet.: How do you get the start and end node? Commented Oct 27, 2017 at 17:51

3 Answers 3

Reset to default
2

Is this operation o(1)?

In general, getting a sublist of a linked list is O(k), not O(1)*.

However, for any specific index value, such as 2, 5, or 5000, any operation is O(1), because a specific index becomes a constant that gets factored out from Big-O notation.

* Construction of sublist may be optimized such that you pay construction costs on the first navigation of sublist, rather on construction. In other words, constructing a sublist without iterating it is O(1).

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

But OP is not asking about specific operation. The heading says something different.
@coderredoc Right, that's why I said "in general" and in this specific case. His title is disconnected from the description, though.
Excuse me sir but can you reconsider what you are saying once more? Do you seriously mean that get to the kth node of a linked list from it's head is a O(1) operation?
@n4fengn Getting node k is O(k), and I say it explicitly at the top. Getting node 5000 is O(5000), which is the same as O(1).
0

It appears that the sublist method runs in O(1) time. See the source code for the method.

All that this code does is return a new instance of SubList that is initialized with the list that sublist is invoked upon. No iteration is happening here, so the operation runs in constant time.

Improve this answer

1 Comment

It's modifiable. the javadoc says: non-structural changes in the returned list are reflected in this list, and vice-versa
0

It's O(n) if you consider the general case of the algorithm. Even if you do what you said finding the n-th and m-th element would take a complete traversal of the list.

It's wrong to consider that the finding the sublist from 2 to 5 would be O(1). It is O(1) ofcourse but it needs constant amount of operations to do that but are you creating an algorithm for sublist(2,5)? If you do that then ofcoursse it is always O(1).

A better example is sorting 100 numbers is of O(1) complexity so is sorting 10,000 numbers. But it is not what we are concerned about. We want to know the nature of the algorithm based on the inputs fed to that algorithm.

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.