数据结构与算法中，数组与链表的区别和特点有哪些？

本文共计5232个文字，预计阅读时间需要21分钟。

1. 动态数组：其基本思路是利用malloc/free等内存分配函数得到一块大内存块，通过数组的形式访问这块内存，或直接调用动态数组的接口进行操作，实现自动扩展。

1. 动态数组

　　它的基本思路是使用如malloc/free等内存分配函数得到一个指向一大块内存的指针，以数组的方式引用这块内存或者直接调用动态数组的接口，根据其内部的实现机制自行扩充空间，动态增长并能快速地清空数组，对数据进行排序和遍历。

　　它的数据结构定义如下:

typedef struct { void *data; int capacity; int index; int type_size; int (*comp)(const void *,const void *); } array_t;

• data表示: 指向一块连续内存的指针;type_size: 元素类型的大小(动态执行时才能确定类型)
• capacity: 动态数组的容量大小，最大可用空间 ; index: 动态数组的实际大小
• int (*comp)(const void *,const void *): 元素的大小比较函数,comp为函数指针

2. 链表

　　链式存储是最通用的存储方式之一，它不要求逻辑上的相邻的元素物理位置上相邻，仅通过链接关系建立起来。链表解决了顺序表需要大量的连续存储空间的缺点，但链表附加指针域，也带来了浪费存储空间的缺点。