This is a good answer, but it fails to point the first element "back" to the last, and the last "forward" to the first. Here's one way to do that:

my %nxt;
my %prev;

my $prv;
my $first;
for (sort { $a <=> $b } keys %hash) {
  $first ||= $_;
  if (defined $prv) {
    $nxt{$prv} = $_;
    $prev{$_} = $prv;
  }
  $prv = $_;
}

$nxt{$prv}=$first;
$prev{$first}=$prv;