Você pode simplesmente adicionar um botão de envio com link para a mesma página, como
while ($row = mysql_fetch_array($result)) { //loop
extract($row);
$html .= "<li><span style=\"font-family: verdana;\"><a href=\"{$link}\" target=\"_blank\">{$link}</a> <form action=\"{$_SERVER["PHP_SELF"]}\" method=\"post\">
<input type=\"hidden\" value=\"{link}\" name=\"Delete\" />
<input type=\"submit\" value=\"Delete\" />
</form></span> <span style=\"color:white; font-family: verdana;\">- {$notes}</span></li>";
}
Então na sua página faça algo como
if (!empty($_POST["delete"])){
$query = "DELETE FROM links where link = '{$_POST["Delete"]}'";
mysql_query($query);
}
Essa é a ideia básica de como eu faria