PHP/HTML Agregar Un botón de eliminación

Simplemente puede agregar un botón de envío que vincule a la misma 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>";
  }

Luego, en su página, haga algo como

if (!empty($_POST["delete"])){
     $query = "DELETE FROM links where link = '{$_POST["Delete"]}'";
     mysql_query($query);
}

Esa es la idea básica de cómo lo haría