If that's a specific use case you need to handle, it's O(1) again if you have a pointer to both the node to be removed and the previous node.

Whether it's more efficient to carry a second pointer around when manipulating the list, or store a second pointer in every list node (aka double linked list) is up to your problem space.

Or whether an O(n) removal is acceptable.

Getting the pointer to that element means randomly hopping around the heap to traverse the list though.

Linked lists are perfect for inserting/deleting nodes, as long as you never need to traverse the list or access any specific node.

You’re assuming no other data structure points to the element. It may. Example: implement a cache.

Each element is: key, value, linked list node for hash table bucket, linked list node for LRU. Hash table to look up element. Element is both a member of hash table and of linked list. Linked list is used as LRU for feeling memory when needed.

LRU never traversed but often needs removal and reinsertion.