Complexity Classes for a List

Question

Why is it that for removing something from an array or vector is O(n) complex but when removing something from a list it is O(1) complexity?

Do you know how vectors and lists work? If not I would recommend getting a [good C++ book](http://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list) — David Brown, Nov 18 '13 at 20:34

score 2 · Accepted Answer · answered Nov 18 '13 at 20:34

2

When you remove an item from a vector and it is not on last position, you have to move all the subsequent elements one position to the left. This happens because a requirement for vector is that all of its elements form a continuous block of memory and so you can not have 'holes'. For list there is no requirement for the order in which elements are stored in memory and so no moving is required after deleting an element.

answered Nov 18 '13 at 20:34

Ivaylo Strandjev

69,226
18
123
176

so to go off on that, when you remove from the middle of a deque, you also have to shift the elements and the pointers which is why removing from deque is also O(n) complex – DebareDaDauntless Nov 18 '13 at 20:37
again a deque would store the elements in a continuous block of memory, so whenever you delete an element somewhere in the middle you will have to move either the elements preceding or the elements succeeding it. – Ivaylo Strandjev Nov 18 '13 at 20:39
@user2521432 That depends on the implementation of the deque you use. – Zac Howland Nov 18 '13 at 20:40
2

@user2521432 note: unlike a vector, removing and inserting from *either* end of a [`std::deque`](http://en.cppreference.com/w/cpp/container/deque) is O(1). A vector only gets that benefit at the end; not at the beginning. *Both* exhibit O(n) for insertions and removals mid-sequence. – WhozCraig Nov 18 '13 at 20:40
@WhozCraig I can't check the C++11 spec at this work location, but IIRC, doesn't `std::deque` specify that it would be *at worst* O(n) for insertions and removals mid-sequence? It would be possible for you to implement a deque that is essentially a linked list, and would have O(1) for insertions and removals mid sequence. – Zac Howland Nov 18 '13 at 20:48
@ZacHowland I believe according to specification random access should be constant in deque which will not be true if you implement it using list. However I think you could use tiered vector for instance and get a better than O(N) complexity for mid removal – Ivaylo Strandjev Nov 18 '13 at 20:50
@ZacHowland Most deques in standard libs I've perused use paging to store expansion in both directions `[..xxx][xxxxx][xxxxx][xxx..]` with the deque linking the pages via an index table and knowing how many elements are in the first and last page can get you anywhere. Obviously the implementations can do their own bidding, and with each, different performance is plausible, but *all* the conditions must be met. If you implement a deque as a pure linked list, you hosed the random-access in O(1) requirement. At *best* paging reduces O(N) to O(N/p) where p is the page size; still O(N) – WhozCraig Nov 18 '13 at 21:14
@WhozCraig But if you set the page size to 1 (so you end up with a list of vectors with size 1), with the index table still there, removing an element is effectively removing a page from the list - which would be O(1). Your indexing table would be a hefty overhead, but you theoretically could implement it this way and meet the requirements of the standard (unless I'm missing something - sadly I have to go completely off memory right now). – Zac Howland Nov 18 '13 at 21:20
@ZacHowland At that point you have an array implemented purely as an indirect index table, and have moved the move-sub-N items problem (the root of O(N)) from the data pages to the index. There isn't any way to get around this, try as you might. – WhozCraig Nov 18 '13 at 21:23
@WhozCraig I think you misunderstood what I was asking. Most implementations of `std::deque` utilize an index table, and a list of "vectors" (term used loosely) called pages. To get O(1) access time, the index table tells you which list the element is in, and then you have a "vector" with random access in constant time (that is, you have 2 operations with constant time). If you set the page size to 1, you have an indexed linked list. I don't recall any requirement that forced the index to be implemented as a vector itself (e.g. could it be a hash?). – Zac Howland Nov 18 '13 at 22:30
@ZacHowland You just described, nearly verbatim, everything I did regarding how most deques are implemented, three comments ago. There's no requirement that it be implemented as indexed pages, much less that said-index is a vector. Again, if you *are* using an index and you reduce the page size to one, all you've done is move the N to the index rather than the pages. *You still have to maintain the index*. Slice it however you want to, we're not getting O(1) universal insertion (ends and internal) *and* O(1) random access. A page size of one just moves the problem to the index mgmt side. – WhozCraig Nov 18 '13 at 22:56
@ZacHowland ...continued. But that said, by all means, link up an implementation that grants O(1) universal insertion/deletion *and* O(1) random access in a deque, as I'm sure I can find a use for it. – WhozCraig Nov 18 '13 at 22:58
@WhozCraig "You still have to maintain the index." Hence my question. Why does the index maintenance *have* to be O(n)? – Zac Howland Nov 18 '13 at 23:02

Zac Howland · Answer 2 · 2013-11-18T20:46:06.823

A list stores pointers to the next and previous entries. So if you want to remove element (where you already have the iterator/pointer to it), it is simply a matter of updating 2 pointers and deleting the memory. A vector stores memory contiguously, so when you remove an element, it has to move all of the elements after it to a new memory location (the best case is removing the last element - no items need to be moved; the worst case is removing the first element - all other items need to be moved).

List Operations

x->prev->next = x->next;
x->next->prev = x->prev;
delete x;

Vector Operations

for x to size - 1
    copy next memory block to previous

score 0 · Answer 3 · answered Nov 18 '13 at 20:35

When you remove an item from an array (arrays and vectors use contiguous memory), the rest of the array needs to moved. That's O(N). In lists, each list item points to the next and previous so unlinking an item is done in O(1) - regardless of the list length.

Complexity Classes for a List

3 Answers3