From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id BAA18268; Tue, 20 Aug 2002 01:17:21 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id BAA18345 for ; Tue, 20 Aug 2002 01:17:21 +0200 (MET DST) Received: from wetware.wetware.com (wetware.wetware.com [199.108.16.1]) by concorde.inria.fr (8.11.1/8.11.1) with ESMTP id g7JNHJT24678 for ; Tue, 20 Aug 2002 01:17:20 +0200 (MET DST) Received: from kallisti.local.(ra06.wetware.com[199.108.16.86]) (1996 bytes) by wetware.wetware.com via sendmail with P:esmtp/R:bind_hosts/T:inet_zone_bind_smtp (sender: ) id for ; Mon, 19 Aug 2002 16:17:18 -0700 (PDT) (Smail-3.2.0.114 2001-Aug-6 #1 built 2002-Aug-4) Date: Mon, 19 Aug 2002 16:17:16 -0700 Subject: Re: [Caml-list] Doubly-linked list Content-Type: text/plain; charset=ISO-8859-1; format=flowed Mime-Version: 1.0 (Apple Message framework v543) Cc: caml-list@inria.fr To: Oleg From: james woodyatt In-Reply-To: <200208130759.DAA26086@dewberry.cc.columbia.edu> Message-Id: Content-Transfer-Encoding: quoted-printable X-Mailer: Apple Mail (2.543) Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk On Tuesday, Aug 13, 2002, at 01:00 US/Pacific, Oleg wrote: > > Has anyone implemented a doubly-linked list with O(1) push_back,=20 > push_front, > back, front, length operations? > > Thanks > Oleg > > P.S. BTW, one could have identical interfaces for a) resizable arrays,=20= > b) > doubly-linked lists and c) deques, the only difference being the=20 > efficiency > of various operations. It could be convenient for a programmer,=20 > because final > data representation can be chosen after the program has been profiled=20= > and > without changing much code. Has anyone tackled this problem? I have recently been working on a fully-persistent, catenable deque=20 that uses explicit recursive slowdown , =E1 la Kaplan and Tarjan, to=20 achieve what seems to me to be O(1) amortized cost for all the=20 traditional operations. I think my design may be substantially simpler=20= than algorithms I've seen published to date, but I'm not sure. I'm=20 certain it isn't O(1) for all operations, but I can push and shift=20 millions of objects into and out of a deque without any noticeable=20 degradation in performance over the size of a deque. In other words,=20 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. =20 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