Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

Even ignoring "implementation details", insertion at head/tail would be O(1). Why would you traverse the list to insert an item?


But 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).


There'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.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: