Need a way to find the middle value efficiently.

A linked list is no good for this.

Design using L = 1 3 4 6 8 9 11.

The 1st thing we need is a pointer to the middle element: 6. What should 6 point to? There are 2 possible outcomes that involve further search: X < 6 and X > 6.

        
Similarly for 6 and 9:
        

Binary tree such that for each node: