Linked lists are only useful in very few situations and this is not one of them.

I've been terrified of linked structures since I saw a video (I think it was here) from a C++ conference talking about how horrible their performance is.

You could keep pointers to both the head and tail in the list object though. Then adding and removing stuff would be O(1) for both ends.

Yep, and that used to be idiomatic, years and years ago when people still wrote their own linked lists. I'd be surprised if it isn't still the standard behavior for that data structure.