Intrusive lists are one of those neat data-structures that are often overlooked.

TL;DR download IntrusiveList.java

Intrusive lists have O(1) remove if you already have the address of the object, and O(1) insert too at head/tail or if you already have the address of an adjacent object.  This is because they store their previous and next pointers in the object itself, rather than having some separately allocated ‘list node’ object.  This makes them very memory efficient and cache-friendly too.

They are common enough inside performance critical code, e.g. in games and operating system kernels.

Its generally better to just put objects you want to get at in a hash-map/set.  That, too, has O(1) add and remove (amortized blah blah).  Hash-tables a good fit outside the extreme performance code or for set operations or maps and so on.

Intrusive lists have advantages for some scenarios: for example, they are ideally suited to most-recently-used lists.  They preserve order and it is O(1) to move an item from the middle of the list to the head when it gets used.

In C/C++ and so on there are various tricks you can do with offsetof() and macros to make utility code that you can mix-in.  In Java, you cannot easily encapsulate a classic intrusive list in a class because its intrusive.  You have to actually put your own prev and next pointers into your class and write your own linking and unlinking code.  This can be error prone.

Or you can allocate a linked node pointer.  Its a compromise you can make, knowing that it’ll likely be allocated adjacent to the main class in memory and have the same lifetime and so on.  If you’re chasing performance in Java you start thinking about mechanical sympathy and avoiding garbage collection and so on.

I offer you a simple IntrusiveList.java class that I use.

Store an instance of it in a (final) attribute on your item.  You can then link() and unlink() it from other items.  You can also create head/tail nodes with makeList() which can be useful.

Classic iteration over all nodes looks like this:

for(Item item = list.getNext(); item!=null; item = item.list.getNext()) ...

To move an item to the top of the list is as simple as:

item.list.link(list);

MRUs have never been simpler nor faster!

The class could easily be extended to use weak-references.  Locking and concurrency are harder to add.