5 ms·
"Linked list" usually refers to a very specific structure (regardless of language, or whether it is implemented as pointers or arrays or whatever) - one in whic
by beagle3 9y ago
"Linked list" usually refers to a very specific structure (regardless of language, or whether it is implemented as pointers or arrays or whatever) - one in which to find the middle element you have to traverse at least half the list.
Singly linked list or doubly linked lists are still considered linked lists. Skip lists, even though they technically are lists of linked items, are not generally considered a "linked list" data structure.
- avip 9y agoEven 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.