Skip to content
Tutorials Center
My learning

Topics

Lesson 91 of 201 ยท Collections

Building Custom Collections with AbstractList and AbstractMap

Build your own Java collections the easy way. Extend AbstractList, AbstractSequentialList and AbstractMap, implement a few methods, and inherit the rest of the List and Map API.

The List interface has more than 30 methods: get, indexOf, contains, subList, equals, hashCode, iterator, listIterator, sort, stream and many more. If you wanted a list backed by an int[], a database cursor or a formula, writing all of them from scratch would be tedious and easy to get wrong. You don't have to. The Collections Framework ships skeletal implementations, abstract classes that implement almost everything in terms of a handful of methods you supply.

This lesson shows how to use AbstractList, AbstractSequentialList and AbstractMap. You will build a read-only list over an array, a list that computes its elements on demand, a fully modifiable list with modCount support, a linked list, and a map view. You'll also see why the JDK's own Arrays.asList and List.subList are built this way. It assumes you know the basics of the Collections Framework, ArrayList and iterators.

The skeletal implementation idea

Every core interface has a matching abstract class named Abstract.... You extend it, implement the few abstract methods, and everything else is inherited and built on top of them. You can override any inherited method too, usually to make it faster.

Class You must implement You get for free
AbstractCollection iterator(), size() contains, toArray, isEmpty, toString, addAll, removeIf ...
AbstractList get(int), size() iterator, listIterator, indexOf, subList, equals, hashCode, sort ...
AbstractSequentialList listIterator(int), size() get, set, add, remove (all via the iterator)
AbstractMap entrySet() get, containsKey, size, keySet, values, equals, hashCode, toString

By default the modifying methods (set, add, remove, put) throw UnsupportedOperationException. That gives you a read-only collection for free, and you opt in to mutation by overriding the methods you want.

A read-only list: get and size

The smallest useful list needs only get(int) and size(). The first class below wraps an int[] and exposes it as a List<Integer>. The second never stores its elements at all: element i is computed as i * i when you ask for it, so a list of a billion squares costs almost no memory. RandomAccess is a marker interface that tells algorithms that get(i) is fast.

Java Read-only lists with only get and size

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

Notice how much worked with two methods: printing, contains, indexOf, subList, the enhanced for loop, streams, and an equals and hashCode that follow the List contract, so the list is equal to List.of(5, 3, 9, 1). Arrays.asList(...) works the same way: it is a fixed-size list over an array, which is why set works on it but add throws. Throw the right exception from get for an invalid index (IndexOutOfBoundsException); Objects.checkIndex does that with a good message.

Be careful with huge lazy lists like Squares. Methods such as toString, equals, contains and stream().sum() walk the whole list, so on a billion-element list they will happily try to produce a billion items. Asking for size() or a single get(i) is cheap.

A modifiable list: set, add, remove and modCount

To allow changes, override the mutators you need. set(int, E) replaces an element and keeps the size. add(int, E) and remove(int) change the size, and the contract says each of these structural changes must increase the protected field modCount, an int that AbstractList declares for you. Its iterators remember the value of modCount when they were created and compare it on every next(). If the list was structurally modified in between by anything other than the iterator itself, they throw ConcurrentModificationException. That is the fail-fast behavior of ArrayList, and you get it by incrementing one field.

Once get, size, set, add(int, E) and remove(int) exist, you inherit the rest: add(E) (calls add(size(), e)), addAll, remove(Object), removeIf, sort, clear and more.

Java A growable list with modCount and fail-fast iteration

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

The class is named RingLog for the idea of a log you append to, but it is really a tiny ArrayList. Two details are worth studying. First, set does not touch modCount: replacing a value is not a structural change, so you may call set while iterating. Second, remove("b") works even though you never wrote it, because AbstractCollection.remove(Object) finds the element with the inherited iterator and calls the iterator's remove, which in turn calls your remove(int). In the last block the exception comes from the loop's next next() call, and the list is left in the state the removal produced.

removeRange: the hook behind subList().clear()

AbstractList has a protected method removeRange(from, to). It is the hook behind a trick you may already use: list.subList(2, 5).clear() deletes a range of elements. The default implementation removes elements one at a time through the list iterator, which is slow on array-backed lists because every removal shifts the tail. ArrayList overrides it to shift once. If you build an array-backed list, override removeRange the same way (and bump modCount) to make clear() on a sub-list fast. You can watch the call in action by subclassing ArrayList.

AbstractList assumes random access: get(i) should be quick. For a linked structure, get(i) has to walk from the head, so the natural primitive is an iterator instead. AbstractSequentialList flips the contract: you implement listIterator(int index) and size(), and it builds get, set, add(int, E) and remove(int) on top of that iterator. LinkedList itself extends this class.

The Chain class below delegates its iterator to an internal LinkedList just to keep the example short; in a real list you would write the node walking yourself.

Java AbstractSequentialList and removeRange in action

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

subList(2, 5).clear() removed the elements at indexes 2, 3 and 4 in a single removeRange call, while the plain remove(0) did not use it. The number of iterator requests at the end is an implementation detail of the JDK version you run, so never rely on the exact count; the lesson is that every positional operation goes through listIterator.

AbstractMap: implement entrySet

AbstractMap needs only one method, entrySet(), which returns a Set<Map.Entry<K, V>>. From it, the class derives get (a scan of the entries), containsKey, containsValue, size, isEmpty, keySet, values, equals, hashCode and toString. The scan makes those lookups linear, so override get if you can do better. put and remove throw UnsupportedOperationException unless you override them. AbstractMap also provides two ready-made entry classes: SimpleEntry (mutable) and SimpleImmutableEntry.

The example is a read-only view of a string as a Map<Character, Integer> of letter counts. It computes the entries when asked, so it always reflects the string it wraps.

Java A map view built with AbstractMap and entrySet

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

Because entrySet() is rebuilt on every call, every get here re-counts the string, which is fine for a demo but wasteful. A real implementation would cache the entries (and invalidate the cache if the underlying data can change) or override get directly.

When to build your own

Writing a custom collection is rarely the first choice. Reach for it when you need:

  • a view over existing data without copying it (an array, a database result, a file),
  • a computed sequence that would be too large or too slow to materialize,
  • a collection with an unusual rule, such as a fixed capacity, a case-insensitive key or automatic logging,
  • a class that must be a List or Map to plug into an API.

For plain storage with a twist, composition usually beats inheritance: hold an ArrayList in a field and delegate to it. Extend a concrete class such as ArrayList only to add one behavior, as LoudList did. And remember the rules every collection must honor: equals and hashCode follow the interface contract (the skeletal classes do this for you), size() is consistent with the iterator, and unsupported operations throw UnsupportedOperationException rather than doing nothing. For ready-made immutable collections see Immutable Collections and Utility Methods.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Which two methods must you implement to get a working read-only List by extending AbstractList?

    AbstractList builds iterators, indexOf, subList, equals and the rest from get(int) and size(). Modifying methods throw UnsupportedOperationException until you override them.
  2. 2. What is modCount used for in AbstractList?

    modCount is incremented on structural changes (add or remove). Iterators compare it with the value they saw at creation, which gives fail-fast behavior.
  3. 3. You extend AbstractSequentialList. Which method do you implement instead of get(int)?

    AbstractSequentialList is for linked structures. You provide listIterator(int) and size(), and get, set, add and remove are built on that iterator.
  4. 4. What is the only method you must implement to subclass AbstractMap?

    AbstractMap derives get, containsKey, keySet, values, size, equals and hashCode from entrySet(). put throws UnsupportedOperationException unless you override it.
  5. 5. list.subList(2, 5).clear() is fast on ArrayList because of which hook?

    subList(...).clear() ends up calling the protected removeRange on the backing list. ArrayList overrides it to remove the whole range with a single shift.

Summary

  • The skeletal classes AbstractList, AbstractSequentialList and AbstractMap implement most of an interface from a few methods you supply.
  • A read-only list needs only get(int) and size(); a map view needs only entrySet(); a linked list needs listIterator(int) and size().
  • Mutators throw UnsupportedOperationException by default; override set, add(int, E) and remove(int) to make a list modifiable.
  • Increment modCount on every structural change so iterators fail fast with ConcurrentModificationException.
  • Override removeRange to speed up subList(...).clear() on array-backed lists, and override inherited methods such as get or contains when you can beat the generic version.
  • Prefer views and computed lists over copying, and prefer composition over inheritance for ordinary storage.

Next: Specialized Collections, the ready-made EnumMap, BitSet, IdentityHashMap and friends that already cover many unusual needs.