It makes sense to have EDIT + DELETE (may be even DETAILS) actions associated with each row in the list, so that it's clear to the user what action they can perform on the individual line item.
But ADD NEW action should always be at the top of the list (preferably on the top right corner with a descriptive icon next to it, for eg, a PLUS sign).
Check out this data tables page here - http://editor.datatables.net/release/DataTables/extras/Editor/examples/inlineControls.html
As you can see from the screenshot below, the action items are placed at the appropriate locations where it makes sense for the user to act on.
And when the user clicks on the button/link (EDIT or ADD NEW), a modal popup is one of the several ways to display a form to capture the user input. The fields would be empty for adding a new entity or populated with existing values when editing an entity.
The submit button that saves the record can be named "SAVE" if you want it to be common for both update and add actions. Or if you want to be more specific, you can call it "ADD" for new records and "UPDATE" for existing records.