2

I was looking through the LinkedList API for Java 7 and noticed something curious. there does not appear to be a "remove before (or after)" type of method. For example, If I have a 100 element LinkedList, and I want to remove the first 20 elements, Java seems to force you to remove them one at a time, rather than moving the start pointer to the 21st element and deleting the link between 20 and 21. It seems like this is an operation that can be done in O(1) time, instead of O(n) time as Java seems to force you to do it.

Am I missing something here, or is it just a glaring hole in Java?

EDIT

I am aware of the sublist(int, int) method in the List interface. I still think that this will be slightly less efficient than the generic "chop off the first (or last) n" use case.

EDIT 2

Touche to everyone who pointed out that finding the nth element is not O(1). Regardless of the ease of chopping off the first n-1 elements, it still takes O(n) time to find the nth.

However, as Dilum Ranatunga points out, there is the possibility that an iterator already exists at the given position. In this case, it would still be useful to say "I am here, remove all before me".

4

6 回答 6

5

It's still an O(n) operation no matter what you do.

You don't have direct access to the individual nodes of the linked list, so you would have to traverse the list first to get access to the 21st node. Once you were there it would be O(1) to 're-head' the list, but it's still O(n) for the entire, atomic operation.

于 2012-07-18T17:28:41.180 回答
1

LinkedList inherits a sublist method from List interface. Information can be found here http://docs.oracle.com/javase/6/docs/api/java/util/List.html#subList(int, int)

于 2012-07-18T17:27:16.360 回答
1

You can call list = list.subList(21, list.size()) to get a sublist from 21 to the end of the list.

The operation is O(1), but you do not get a LinkedList back, you get an AbstractList.SubList which acts like a wrapper class for the original LinkedList, delegating methods with the sublist's offsets.

Although this is constant time, it is important to note this is not a new list. If your list size went from n to m, subsequent linear-time methods called on the list will still run in O(n) not in O(m).

于 2012-07-18T17:28:10.283 回答
1

It is impossible to immediately jump to the Nth element because each prior node contains the address of the Node.next (the next node in the chain). So it has to naturally traverse 20 elements causing O(n) runtime.

For example:

[Node 1, address of Node 2] -> [Node 2, address of node 3] -> etc... -> [Node 20, address of Node 21]

You cannot get the "address of Node 21" without getting to the Node 20 first, and to do so you need to "address of Node 20" from Node 19 and so on.

于 2012-07-18T17:29:53.743 回答
1

What is your algorithm for finding item n in O(1) time? This would still be an O(n) operation to locate the nth item and set it as the head. You would save some intermediate pointer assignments compared to 20 removes, but not a huge gain.

于 2012-07-18T17:30:14.457 回答
0

Java's java.util.List defines the API listIterator(). ListIterator has previous().

So the idiom you want is:

// some loop construct {
  listIter.previous();
  listIter.remove();
}
于 2012-07-18T17:30:42.270 回答