3

My aim is to delete a node somewhere in the middle of a Java LinkedList object, in O(1) time.

If I can get a reference to the node, I could probably do this myself without the need for a Java-provided method. But I cannot seem to find a way to get a reference to anything but the head of the list.

How can I get a reference to the last node in a Java LinkedList object? I wold then store these references in a map to use later.

Note: I know this is doable if I implement my own LinkedList, but is there a way to do it with Java's LinkedList class?

rahs
  • 1,759
  • 2
  • 15
  • 31
  • This is an admirable aim, but I don't think there is a way to do it. – mwarren Apr 24 '20 at 09:46
  • Note that in practical use cases `LinkedList` is incredibly rarely the correct data type for storing stuff in Java (even the original author seems to think so). Yes, that does run contrary to what you usually learn in your data structure courses. What is your specific use case and why do you think that `LinkedList` is the way to go. – Joachim Sauer Apr 24 '20 at 09:59

2 Answers2

0

I would suggest actually changing your data structure to LinkedHashSet here instead of LinkedList. The reason for this is that LinkedHashSet#get() and remove() can lookup or delete any element by key in O(1) time. Also, a LinkedHashSet is implemented with a linked list running through the entries. The order of the entries while iterating the list are determined by the insertion order, so it behaves similarly to a LinkedList in that regard.

Tim Biegeleisen
  • 502,043
  • 27
  • 286
  • 360
  • A great suggestion! The only issue with this is the inability to store duplicate values. Do you know of a data structure that can handle those? – rahs Apr 24 '20 at 09:53
  • Well, you could use `LinkedHashMap`, and have the value be a collection. That way, each value would actually point to a set of duplicates. Maybe not ideal, but it might work for your case. – Tim Biegeleisen Apr 24 '20 at 09:54
  • Follow up: How would I use remove on the last element without knowing what it is? And say I remove the last, I wouldn't know what the second last is unless I maintain a queue which I don't what to do – rahs Apr 25 '20 at 09:55
  • @rahs [Check here](https://stackoverflow.com/questions/10741902/java-linkedhashset-backwards-iteration). You may iterate the `LinkedHashSet` in reverse and delete just the "first" item (actually the last item). – Tim Biegeleisen Apr 25 '20 at 10:12
0

The closest thing you can get to a direct reference is an Iterator that points to a specific point.

If you call remove() on such an Iterator it should work in O(1):

LinkedList<Object> linkedList = ...;
Iterator<Object> it = linkedList.iterator();
while (it.hasNext()) {
  if (matchesSomeCondition(it.next()) {
    it.remove();
  }
}

Note that this sample code definitely doesn't run in O(1), it's specifically just the remove() call that can have that efficiency. If you haven't already identified the node in some way (such as positioning an Iterator at that place), then you won't be able to remove an element from a LinkedList in O(1) time.

Edit and since you mention "last recently added" element then maybe a ListIterator is the thing to use, since it has an add() method. If you can efficiently implement all your adding/removing using a ListIterator, then you can keep the traversal operations over the LinkedList to a minimum. In fact, if you always use indexes to add/remove objects from your LinkedList then you loose a lot of its efficiency (since each add/remove call has to find the affected item first via traversal).

Joachim Sauer
  • 302,674
  • 57
  • 556
  • 614
  • How can iterating a list of size N to find an arbitrary element possibly be an `O(1)` operation? If I understand correctly, the OP is not asking about the running time of the service call, rather the overall running time. – Tim Biegeleisen Apr 24 '20 at 10:01
  • @TimBiegeleisen: It can't and that's also not what I said. `remove()` is the O(1) operation, not getting the iterator there. If the node hasn't been somehow identified already, then there won't be any way to make it O(1) with just a LinkedList. Edit: I've added a clarification to my answer. – Joachim Sauer Apr 24 '20 at 10:03