Tag: 数据结构

普及向——链表初步(C向)

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

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







数组与链表的复杂度比较
数组 链表
遍历 O(n) O(n)
查找 O(log n)(二分) O(n)
插入、删除、移动 O(n) O(1)

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