Functional Pearls A symmetric set of efficient list operations
- 1 October 1992
- journal article
- Published by Cambridge University Press (CUP) in Journal of Functional Programming
- Vol. 2 (4) , 505-513
- https://doi.org/10.1017/s0956796800000526
Abstract
In this paper we show that it is possible to implement a symmetric set of finite-list operations efficiently; the set is symmetric in the sense that lists can be manipulated at either end. We derive the definitions of these operations from their specifications by calculation. The operations have O(1) time complexity, provided that we content ourselves with, so-called, amortized efficiency, instead of worst-case efficiencyKeywords
This publication has 2 references indexed in Scilit:
- Amortized Computational ComplexitySIAM Journal on Algebraic Discrete Methods, 1985
- The Science of ProgrammingPublished by Springer Nature ,1981