0

I do not understand why the complexity of removing an element in a LinkedList in Java is O(n). The LinkedList in Java is a DoublyLinkedList. In an ideal DoublyLinkedList each element have a field prev and next that points to the next and previous element respectively. Now if I think about a method remove(element), the only thing to do is to update the next and the prev field of the previous and next element. This is O(1). This is the good thing of picking a DoublyLinked List.

I tried to search in the built-in API an implementation that assure this complexity, but I failed. Is there a class in the Java API that allow to remove in O(1)?

user2695795
  • 21
  • 1
  • 2
  • the problem is how to get to that element you need to move from the start till you find it which in worest case will require to visit all element –  Apr 06 '23 at 21:52
  • the complexity to delete element in DoublyLinkedLidt is O(n) because we need to search that element in that list first, and only then we can perform the link updates. The search operation takes O(n) – shubhkr1 Apr 06 '23 at 21:53
  • Removing the element is O(1) but stepping through each of the links to get to the one to remove is O(n) – John Williams Apr 06 '23 at 22:04
  • The question is about if I have already the object. Suppose I have a LinkedList ll, I have the Person p1 and I want to do ll.remove(p1). This should be O(1) since I have the reference to p1, but Java does not work like this. – user2695795 Apr 07 '23 at 07:51
  • O(1) remove would be possible if Java supported proper iterators (an iterator is an reference to a node) for a Linked List, such as C++ std::list. In C++, nodes can also be moved within a list or from one list to another using std::list::splice(), but Java doesn't have an equivalent API. – rcgldr Apr 07 '23 at 14:46

2 Answers2

0

The link to prev and next objects not in the object itself. In linkedlist we have some nodes with link to prev, next and object, to find this node we have to check every node one by one.

Denis Rozhko
  • 60
  • 6
  • Ok, so if I implement on my own a list with object with next and prev in the fields I can in O(1) and it is more efficient than Java, seems crazy to me but ok – user2695795 Apr 07 '23 at 07:49
  • @user2695795 - Java could have followed the pre-existing C++ standard of std::list and iterators, which early versions of Java once did, using references | iterators to nodes, where prev and next pointers would be private, but compatibility with C++ standards was later dropped, and Java's LinkedList ended up as a poor implementation. – rcgldr Apr 07 '23 at 18:36
0

If you already have the element, then indeed the delete operation has a time complexity of O(1).

But:

  • Java's LinkedList class implements a doubly linked list, but its nodes are private. The API only provides access to the values in the linked list, not the nodes. So you never have a reference to the element to delete.

  • Even if you use an alternative implementation where you do have access to the nodes, you start out with a reference to the head node only, not with an array of references to all nodes in the list. So that means if you want to delete the kth node in the list, you'll have to traverse the list to locate it first. It is only fair to include that work in the work of deleting the kth node.

You wrote in a comment:

Suppose I have a LinkedList<Person> ll, I have the Person p1 and I want to do ll.remove(p1).

That will not work like you hoped, because Person does not have the prev/next properties. When you create LinkedList<Person> ll, there is a private node class involved that contains a reference to a Person, but has in addition those prev/next references. That p1 does not help you to get access to those prev/next members. You would still need to traverse the list to find which node has that particular p1 and then update that node. This is what Java's removeFirstOccurrence does.

Should Java's LinkedList have given access to nodes for better performance?

You may think that Java's choice to make the Node objects private and not provide methods to work on those nodes directly is a bad one, as it seems to make some operations on the list less efficient, but consider this:

  • If you have access to nodes directly, you can accidently make the list "inconsistent" in a way: you could:

    1. introduce cycles
    2. link to a node that is actually part of another list, and consequently:
    3. mutate another list B by mutating list A.

  • Even if those effects are acceptable in your scenario, then consider that you don't have a direct reference to each node in the linked list. If you would, then you really ended up with a collection of node references, where you have the additional task to manage CRUD operations on that collection. For instance, if it is a vector, then deletion of a node reference in that vector will be O(n). Or if it is a Map, you need unique keys for your nodes, while linked lists allow for duplicates.

    Whatever that collection would be like, it would represent an additional overhead, and in some cases you might then decide to drop the linked list and only keep that collection. For instance, with a TreeMap you get the order, and you get sublinear methods to get, set and delete an entry.

trincot
  • 317,000
  • 35
  • 244
  • 286
  • `Should Java's LinkedList have given access to nodes for better performance?` - yes, via proper iterators. std::list: assigning an iterator creates a new instance. std::list erase or insert will not invalidate any iterators, except for any iterator to the erased (deleted) node. In a release (optimized) build, some compilers will disable all checking of iterators (no overhead). Take a look at the first code snippet for [linked list bottom up merge sort using iterators](https://stackoverflow.com/a/40629882/3282056), and imagine trying to duplicate this in Java. – rcgldr Apr 07 '23 at 14:22
  • plus something equivalent to std::list::splice() (moves one or more nodes within a list or from one list to another). – rcgldr Apr 07 '23 at 14:24
  • Iterators are a different concept than giving access to the node objects themselves. They are certainly useful as implemented in C++. – trincot Apr 07 '23 at 14:33