4 ms·

there's no "time complexity" associated with inserting an item to an abstract linked list. The answer varies with implementation. Any answer <= O(n) could be co

• 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 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 ago
      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).
      • avip 9y ago
        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.