Immutability on the interface level does not mean you should use only immutable data structures in the implementation.