Slightly simplified & loops through all the links on the first page :

    import re, youtube_dl
    from bs4 import BeautifulSoup
    from urllib2 import urlopen
    from urllib import quote_plus

    ydl_opts = {}

    soup = BeautifulSoup(urlopen('https://www.youtube.com/results?search_query=' + quote_plus('linkin')).read())
    links = soup.find_all('a', href=re.compile(r'watch\?v='), class_='yt-uix-tile-link')
    
    for i, link in enumerate(links):
        print i+1, '-', link.text

    choice = int(raw_input("Select song index : "))

    with youtube_dl.YoutubeDL(ydl_opts) as ydl:
        ydl.download(['http://www.youtube.com/' + links[choice-1].get('href')])