Remove Minimum Element from a Java Linked List

Question

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?

Remark: You have to use 'Integer' in your List, not the primitive type 'int' — Jérôme
– Jérôme, Commented Mar 27, 2017 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
– otori, Commented Mar 27, 2017 at 13:40
Why do you want to do that? Are you hoping to improve performance? — Anonymous
– Anonymous, Commented Mar 27, 2017 at 13:53
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
– esin88, Commented Mar 27, 2017 at 13:53

Oghli · Accepted Answer · 2017-03-27 15:30:38Z

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

edited Mar 27, 2017 at 15:30

answered Mar 27, 2017 at 14:00

Oghli

2,4111 gold badge18 silver badges42 bronze badges

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

13 Comments

Anonymous Over a year ago

Yes, but it takes O(n). Just guessing that this was possibly what the asker wanted to avoid.

Oghli Over a year ago

you are right but I think this is the only possible way to achieve what he wants.

Anonymous Over a year ago

I agree that it is.

Anonymous Over a year ago

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).

Anonymous Over a year ago

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.

|

Jérôme · Accepted Answer · 2017-03-27 13:40:04Z

0

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

void removeMin(LinkedList<Integer> list) {
    list.remove(Collections.min(list));
}

answered Mar 27, 2017 at 13:40

Jérôme

1,2502 gold badges22 silver badges28 bronze badges

Comments

K.Nugusbayev · Accepted Answer · 2017-03-27 18:37:26Z

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.

answered Mar 27, 2017 at 18:37

K.Nugusbayev

211 bronze badge

Collectives™ on Stack Overflow

Remove Minimum Element from a Java Linked List

3 Answers 3

13 Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

13 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related