深圳23考研寄宿暑期集训营报名开始啦
来源:深圳社科赛斯考研培训学校
时间:2022/4/8 14:38:16
408计算机专业课,要复习的内容较多!为了帮助考生巩固专业知识,深圳社科赛斯考研小编特意为大家给出-考研计算机知识点:链表的运算效率,供考生参考。
2023考研计算机知识点:链表的运算效率
1.查找
因线性链表只能顺序存取,即在查找时要从头指针找起,查找的时间复杂度为 O(n)。
2.插入和删除
因线性链表不需要移动元素,只要修改指针,一般情况下时间复杂度为 O(1)。
但是,如果要在单链表中进行前插或删除操作,因为要从头查找前驱结点,所耗时间复杂度将是 O(n)。
例:在n个结点的单链表中要删除已知结点*P,需找到它的前驱结点的地址,其时间复杂度为 O(n)