[Issue 4420] insertBack() for SList

[d-bugmail at puremagic.com]

http://d.puremagic.com/issues/show_bug.cgi?id=4420



--- Comment #2 from Jonathan M Davis <jmdavisProg at gmail.com> 2010-07-04 02:40:40 PDT ---
Which complexity requirements? I understand that it can't do it as is because
that would be O(n). I was pointing out that it kept track of the last element
in addition to the first one, it could implement insertBack() in O(1) without
needing the extra space per node that a doubly linked list requires. And if it
keeps track of the next-to-last node as well, then it can implement popBack()
in O(1) as well. Is it that other operations no longer fit the appropriate
complexity requirements if it keeps track of the last element in addition to
the first? I would think that the other operations would have the same
complexity but with (in some cases) a slightly higher constant - as in xO(1)
would have a greater value of x rather than becoming O(n) or O(log n) or
anything worse than O(1).

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------