How to get back all notes when Notes icon disappeared or the Notes.app got deleted
Have you attempted to go on the App Store and look for Notes by Apple? It will be there (the Notes app by Apple). If it just shows "Open" instead of (arrow pointing down from the Cloud), then you do have it on your iPhone, just hidden away "somewhere". You can use Spotlight to find it (drag down slightly below the top (not so high that you activate the Notification Center) and type in Notes.

As regards losing all your info by deleting an Apple default app - a friend of mine removed his Mail app on his iPhone by accident and panicked, thinking he had lost all his Mails, Mail settings etc.

He brought the iPhone in and I went to the AppStore, clicked download on the Mail app there (the correct one), and all the settings reappeared and everything was alright.

Tell us how you get on with this project and good luck!