> I actually have 2 questions about this one: > > Can we assume that we have any "tools" with us when we > enter the linked list? E.g. a pointer, a vector or > something of the like? I guess what I want to know is > when does the O(1) constraint take affect. When we > hit the list and start to analyze, we cannot create > any thing that will add to the space. Or, can we > create a tool that we use to analyze the list?
Any additional "tools" must take no more than O(1) space and require less than O(N) time to initialize. > Second, I was under the impression (perhaps misguided) > that circular linked lists were not used. One may > have a circular array, but it was very rare, if not > unheard of, to have a circular linked list. When > would a circular linked list be used? A circular linked list with one dummy node is a convinient form of linked list. It has the advantages of having a dummy node at head and tail, while only requiring allocation for one. They are used for queues, etc. But even if they were not used, I have encountered linked lists that were made circular by programming errors more than once in "real life". Finding out if the list was correct (ends in a null) or confused (ends in a loop of indetermiate length) has become a standard part of my test cases. I like this problem because it clarifies the discussion of big O, which has been going on all semester, and encourages you to evaluate all of the techniques you have learned to this point as potential 'tools'. - jeff parker
