I have a web site using PHP and a database that stores a list of
several hundred song titles alphabetically.  The same song may be
listed in the array 10 times (for different versions), and some letters of
the alphabet (or numerals even) may have no songs that start with that
letter (like Q or X or Z).

Currently, I have in memory the array of all songs in my list, split
into multiple pages of 25 records each.  I know how many pages there
are, which page number I'm currently on, and also the
first/last/next/previous page numbers.

What I WANT to do is have a row of letters at the top that the user
will click on, and that will take him/her to the page that has the
titles starting with that letter:

1 7 A B C G H J L M N V Y

The row might have letters missing (because if you don't have any
songs that start with 'X' I don't want to take you to a wrong/dead
page.

Also, clicking on the letter will not simply do a new query for all
the songs with that letter (that's the easy way and not what I want). 
Instead, it should only take you to the page that contains songs
starting with that letter.  So, clicking on the letter "Y" might
actually have songs that also start with the letter "V".

Simple enough?  How do you do this?  Do I just have to run through the
array 26 times?  I just need the concept and maybe some pseudo-code if
necessary.