学步园

转载时请注明出处和作者联系方式
文章出处：http://www.limodev.cn/blog
作者联系方式：李先静 <xianjimli at hotmail dot com>

对比双向链表和动态数组

在C语言中，数组的长度是事先确定的，不能在运行时动态调整。所谓动态数组就是它的长度可以根据存储数据多少自动调整，这需要我们用程序来实现。对比双向链表和动态数组，我们会发现：

o 动态数组本身占用一块连续的内存，而双向链表的每个结点要占用一块内存。在频繁增删数据的情况下，双向链表更容易造成内存碎片，具体影响与内存管理器的好坏有关。

o 动态数组的增删操作需要移动后面的元素，而双向链表只需要修改前后元素的指针。在存储大量数据的情况下，这种差异更为明显。

o 动态数组支持多种高效的排序算法，像快速排序、归并排序和堆排序等等，而这些算法在双向链表中的表现并不好，甚至不如冒泡排序来得快。

o 排序好的动态数组可以使用二分查找，而排序好的双向链表仍然只能使用顺序查找。主要原因是双向链表不支持随机定位，定位中间结点时只能一个一个的移动指针。

o 对于小量数据，使用动态数组还是双向链表没有多大区别，使用哪个只看个人的喜好了。

实现动态数组

在考虑存值还是指针时，我们同样选择存指针，所以这里我们实现的是指针数组。动态数组的功能和双向链表非常类似，所以它对外的接口也是类似的：

struct _DArray;
typedef struct _DArray DArray;

DArray* darray_create(DataDestroyFunc data_destroy, void* ctx);

Ret    darray_insert(DArray* thiz, size_t index, void* data);
Ret    darray_prepend(DArray* thiz, void* data);
Ret    darray_append(DArray* thiz, void* data);
Ret    darray_delete(DArray* thiz, size_t index);
Ret    darray_get_by_index(DArray* thiz, size_t index, void** data);
Ret    darray_set_by_index(DArray* thiz, size_t index, void* data);
size_t  darray_length(DArray* thiz);
int    darray_find(DArray* thiz, DataCompareFunc cmp, void* ctx);
Ret    darray_foreach(DArray* thiz, DataVisitFunc visit, void* ctx);

void darray_destroy(DArray* thiz);

动态数组的动态性如何实现了呢？其实很简单，借助标准C的内存管理函数realloc，我们可以轻易改变数组的长度。函数realloc是比较费时
的，如果每插入/删除一个元素就要realloc一次，不但会带来性能的下降，而且可能造成内存碎片。为了解决这个问题，需要使用一个称为预先分配的惯用
手法，预先分配实际上是用空间换时间的典型应用，下面我们看看它的实现：

扩展空间

在扩展数组时，不是一次扩展一个元素，而是一次扩展多个元素。至于应该扩展多少个，经验数据是扩展为现有元素个数的1.5倍。

#define MIN_PRE_ALLOCATE_NR 10
static Ret darray_expand(DArray* thiz, size_t need)
{
    return_val_if_fail(thiz != NULL, RET_INVALID_PARAMS);

    if((thiz->size + need) > thiz->alloc_size)
    {
        size_t alloc_size = thiz->alloc_size + (thiz->alloc_size>>1) + MIN_PRE_ALLOCATE_NR;

        void** data = (void**)realloc(thiz->data, sizeof(void*) * alloc_size);
        if(data != NULL)
        {
            thiz->data = data;
            thiz->alloc_size = alloc_size;
        }
    }

    return ((thiz->size + need) <= thiz->alloc_size) ? RET_OK : RET_FAIL;
}

Ret darray_insert(DArray* thiz, size_t index, void* data)
{
    Ret ret = RET_OOM;
    size_t cursor = index;
    return_val_if_fail(thiz != NULL, RET_INVALID_PARAMS);

    cursor = cursor < thiz->size ? cursor : thiz->size;

    if(darray_expand(thiz, 1) == RET_OK)
    {
        size_t i = 0;
        for(i = thiz->size; i > cursor; i--)
        {
            thiz->data[i] = thiz->data[i-1];
        }

        thiz->data[cursor] = data;
        thiz->size++;

        ret = RET_OK;
    }

    return ret;
}

扩展的大小由下列公式得出：

size_t alloc_size = (thiz->alloc_size + thiz->alloc_size>>1) + MIN_PRE_ALLOCATE_NR;

计算1.5*thiz->alloc_size时，我们不使用1.5 * thiz->alloc_size，因为这样存在浮点数计算，在大多数嵌入式平台中，都没有硬件浮点数计算的支持，浮点数的计算比定点数的计算要慢上百倍。

我们也不使用thiz->alloc_size+ thiz->alloc_size/2，如果编译器不做优化，除法指令也是比较慢的操作，特别是像在ARM这种没有除法指令的芯片中，需要很多条指令才能实现除法的计算。

这里我们使用(thiz->alloc_size + thiz->alloc_size>>1)，这是最快的方法。后面加上MIN_PRE_ALLOCATE_NR的原因是避免thiz->alloc_size为0时存在的错误。

减小空间

在删除元素时也不是马上释放空闲空间，而是等到空闲空间高于某个值时才释放它们。这里我们的做法时，空闲空间多于有效空间一倍时，将总空间调整为有效空间的1.5倍。

static Ret darray_shrink(DArray* thiz)
{
    return_val_if_fail(thiz != NULL, RET_INVALID_PARAMS);

    if((thiz->size < (thiz->alloc_size >> 1)) && (thiz->alloc_size > MIN_PRE_ALLOCATE_NR))
    {
        size_t alloc_size = thiz->size + (thiz->size >> 1);

        void** data = (void**)realloc(thiz->data, sizeof(void*) * alloc_size);
        if(data != NULL)
        {
            thiz->data = data;
            thiz->alloc_size = alloc_size;
        }
    }

    return RET_OK;
}

Ret darray_delete(DArray* thiz, size_t index)
{
    size_t i = 0;
    Ret ret = RET_OK;

    return_val_if_fail(thiz != NULL && thiz->size > index, RET_INVALID_PARAMS);

    darray_destroy_data(thiz, thiz->data[index]);
    for(i = index; (i+1) < thiz->size; i++)
    {
        thiz->data[i] = thiz->data[i+1];
    }
    thiz->size--;

    darray_shrink(thiz);

    return RET_OK;
}

为了避免极端情况下的出现频繁resize的情况，在总空间小于等于MIN_PRE_ALLOCATE_NR时，我们不减少空间的大小。

本节的示例请到这里下载。