Implement and lightly test headnode_delete

Can you explain why this was removed?