As a general rule, when choosing a data structure I first consider whether I have strong reasons to believe that performance of the code in question is going to be important:
if I don't, I choose the simplest data structure that would do the job, or the one that lends itself to the clearest code;
if I do, I think carefully about what operations I am going to perform on the structure and choose accordingly, possibly followed by profiling.
It completely depends on which operations you are going to perform on the data structure. If you will be retrieving data by index (eg, data[ 3 ]), then a list is a horrible idea since each read will require you to walk the list. If you will be inserting into the first position a lot (eg, data[ 0 ] = x), then an array will be terrible because you will be moving all the data for each insertion.
If you were going to use std::vector, then a dynamic array is probably the best replacement. But perhaps std::vector would not have been the correct choice.
Static arrays: perfect for lookup tables and data that doesn't change its size throughout the program execution. They get allocated on program startup, so you don't have to manage this memory in any way. A disadvantage is that you cannot resize or free a static array - it stays there until the program terminates.
Dynamically growing arrays: an easy to manage data structure that can almost be a substitute for vector arrays in C++. A disadvantage is the overhead of allocating memory at runtime, but that can be alleviated if you allocate bigger chunks at once.
Linked lists: take care if you are going to have a lot of elements because allocating each one separately without using a memory pool can lead to memory waste and fragmentation.
Vector is a dynamic array and is implemented internally as a dynamic array. I would suggest you to use vector as the machines are optimized to retrieve the continuous memory locations,while the link list will not be stored in continuous location.
Having said that,if you don't require the fast retrieval of element by index in your use case then you can go for link list also.The link list also has a benefit of not wasting the space unlike dynamic array(by doubling when it is about to get full) and also insertion in the start or between the elements is cheaper as compared to array.
在纯 CI 中主要使用静态数组。它与嵌入式设备的编程有关，这些设备在分配和释放内存（堆碎片）方面存在问题。
但如果需要使用列表，我自己实现一个 - 有时它的实现是基于静态数组（再次）。
我认为 C 语言的库可以提供更复杂数据结构的良好实现。 AFAIK glib 被广泛使用并且至少提供了链表。
In pure C I mostly use static arrays. It is connected with programming of embedded devices that have problems with allocating and freeing memory - heap fragmentation.
But if there is a need of using list I implement one myself - sometimes its implementation is based on static arrays (again).
I think there are libraries for C that offer decent implementation of more complex data structures. AFAIK glib is widely used and offers at least linked lists.
额外： 我发现 GNU NSMutableArray (Objective-C) 方法的实现是在 C 中完成的，它们的作用与上面相同。每次必须添加对象并且无法放入数组时，它们都会将数组的大小加倍。请参见第 131 行至第 145 行
I remember I read a document from Apple some time ago saying that such a thing could be naively implemented with a structure similar to:
struct {
void *data; //other type rather than void is easier
int length;
} MyArray;
MyArray *MyArrayCreate(){
//mallocate memory
return ...
}
void MyArrayRelease(){
free(...);
}
And implement a function that checks the length of the array and its not long enough then another big enough array will be allocated, former data will be copied to it and new data added to it.
MyArrayInsertAt(MyArray *array, index, void *object){
if (length < index){
//mallocate again, copy data
//update length
}
data[index] = object;
}
MyArrayInsertAt() function won't win a price for its performance, but it could be a solution for no high-demanding programs/applications
I just can't find the link... maybe someone read it too?
ADDED: I have found that GNU NSMutableArray (Objective-C) methods implementation are done in C and they do the same as above. They double the size of the array each time an object has to be added and won't fit in the array. See line 131 through 145
发布评论
评论（7）
不同的数据结构为插入、查找和其他操作提供不同的计算复杂度。
举个具体的例子，数组和链表之间有很多区别：
O(1)，而在数组中按索引查找是O(n)在列表中；O(1)或O(n)（取决于它们是否需要遍历），插入数组的时间为O(1)如果做得好；O(n)，而某些类型的列表删除可以在O(1)时间内完成；您可能会发现以下页面很有用： http://essays.hexapodia.net/datastructs/
作为一般规则是，在选择数据结构时，我首先考虑是否有充分的理由相信相关代码的性能很重要：
至于好的 C 数据结构库的建议，请查看 有没有通用数据结构的开源C库？
Different data structures offer different computational complexity for insertions, lookups and other operations.
To take your specific example, there is a number of differences between an array and a linked list:
O(1)in an array andO(n)in a list;O(1)orO(n)(depending on whether they require traversal), and into an array are amortizedO(1)if done well;O(n)whereas certain types of list deletions can be done inO(1)time;You might find the following page useful: http://essays.hexapodia.net/datastructures/
As a general rule, when choosing a data structure I first consider whether I have strong reasons to believe that performance of the code in question is going to be important:
As for recommendations for good C data structure libraries, take a look at Are there any open source C libraries with common data structures?
这完全取决于您要对数据结构执行哪些操作。如果您将通过索引检索数据（例如，data[3]），那么列表是一个可怕的想法，因为每次读取都需要您遍历列表。如果您要多次插入第一个位置（例如，data[0] = x），那么数组将很糟糕，因为每次插入都会移动所有数据。
如果您打算使用 std::vector，那么动态数组可能是最好的替代品。但也许 std::vector 不是正确的选择。
It completely depends on which operations you are going to perform on the data structure. If you will be retrieving data by index (eg, data[ 3 ]), then a list is a horrible idea since each read will require you to walk the list. If you will be inserting into the first position a lot (eg, data[ 0 ] = x), then an array will be terrible because you will be moving all the data for each insertion.
If you were going to use std::vector, then a dynamic array is probably the best replacement. But perhaps std::vector would not have been the correct choice.
每个都有自己的优点和缺点。
静态数组：非常适合查找表和在程序执行过程中不会改变其大小的数据。它们在程序启动时分配，因此您不必以任何方式管理该内存。缺点是您无法调整或释放静态数组的大小 - 它会一直保留在那里，直到程序终止。
动态增长数组：一种易于管理的数据结构，几乎可以替代 C++ 中的向量数组。缺点是在运行时分配内存的开销，但如果一次分配更大的块，则可以减轻这种开销。
链接列表：如果您要拥有大量元素，请小心，因为在不使用内存池的情况下单独分配每个元素可能会导致内存浪费和碎片。
Each has its own advantages and disadvantages.
Static arrays: perfect for lookup tables and data that doesn't change its size throughout the program execution. They get allocated on program startup, so you don't have to manage this memory in any way. A disadvantage is that you cannot resize or free a static array - it stays there until the program terminates.
Dynamically growing arrays: an easy to manage data structure that can almost be a substitute for vector arrays in C++. A disadvantage is the overhead of allocating memory at runtime, but that can be alleviated if you allocate bigger chunks at once.
Linked lists: take care if you are going to have a lot of elements because allocating each one separately without using a memory pool can lead to memory waste and fragmentation.
动态链接列表广泛用于 C 语言，其中要存储的项目数量未知。
Dynamic Link lists are widely used in C where number of items to be stored is not known.
Vector是一个动态数组，并且在内部实现为动态数组。我建议您使用向量，因为机器经过优化以检索连续内存位置，而链接列表不会存储在连续位置。
话虽如此，如果您不需要在用例中通过索引快速检索元素，那么您也可以使用链接列表。与动态数组不同，链接列表还有一个优点，即不浪费空间（通过在它时加倍）即将满），并且与数组相比，在开头或元素之间插入也更便宜。
Vector is a dynamic array and is implemented internally as a dynamic array. I would suggest you to use vector as the machines are optimized to retrieve the continuous memory locations,while the link list will not be stored in continuous location.
Having said that,if you don't require the fast retrieval of element by index in your use case then you can go for link list also.The link list also has a benefit of not wasting the space unlike dynamic array(by doubling when it is about to get full) and also insertion in the start or between the elements is cheaper as compared to array.
在纯 CI 中主要使用静态数组。它与嵌入式设备的编程有关，这些设备在分配和释放内存（堆碎片）方面存在问题。
但如果需要使用列表，我自己实现一个 - 有时它的实现是基于静态数组（再次）。
我认为 C 语言的库可以提供更复杂数据结构的良好实现。 AFAIK glib 被广泛使用并且至少提供了链表。
In pure C I mostly use static arrays. It is connected with programming of embedded devices that have problems with allocating and freeing memory - heap fragmentation.
But if there is a need of using list I implement one myself - sometimes its implementation is based on static arrays (again).
I think there are libraries for C that offer decent implementation of more complex data structures. AFAIK glib is widely used and offers at least linked lists.
我记得我前段时间读过苹果的一份文档，说这样的事情可以用类似于以下的结构来简单地实现：
并实现一个检查数组长度的函数，如果它不够长，那么将分配另一个足够大的数组，以前的数据将被复制到其中，新数据将添加到其中。
所以它可以像这样使用：
MyArrayInsertAt() 函数不会因其性能而赢得价格，但它可能是没有高要求的程序/应用程序的解决方案
我只是找不到链接......也许有人读过它也？
额外：
我发现 GNU NSMutableArray (Objective-C) 方法的实现是在 C 中完成的，它们的作用与上面相同。每次必须添加对象并且无法放入数组时，它们都会将数组的大小加倍。请参见第 131 行至第 145 行
I remember I read a document from Apple some time ago saying that such a thing could be naively implemented with a structure similar to:
And implement a function that checks the length of the array and its not long enough then another big enough array will be allocated, former data will be copied to it and new data added to it.
So it can used like so:
MyArrayInsertAt() function won't win a price for its performance, but it could be a solution for no high-demanding programs/applications
I just can't find the link... maybe someone read it too?
ADDED:
I have found that GNU NSMutableArray (Objective-C) methods implementation are done in C and they do the same as above. They double the size of the array each time an object has to be added and won't fit in the array. See line 131 through 145