Maybe you could keep around another dataset of size n+1 and only replace the last element dynamically?
n+1