c++ - C++中的动态数组VS链表

Question

<分区>

Answer 1

Dynamic array is an array that resizes itself up or down depending on the number of content.

Advantage:

• accessing and assignment by index is very fast O(1) process, since internally index access is just [address of first member] + [offset].

• appending object (inserting at the end of array) is relatively fast amortized O(1). Same performance characteristic as removing objects at the end of the array. Note: appending and removing objects near the end of array is also known as push and pop.

Disadvantage:

• inserting or removing objects in a random position in a dynamic array is very slow O(n/2), as it must shift (on average) half of the array every time. Especially poor is insertion and removal near the start of the array, as it must copy the whole array.

• Unpredictable performance when insertion or removal requires resizing

• There is a bit of unused space, since dynamic array implementation usually allocates more memory than necessary (since resize is a very slow operation)

Linked List is an object that have a general structure of [head, [tail]], head is the data, and tail is another Linked List. There are many versions of linked list: singular LL, double LL, circular LL, etc.

Advantage:

• fast O(1) insertion and removal at any position in the list, as insertion in linked list is only breaking the list, inserting, and repairing it back together (no need to copy the tails)

• Linked list is a persistent data structure, rather hard to explain in short sentence, see: wiki-link . This advantage allow tail sharing between two linked list. Tail sharing makes it easy to use linked list as copy-on-write data structure.

Disadvantage:

• Slow O(n) index access (random access), since accessing linked list by index means you have to recursively loop over the list.

• poor locality, the memory used for linked list is scattered around in a mess. In contrast with, arrays which uses a contiguous addresses in memory. Arrays (slightly) benefits from processor caching since they are all near each other

Others:

• Due to the nature of linked list, you have to think recursively. Programmers that are not used to recursive functions may have some difficulties in writing algorithms for linked list (or worse they may try to use indexing).

Simply put, when you want to use algorithms that requires random access, forget linked list. When you want to use algorithms that requires heavy insertion and removal, forget arrays.

这个摘自这个question的最佳答案

我对这个答案深信不疑。