3 ms·
Even ignoring "implementation details", insertion at head/tail would be O(1). Why would you traverse the list to insert an item?
by avip 9y ago
Even ignoring "implementation details", insertion at head/tail would be O(1). Why would you traverse the list to insert an item?
- beagle3 9y agoBut average case or worst case are in the middle (for a doubly linked list) or the end (a singly linked list without a tail pointer).
- avip 9y agoThere's no "worse case" for insertion if the api just says list.insert(item). The half-trollish point being that nothing is "obvious". Indeed, list insertion is O(1) in popular programming languages s.a python or JS.