2

I am trying to remove a minimum element from a Java LinkedList.

In order to find the minimum, I have to traverse through the LinkedList once. I would like to save the Node or Iterator of that element to remove it in O(1).

The normal

list.remove(Object o)

takes O(n) steps.

void removeMin(LinkedList<Integer> list) {
    ListIterator<Integer> itList = list.listIterator();

    Integer min = itList.next();

    while(itList.hasNext()) {
        Integer curVal = itList.next();
        if(curVal < min) {
            min = curVal 
            // Copy the iterator here?
        }        
    }
    // remove min from list here.
}

Is there a way, to copy the iterator, when a new minimum is found, so I can call the remove() of the iterator afterwards?

otori
  • 111
  • 8
  • 2
    Possible duplicate of [Pointer into Java LinkedList Node](http://stackoverflow.com/questions/21294241/pointer-into-java-linkedlist-node) – glee8e Mar 27 '17 at 13:33
  • Remark: You have to use 'Integer' in your List, not the primitive type 'int' – Jérôme Mar 27 '17 at 13:35
  • You are right, I changed my example Code... Still, the problem is there, but what I read from glee8e's comment link, it does not seem to be possible -.- – otori Mar 27 '17 at 13:40
  • Why do you want to do that? Are you hoping to improve performance? – Ole V.V. Mar 27 '17 at 13:53
  • 1
    You have to traverse your list at least once, as you said. That is already `O(n)`. If you traverse it twice (first to find minimum element, second to remove it) the overall complexity is still `O(n)`. – esin88 Mar 27 '17 at 13:53
  • @otori check the updated solution i think it will work for you – Oghli Mar 27 '17 at 15:33

3 Answers3

1

you can copy the iterator at current .next index in this way :

ListIterator<Integer> minItList = List.listIterator(itList.nextIndex());

the solution will be like:

ListIterator<Integer> itList = list.listIterator();
ListIterator<Integer> minItList = list.listIterator();

Integer min = itList.next();

while(itList.hasNext()) {
    Integer curVal = itList.next();
    if(curVal < min) {
        min = curVal; 
        // Copy the iterator here?
        minItList = list.listIterator(itList.nextIndex());
    }        
}
  // remove min from list here.
  minItList.previous();  
  minItList.remove();  //note that you can't call .remove() on list iterator until .next() or .previous() have been called once because you will get IllegalStateException
Oghli
  • 2,200
  • 1
  • 15
  • 37
  • Yes, but it takes O(n). Just guessing that this was possibly what the asker wanted to avoid. – Ole V.V. Mar 27 '17 at 14:01
  • 1
    you are right but I think this is the only possible way to achieve what he wants. – Oghli Mar 27 '17 at 14:04
  • I agree that it is. – Ole V.V. Mar 27 '17 at 14:05
  • @otori I think the updated solution will work for you – Oghli Mar 27 '17 at 15:32
  • @OleV.V. now it will take O(1) because we only call .remove() on the reference to the min object that we save it in `minItList` iterator. – Oghli Mar 27 '17 at 15:44
  • 1
    Nice thought, but it doesn’t work that way, sorry. First, every time you meet a preliminary minimum, you create a list iterator, that’s n times at worst, maybe typically just squareroot(n). Next, creating the list iterator is O(n) because it has to step through the list to the desired position. So all this alone is O(n*n) or O(n^2). After that you are correct, calling `remove()` is O(1). – Ole V.V. Mar 27 '17 at 16:24
  • @OleV.V. Thanks for the detailed explanation on calculating big O – Oghli Mar 27 '17 at 18:23
  • Yes, Ole is right - since nextIndex() only returns an int, the contructor of the ListIterator(int) has to iterate to the position. At this point I think it is just not possible to remove the minimum in O(1) i the java implementation, although in theory it is possibly for a double linked list data structure. – otori Mar 29 '17 at 12:16
  • @otori I think our problem with the way that iterator reach a specific element if it will iterate through all elements to the position of min then it will take also O(n) or if it will reach specific position for element directly then that's what we want and it will be O(1) so our problem with algorithm that iterator implemented to reach a specific position and I think in linked list it's hard to reach element in o(1) because it not like array which directly reach specific element by it index and this one of pros for array over linked list. – Oghli Mar 29 '17 at 15:17
  • the only way to reach element in linked list directly in O(1) is to know and save it's address in the memory so you can get to it's value directly and this is a lower level of programming which I think C++ is more efficient than java in memory management and manipulating. – Oghli Mar 29 '17 at 15:21
  • @OleV.V. what do you think about this. – Oghli Mar 29 '17 at 15:22
  • 1
    Thanks for inviting me back into the discussion, @MohammadOghli. This isn’t about the language, but about the design of `java.util.LinkedList`. It would be easy to design a linked list in Java that would allow you to access the nodes of the linked list so you could save a reference to the one you wanted to delete. Then you could delete in O(1). It would “just” break the principle of encapsulation. – Ole V.V. Mar 29 '17 at 15:44
  • right exactly what I was thinking about it's it's a matter of design and algorithm that linked list is implemented in java.util. – Oghli Mar 29 '17 at 15:54
0

I dont know if its faster but you can use Collections.min(...)

void removeMin(LinkedList<Integer> list) {
    list.remove(Collections.min(list));
}
Jérôme
  • 1,254
  • 2
  • 20
  • 25
0

in any way, if you use sequential search symbol table(unordered linked list) in worst case find of minimum element will be O(N) + O(M) for removeOperation where M "position" of Min Node. May be you should use binary search symbol table(ordered) where at the head store the minimum value and you with O(1) time can deleteMin.

K.Nugusbayev
  • 21
  • 1