Contact list is gone. Was not saved in iCloud.

When you look deeply you will find that Contacts are neither stored on an iPhone nor on SIM. They are synced to an email account that you may have added and enabled Contacts. It could be Google, iCloud, AOL, Exchange, Outlook, Yahoo or any Other email client server.

When you enable Contacts in any of the email accounts they are displayed to you through the Contacts App. When you edit these contacts on an iPhone they are ultimately edited on the client-server.

Please see the pic below for a better understanding...

If you are unable to find your contacts which were stored in the email client, then try this --> Restore contacts, calendars, bookmarks, and more using ...

Check if the email account has been removed from the iOS mail app.

Add the email account that stores your contacts in the IOS mail app and enable Contacts.

What is your default Contacts account? If none, please add an email account and enable contacts.

See the pic below

Unlike some Android devices, contacts are neither stored locally on an iPhone nor in SIM. They are synced to an email account that you had Google, iCloud, AOL, Exchange, Outlook, Yahoo or any Other

If you have a corporate email account added through a profile on your device, please check with your organization's system administrator.