Ipod and Recycle Bin

So, I was stupid in thinking that after I uploaded my songs to my iPod from
itunes, that I could just delete them of of itunes so it wouldn't slow my
computer down so much. I went to add more songs and it deleted my other songs
from it..

I went to Recycle Bin and restored all of the music files but I have no idea
where they went and I want to get them back on my iPod without having to put
in all my CD's and go through the process again.

What should I do?