3 ms·

Premature optimization is the root of all evil, but removing from the beginning of any array-based growable structure rather than the beginning will turn a O(n)

• danieldk 15y ago
  but removing from the beginning of any array-based growable structure rather than the beginning will turn a O(n) operation into an O(n^2) operation. I'll bite: in arrays, front deletion (like back deletion) can be done in O(1) time. Keep a pointer to the first element, and just increment it upon front deletion (and free the element if necessary). Obviously, you may want to be smart to avoid memory use getting out of hand. And you don't know what's going into those tabs. If the array stores references (pointers), which you'd expect with tabs, that is orthogonal to the discussion. Whatever is going into those tabs, a pointer is a pointer.
  • xentronium 15y ago
    > I'll bite: in arrays, front deletion (like back deletion) can be done in O(1) time. Keep a pointer to the first element, and just increment it upon front deletion (and free the element if necessary). Obviously, you may want to be smart to avoid memory use getting out of hand. Actually that's how they often do array-based queues and deques. To help with memory use they let the tail pointer overflow through the end (so you could have tail at index 2 and head at index 8).