CODEWITHSUNDEEP
javalinked-list
Peter
Peter

Reputation: 11910

Efficiently removing an item from Java LinkedList

Here is the pseudo-code I am using to remove an item from the linked-list:

public static void removeByID(LinkedList<Fruit> fruits, int fruitID) {
    for(Fruit f : fruits) {
      if (f.ID == fruitID) {
         fruits.remove(f);
         return;
      }
    }
}

I am thinking this is not very efficient as fruits.remove() will once again iterate over the list. Wondering if there is a better way to achieve this.

Upvotes: 1

Views: 160

Answers (5)

chiastic-security
chiastic-security

Reputation: 20520

Nope, not in terms of asymptotic complexity. That's the price you pay for using a LinkedList: removals require a traversal over the list. If you want something more efficient, you need to use a different data structure.

You're in fact doing two traversals here if you've got a singly linked list: the .remove() call needs to find the parent of the given node, which it can't do without another traversal.

Upvotes: 3

BodXav
BodXav

Reputation: 23

Regarding to your post, using a HashMap appears to a good solution. In addition, if we suppose that you need also to search a fruit using the fruitID into your set, HashMap will make the search time barely constant.

Regarding complexity, you can find additional information on Simple Notions article depending the data structure that you use.

Upvotes: 0

Radiodef
Radiodef

Reputation: 37845

For a java.util.LinkedList, use the Iterator.

Iterator<Fruit> it = fruits.iterator();
while(it.hasNext()) {
    if(it.next().ID == fruitID) {
        it.remove();
        break;
    }
}

This will result in only a single traversal. The Iterator returned has access to the underlying link structure and can perform a removal without iterating.

The Iterator is implicitly used anyway when you use the for-each loop form. You'd just be retaining the reference to it so you can make use of its functionality.

You may also use listIterator for O(n) insertions.

Upvotes: 5

rock-fall
rock-fall

Reputation: 438

As stated in the above linked lists generally need traversal for any operation. Avoiding multiple traversal can probably be done with an iterator. Although, if you are able to relate fruit to fruit.ID ahead of time you may be able to speed up your operations because you can a void the slow iterative look up. This will still require a different data structure, namely a Map (Hashmap probably).

Upvotes: 0

kapex
kapex

Reputation: 29979

If you need to access elements from a collection that have a unique attribute, it is better to use a HashMap instead, with that attribute as key.

Map<Integer, Fruit> fruits = new HashMap<Integer, Fruit>();
// ...
Fruit f = fruits.remove(fruitID);

Upvotes: 0

Related Questions