It doesn't have to be a linked list though. There are other purely functional sequence data structures which support O(log n) insertion and deletion, e.g. Haske

It doesn't have to be a linked list though. There are other purely functional sequence data structures which support O(log n) insertion and deletion, e.g. Haskell's Data.Sequence, which is a finger tree of some sort. If you could find a way to do binary search on one of these in better than O(log^2 n) time you'd pretty much have your purely functional skip list.