You'll probably just want to build your hash as a circular linked list:

my $position_of = (
      'A' =>  {
               next_key => 'A#',
               prev_key => 'G#',
               #  other stuff . . .
              },
      'A#' => {
               next_key => 'B',
               prev_key => 'A',
               #  other stuff . . .
              },
       ### in-between stuff
      'G#' => {
               next_key => 'A',
               prev_key => 'G',
               #  other stuff . . .
              },
);
[download]

Update: with circular linked lists you usually keep track of head/tail:

my $head = 'A';
my $tail = 'G#';
[download]

--Jim