A Java-related list that supports the quick removal of any nodes?

Question

java.util.LinkedList does not allow you to quickly remove this object from the list. The remove (object) method performs a linear search to find the object in the list so that it can remove it. Since this is a double linked list, it would be nice to delete just updating the pointers (node.prev and node.next).

What is the standard Java solution for this problem?

NOTE 1: I do not want to delete during iteration. I know this is fast, but I do not repeat my elements in the first place.

NOTE2: To make it simple: given the O object, which I know is in a double linked list, I want to quickly remove O from this list (by updating pointers) without having a linear search for it in the list, like java.util .LinkedList does.

Answer 1

You should take a look at the LinkedHashSet class. This is mainly a HashSet, which maintains a double list among its entries. It supports searching (and therefore deleting) an element in O (1) (hopefully). Check the specification link for how it handles the order of items in case of re-setting the record and other details.

EDIT:

If you need to keep duplicates, you can take a look at Guava LinkedHashMultiset (never been used before). Guava Multiset User Guide here .

Answer 2

I bet that the implementation of LinkedList#remove() removes it by updating the pointers to the previous and next elements - the problem is that it must iterate over all the objects until it finds a suitable one for removal.

If you want a collection that is deleted faster without iterating over all objects, use Set or Map .

Answer 3

It looks like you need a complex object. Create a class containing your list, and save the index in that list.

Therefore, when you want to quickly delete, you perform a constant search on the time index to get a link to the list item that you want to delete, followed by a permanent removal of time.

Answer 4

I am primarily a C programmer learning Java. I found this thread because I also wonder why there was no linked implementation of the list where you could just delete the object directly without looking for it. Search is linearly incredibly inefficient. The list maintained by the hash table is better, but you really don't know how the hash table will be executed.

The reason you can easily do this in C is because usually the list item object itself contains the next and previous pointers, so given the object, this is an easy way to manipulate multiple pointers to remove an item from the list, so this is an operation O (1). In Java, you have an object, but you do not have direct access to pointers, because they are supported separately in the list. Thus, you need to search for the object either linearly or using a hash table.

It seems that this problem can be solved by creating an implementation of a linked list, where each type of object added to the list will have to implement the LinkedListElement interface, which will support the receipt and installation of the next and previous pointers. You will need to add the following and previous pointers to your class and implement the functions for getting and setting them. The link list class can then easily remove the object, because the object itself contains pointers.

Answer 5

Typically, you want to work using ListIterator where possible. It remove will be permanent.

The Java standard library does not have a separate node linked list structure, so I think ListIterator is the best option.

Answer 6

Perhaps a map would be suitable. It gives the expected time to remove O (1). But again, you did not indicate what it means quickly.

A list supported by BST may also work. This will give log (n) delete time.

For the solutions listed here, I took something faster, iterating through the list, so that everything is faster than O (n);