Apr 092018Search problems vary in two ways: what do we want to search for, and what type of collection are we searching in?(1)
When we need a search algorithm, the data structure we want to search is more important than what we want to find.
We could even say that linear search and binary search work on different data structures: linear search uses a list, and binary search uses a list which must be kept in order.(2)
Feb 122018A list can do everything an array can do, and more; the array data type is strictly “less useful” than the list data type.
However, the array data structure is both faster and uses less memory than any list data structure.(1)
This is common: if a data type supports fewer operations, then programmers who use that type have less freedom, but programmers who implement it (or choose an implementation) have more freedom.
A data structure supporting fewer operations can often be more efficient in speed, memory use, or both; or, if you want more operations supported, expect a lower efficiency.