My Notes icon from iPhone 6 seems to have got either accidentally deleted or somehow disappeared while it was in my pocket with keys etc. I have so many important work notes, and desperately need it. The icon does not show up in spotlight, is not hidden in any other app folder and there was no iCloud backup.
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!