The SortedList ADT

A SortedList keeps its elements in ascending order at all times, and can be implemented array-backed or with linked nodes (SortedLinkedList). add means insert into the sorted position, not append.

Solution

implements List is a claim to keep the full List contract, which promises set without marking it optional. Any code that takes a List could then be handed a SortedList and call set on it, which compiles and fails at run time. SortedList cannot keep that promise, so it needs its own interface, with no set.

Solution

No. Binary search repeatedly jumps to the middle of the current range. On an array, that jump is $O (1)$ . A linked structure has no such jump: reaching a middle node means following links to it one at a time. Using get(mid) at each step costs $O (n)$ per probe, so $O (n lo g n)$ in the worst case, worse than the $O (n)$ of a linear scan.