Version française
Home     About     Download     Resources     Contact us    

This site is updated infrequently. For up-to-date information, please visit the new OCaml website at

Browse thread
[Caml-list] Doubly-linked list
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2002-08-19 (23:17)
From: james woodyatt <jhw@w...>
Subject: Re: [Caml-list] Doubly-linked list
On Tuesday, Aug 13, 2002, at 01:00 US/Pacific, Oleg wrote:
> Has anyone implemented a doubly-linked list with O(1) push_back, 
> push_front,
> back, front, length operations?
> Thanks
> Oleg
> P.S. BTW, one could have identical interfaces for a) resizable arrays, 
> b)
> doubly-linked lists and c) deques, the only difference being the 
> efficiency
> of various operations. It could be convenient for a programmer, 
> because final
> data representation can be chosen after the program has been profiled 
> and
> without changing much code. Has anyone tackled this problem?

I have recently been working on a fully-persistent, catenable deque 
that uses explicit recursive slowdown , á la Kaplan and Tarjan, to 
achieve what seems to me to be O(1) amortized cost for all the 
traditional operations.  I think my design may be substantially simpler 
than algorithms I've seen published to date, but I'm not sure.  I'm 
certain it isn't O(1) for all operations, but I can push and shift 
millions of objects into and out of a deque without any noticeable 
degradation in performance over the size of a deque.  In other words, 
it looks to me to be good enough for government work.

When I've put the code through some more paces, I will publish it.  
Give me a few more weeks.


To unsubscribe, mail Archives:
Bug reports: FAQ:
Beginner's list: