如何修改O(n)列表长度函数以在O(1)中运行？

Question

从这个链接,是ilist.c文件的副本 http://www.student.cs.uwaterloo.ca/~cs136/assignments/a5/

我需要做的是如何将此O(n)函数转换为在O(1)中运行:

// computes the number of elements in il
int ilength(ilist il)
{
    int i = 0;
    while (!iempty_huh(il))
    {
        i++;
        il = irest(il);
    }
    return i;
}

我可以编辑ilist.c文件中的函数(我假设结构和图标)但我无法编辑ilist.h文件.我根本不知道如何处理转换为O(1),任何想法都会有所帮助!

Answer 1

您可以将列表中元素的数量存储在与其关联的对象中,使用每个添加的元素增加它,并使用每个已删除的元素减少它.然后,如果请求列表的总长度,则只返回该数字.

我没有看到任何其他方式这样做.遍历链表始终需要O(n).