If it is lost it and its info is gone, unless you had it backed up somewhere off the device (google, computer, etc.), then you can get the info there. If not, then they are gone with the phone.
You can try checking your bill (paper or online in your account with your carrier/service provider) and get phone numbers from it. But no names, so you would have to check for say dates and times of the contacts to estimate what number is for who.