When you started your phone for the first time, it should have prompted you to link it with your Google account. I'm not sure how easily a person can skip that step, so chances are you did have your phone linked to Google. The main question is which account did you enter all of your contacts on your phone--the Phone Account or the Google Account. If you have a Google account, go to Google Contacts (
Redirecting...) and log in. Do you see all of your contacts there? If so, then you should be able to re-sync all of your contacts.
The reason there wasn't a double confirmation when you deleted the contacts is probably because you were in the Settings/Apps menu, looking at the App Info. Although I believe there actually is a caution when you tap "Clear Data" that you may lose important information. In any case, if you're a novice at Android, I strongly caution against deleting anything unless you know for certain it isn't important.
I'm not aware of any easy way to retrieve deleted contacts from the Phone Account, but if you do a web search for "samsung galaxy recover deleted contacts," you'll find a number of possible solutions. These usually involve purchasing a program or app. Publishers of this kind of software tend to spam this and other forums a lot, so I would be cautious proceeding with any of them, since there could always be some risk for malware.