题10

题10

题目

在一个长度为 的带头结点的单链表 上，设有尾指针 ，则执行 ( ) 操作与链表的表长有关.
A. 删除单链表中的第一个元素
B. 删除单链表中的最后一个元素
C. 在单链表第一个元素前插入一个新元素
D. 在单链表最后一个元素后插入一个新元素

分析

尾指针 ,使其始终指向当前链表的尾结点

有尾指针，可以直接定位到最后一个元素
要删除最后一个元素的话，需要把尾指针往回找一个，但是单链表是没有往回找这个能力的，还是需要遍历到最后一个节点的前驱那里去

解

B
删除单链表的最后一个结点需置其前驱结点的指针域为 NULL, 需要从头开始依次遍历找到该前驱结点,需要 的时间,与表长有关。其他操作均与表长无关,读者可自行模拟。