Instead of using linked lists to represent the rows and/or columns of sparse arrays, we can use binary search trees. If the trees are kept balanced, then this means that array element access can be performed in time (where x is the number of non-zero elements in the given row or column). With some care, even a completely full n-by-n array can have its elements accessed in time. While this is quite a bit more than the O(1) required by the ordinary representation, it is also much less than the O(n) required in the worst case by the linked-list approach.
Implementing binary trees instead of linked lists adds a degree of difficulty to the representation- keeping trees balanced is challenging, and traversing the tree inorder (to achieve the same effect as traversing the linked list) is somewhat more so. However, these problems have all been solved before, so they should present no overwhelming obstacles.