If you don't have a data connection then it's fine to give location data to an application because there's nowhere it can send it. With properly designed APIs, the app shouldn't be able to store the location data either, only display it to the user by calling the map API.
Location can, and is, stored in the local device and uploaded when connected. Location data is tiny compared to something like video.
All apps can store data because most need to store data if just for settings and cached. Especially any offline navigation app. There is a difference between app storage and general storage.
If you don't give the location data to the application, how is it going to do navigation, finding restaurants near you, and all other similar features?
