开始便想到了洲哥奇葩的期中考试中的“给定常量M”……

链表出现的主要意义第一是满足元素个数没有明确上限的时候，使用动态内存分配来满足程序的需求。其次是因为数组对插入、删除、移动操作的时间复杂度较高，因此采用链表来实现。

数组与链表的复杂度比较

	数组	链表
遍历	O(n)	O(n)
查找	O(log n)(二分)	O(n)
插入、删除、移动	O(n)	O(1)

可见，在查找次数比较多的时候使用数组，在插入、删除次数比较多的时候使用链表。