很多编程语言的标准库中都实现了很多数据结构，方便开发者快速上手，避免重复造轮子，例如Java中的XXXList，Go的slice以及container包中的list包。他们大多是基于数组与链表这两个基本数据结构的封装，也是两种不同的数据存储方式，这两种数据结构究竟有何异同？

数组

在内存中，数组由一段连续的内存组成，且长度固定，如图所示。

查找元素

在C语言中，数组名保存着数组的首地址，如果是一个int型数组，每个元素占4字节，若起始地址base == 200，则第i个元素的起始地址为200 + 4 * i，数组中的任何一个元素的位置都可以这样计算出来，与元素个数无关，时间复杂度为O(1)。

增删元素

从长度为 N 的数组中删除或者插入位于 i 的元素，我们需要移动（N – i）个元素，在这个过程中，定位的时间复杂度为O(1)，相当于一次查找，定位后，我们需要执行（N – i）次写入操作，来调整位置，时间复杂度为O(N)。

如果在末尾插入一个元素，并且超出数组的空间大小时，需要重新申请一块更大的内存，所需空间复杂度更高。

链表

在内存中，链表由多个分散在不同位置的节点组成，每个节点保存其元素与下一个节点的位置，因此链表的大小不是固定的，与元素的个数相应，不会像数组那样分大了浪费，分小了容易溢出，因为每个节点多出一个保存地址的空间，存储相同数量的元素，其空间复杂度大约是数组的二倍。

查找元素

我们只知道每个链表头节点的位置，所以如果要找到第i个元素，需要执行i次listNode = listNode->next的操作，时间复杂度为O(N)，这一点并不如数组来的快。

增删元素

与查找一样，我们依旧需要执行一次时间复杂度为O(N)的定位操作之后，再执行一个操作即可完成链表的增删元素。

例如:

void DelAnyToList(ListNode *listNode, int loca)
{
    for (int i = 1; i < loca; i++)
    {
        if (listNode->next == NULL)
        {
            cout<<"DelAnyToList Error loca more long than List"<<endl;
            return;
        }
        listNode = listNode->next; 
    }
    ListNode* delNode = listNode->next;
    listNode->next = listNode->next->next;

    delete delNode;    
}

但是，对于在某个位置多次插入元素，链表相对于数组的整体迁移，时间复杂度低很多，因为只需要定位到要插入的位置，之后的操作就都是O(1)了。不过一般情况下，数组与链表的插入删除操作可以说是各有优势。如果链表与其他数据结构搭配使用，例如哈希表，来存储链表中每个位置的指针。这样，我们可以直接访问要插入删除的元素，而不需要遍历整个链表，相对于数组拥有更大的优势。

总结

本篇文章尚不严谨，没想到会越写越疑惑，关于更详细的研究，感觉得再想想。

在查询比较多的场景中，我们要尽量使用数组，而在添加和删除操作比较多时，我们应该使用链表结构