Browse thread
[Caml-list] Doubly-linked list
-
Oleg
- Markus Mottl
- Diego Olivier Fernandez Pons
- james woodyatt
[
Home
]
[ Index:
by date
|
by threads
]
[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
[ 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. --james ------------------- To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/ Beginner's list: http://groups.yahoo.com/group/ocaml_beginners