链表的优势：

• 数组大小固定，链表大小可轻易扩展。
• 数组的插入、删除需要将元素移动(shift)，而链表不用。(当然，可以将数组中被删除的位置设置为特殊值，标记为“已删除”)

链表的劣势：

• 链表无随机访问，只能顺序访问
• 链表需要额外的空间来存储指针
• 数组的缓存局部性比链表好，因为所有内容都存储在邻近的位置

遇到需要更新链表头结点的情况，例如在链表的头部插入一个新结点，要如何更新链表的head结点呢？

• （不推荐）令head为全局变量
• （推荐）让所有可能修改head结点的函数，返回head结点，这样用户调用时需要这样：head = list_insert(head, xxx);
• 使用指针修改head变量，如：list_insert(struct Node **head_p, xxxxx);

使用malloc或new之类的方法，从堆里动态分配空间的数组。虽然数组大小不需要在编译时就决定，但是一次分配后，数组的大小仍然是不可变得，除非realloc。

在嵌入式系统中，有时不能像普通程序那样频繁调用malloc以产生新的链表结点(例如由于malloc耗时较长)。这时我们可以用数组来模拟链表:

struct ListNode {
        int data;
        int next;       // 下一个结点在数组中的下标
};

ListNode list[100];     // 拥有100个结点的链表，插入时就从其中寻找一个未使用的结点

我们可以设置一个变量struct ListNode *head来保存链表的头结点。

每次插入时，我们都从list数组中找到一个空结点（还没用过的结点），将其加入到链表中。那么如何快速找到空的结点呢？遍历整个list数组，当然可以找到空的结点，但这需要O(s)的时间复杂度，s为数组list的大小。有一种更巧妙的方法是，将所有空结点连接起来，形成一个空结点链表，其头结点为struct ListNode *empty。每次需要空结点时，就取用empty链表的第一个结点，并让empty前进一位。如果empty链表一个结点都没有，说明链表已满。