From: Jeffrey Carter <jrcarter@acm.org>
Subject: Re: List container: Insert and Delete
Date: Tue, 13 Nov 2001 02:27:20 GMT
Date: 2001-11-13T02:27:20+00:00 [thread overview]
Message-ID: <3BF08501.50C83D22@acm.org> (raw)
In-Reply-To: dFTH7.21871$xS6.33592@www.newsranger.com
Ted Dennison wrote:
>
> In article <3BEFF9D6.607480D@boeing.com>, Jeffrey Carter says...
> >They will be O(N) in both versions, unless you make the extremely poor
> >implementation decision for the bounded version to implement insertions
> >and deletions by moving entire slices of the underlying array. I suspect
> >such an implementation will be universally considered unacceptable.
> >Making insertions and deletions O(N) so that indexing can be O(1) is a
> >poor choice, especially considering that both can be O(1).
>
> If you make deletions O(N) in a bounded structure, that means you have to deal
> with the possiblity of "holes" in your bounded storage area. I believe that
> means that you will have to go searching for a empty hole in which to place new
> nodes, which means that insertions are actually *not* O(1), even when done to
> the end of the list!
I'm not sure what you're saying here; perhaps that initial "O(N)" should
be O(1)? Actually, for a bounded list you have 2 lists in the same
array: the real list and a free list. Because of the free list, there is
no searching for a hole. Insertions and deletions are O(1) for all
positions.
I think I have a skeleton for a bounded list somewhere. If I can get 2
votes for posting the basics of the implementation I'll dig it out (or
make it up again) and post it.
--
Jeff Carter
"If you think you got a nasty taunting this time,
you ain't heard nothing yet!"
Monty Python and the Holy Grail
next prev parent reply other threads:[~2001-11-13 2:27 UTC|newest]
Thread overview: 189+ messages / expand[flat|nested] mbox.gz Atom feed top
2001-11-10 3:51 List container strawman 1.2 Ted Dennison
2001-11-10 4:20 ` Jeffrey Carter
2001-11-10 4:59 ` Ted Dennison
2001-11-10 11:14 ` Florian Weimer
2001-11-10 16:24 ` Ted Dennison
2001-11-10 17:39 ` Florian Weimer
2001-11-10 18:31 ` Ted Dennison
2001-11-10 18:45 ` Jean-Marc Bourguet
2001-11-10 22:44 ` Ted Dennison
2001-11-11 3:59 ` Steven Deller
2001-11-11 11:29 ` Jean-Marc Bourguet
2001-11-11 17:42 ` Steven Deller
2001-11-11 12:36 ` Jean-Marc Bourguet
2001-11-10 22:07 ` Jeffrey Carter
2001-11-11 17:28 ` Jeffrey Carter
2001-11-10 14:51 ` Ehud Lamm
2001-11-10 16:08 ` Larry Kilgallen
2001-11-10 16:23 ` List container: Insert and Delete Nick Roberts
2001-11-10 17:13 ` Ted Dennison
2001-11-10 21:20 ` Nick Roberts
2001-11-10 22:15 ` Ehud Lamm
2001-11-10 22:48 ` Ted Dennison
2001-11-10 22:40 ` Jeffrey Carter
2001-11-11 4:00 ` Nick Roberts
2001-11-11 17:37 ` Jeffrey Carter
2001-11-11 19:29 ` Steven Deller
2001-11-12 0:20 ` Nick Roberts
2001-11-12 3:48 ` Steven Deller
2001-11-12 13:54 ` Nick Roberts
2001-11-12 15:21 ` Larry Kilgallen
2001-11-13 1:19 ` Nick Roberts
2001-11-12 17:27 ` Jeffrey Carter
2001-11-13 1:28 ` Nick Roberts
2001-11-13 1:37 ` Darren New
2001-11-13 15:58 ` John English
2001-11-13 17:53 ` Pascal Obry
2001-11-12 15:42 ` Marin David Condic
2001-11-12 5:23 ` Ted Dennison
2001-11-12 13:04 ` Nick Roberts
2001-11-12 16:36 ` Ted Dennison
2001-11-12 17:20 ` Jeffrey Carter
2001-11-12 18:55 ` Marin David Condic
2001-11-12 19:56 ` Larry Kilgallen
2001-11-12 20:36 ` Marin David Condic
2001-11-12 21:14 ` Darren New
2001-11-13 7:31 ` Simon Wright
2001-11-13 21:31 ` Marin David Condic
2001-11-14 4:43 ` Nick Roberts
2001-11-13 2:16 ` Jeffrey Carter
2001-11-13 14:18 ` Marin David Condic
2001-11-13 15:03 ` Ted Dennison
2001-11-13 15:28 ` Marin David Condic
2001-11-13 16:16 ` Jeffrey Carter
2001-11-13 19:59 ` Ted Dennison
2001-11-13 20:18 ` Marin David Condic
2001-11-13 21:26 ` Ted Dennison
2001-11-13 21:39 ` Marin David Condic
2001-11-13 22:16 ` Map container (was: List container: Insert and Delete) Ted Dennison
2001-11-14 15:07 ` Marin David Condic
2001-11-13 22:22 ` List container: Insert and Delete Jeffrey Carter
2001-11-13 17:46 ` Darren New
2001-11-13 19:25 ` Steven Deller
2001-11-13 19:40 ` Darren New
2001-11-13 20:53 ` Ted Dennison
2001-11-13 20:10 ` Ted Dennison
2001-11-13 21:31 ` Darren New
2001-11-13 22:37 ` Ted Dennison
2001-11-13 22:44 ` Ted Dennison
2001-11-13 23:00 ` Darren New
2001-11-14 14:31 ` Ted Dennison
2001-11-13 14:20 ` Steven Deller
2001-11-13 15:48 ` John English
2001-11-13 20:22 ` Ted Dennison
2001-11-14 12:59 ` John English
2001-11-14 14:55 ` Ted Dennison
2001-11-14 15:34 ` Marin David Condic
2001-11-15 16:35 ` John English
2001-11-14 16:41 ` Jeffrey Carter
2001-11-13 20:22 ` Ehud Lamm
2001-11-13 21:33 ` Simon Wright
2001-11-14 12:54 ` John English
2001-11-14 16:43 ` Ehud Lamm
2001-11-14 18:19 ` Marin David Condic
2001-11-15 4:29 ` List container: Sawdust woman 43 Jeffrey Carter
2001-11-15 15:25 ` Marin David Condic
2001-11-16 1:59 ` Jeffrey Carter
2001-11-15 20:30 ` List container: Insert and Delete Simon Wright
2001-11-15 17:01 ` John English
2001-11-19 17:40 ` Ted Dennison
2001-11-20 10:52 ` John English
2001-11-13 21:07 ` Ted Dennison
2001-11-12 17:18 ` Jeffrey Carter
2001-11-12 17:13 ` Jeffrey Carter
2001-11-11 23:34 ` Nick Roberts
2001-11-12 16:33 ` Jeffrey Carter
2001-11-12 17:28 ` Ted Dennison
2001-11-13 2:27 ` Jeffrey Carter [this message]
2001-11-13 14:21 ` Ted Dennison
2001-11-14 4:16 ` Nick Roberts
2001-11-14 15:03 ` Ted Dennison
2001-11-13 0:51 ` Nick Roberts
2001-11-12 16:51 ` Ted Dennison
2001-11-13 0:44 ` Nick Roberts
2001-11-13 14:18 ` Ted Dennison
2001-11-14 4:17 ` Nick Roberts
2001-11-10 16:12 ` List container strawman 1.2 Ted Dennison
2001-11-10 18:49 ` Jean-Marc Bourguet
2001-11-10 19:29 ` Ehud Lamm
2001-11-11 10:46 ` Jean-Marc Bourguet
2001-11-11 13:07 ` Larry Kilgallen
2001-11-10 19:07 ` Jacob Sparre Andersen
2001-11-10 22:53 ` Ted Dennison
2001-11-12 16:45 ` Jacob Sparre Andersen
2001-11-13 0:55 ` Nick Roberts
2001-11-13 15:11 ` Ted Dennison
2001-11-10 22:17 ` Jeffrey Carter
2001-11-11 22:04 ` Simon Wright
2001-11-12 16:53 ` Ted Dennison
2001-11-13 7:25 ` Simon Wright
2001-11-13 22:04 ` Ted Dennison
2001-11-10 17:43 ` Florian Weimer
2001-11-10 16:46 ` Ted Dennison
2001-11-10 18:50 ` Steven Deller
2001-11-12 9:25 ` Martin Dowie
2001-11-12 12:57 ` Nick Roberts
2001-11-12 15:32 ` Marin David Condic
2001-11-12 16:58 ` Martin Dowie
2001-11-12 18:44 ` Marin David Condic
2001-11-13 7:18 ` Simon Wright
2001-11-13 21:26 ` Marin David Condic
2001-11-15 23:53 ` martin.m.dowie
2001-11-12 17:35 ` Ted Dennison
2001-11-12 18:39 ` Martin Dowie
2001-11-12 19:58 ` Ted Dennison
2001-11-12 18:39 ` Steven Deller
2001-11-12 20:05 ` Ted Dennison
2001-11-13 19:12 ` Stephen Leake
2001-11-12 16:37 ` Jeffrey Carter
2001-11-12 18:50 ` Marin David Condic
2001-11-13 1:07 ` Nick Roberts
2001-11-13 15:13 ` Ted Dennison
2001-11-15 23:54 ` martin.m.dowie
2001-11-13 19:10 ` Stephen Leake
[not found] ` <3BF0247D.4500975E@san.rr.com>
2001-11-12 20:30 ` Ehud Lamm
2001-11-12 21:57 ` Ted Dennison
2001-11-12 22:53 ` Darren New
2001-11-12 22:55 ` Darren New
2001-11-13 15:54 ` Ted Dennison
2001-11-13 19:17 ` Stephen Leake
2001-11-13 22:37 ` Jeffrey Carter
2001-11-13 15:49 ` Ted Dennison
2001-11-13 16:38 ` Martin Dowie
2001-11-13 19:06 ` Ted Dennison
2001-11-13 19:43 ` Marin David Condic
2001-11-13 20:50 ` Ted Dennison
2001-11-13 21:08 ` Marin David Condic
2001-11-14 4:34 ` Nick Roberts
2001-11-14 14:58 ` Marin David Condic
2001-11-13 17:36 ` Darren New
2001-11-14 4:40 ` Nick Roberts
2001-11-13 22:34 ` Jeffrey Carter
2001-11-14 13:39 ` John English
2001-11-14 15:09 ` Ted Dennison
2001-11-14 16:04 ` Jeffrey Carter
2001-11-14 16:36 ` Ted Dennison
2001-11-15 16:31 ` John English
2001-11-19 17:59 ` Ted Dennison
2001-11-19 21:08 ` Stephen Leake
2001-11-20 10:43 ` John English
2001-11-21 19:40 ` ramatthews
2001-11-22 3:01 ` Nick Roberts
2001-11-22 9:28 ` John English
2001-11-24 3:52 ` Nick Roberts
2001-11-23 2:21 ` Ted Dennison
2001-11-24 0:27 ` John English
2001-11-27 20:04 ` Marin David Condic
2001-11-28 8:10 ` Thomas Wolf
2001-11-28 14:29 ` Marin David Condic
2001-11-28 17:34 ` Ted Dennison
2001-11-28 18:01 ` Marin David Condic
2001-11-28 18:53 ` Ted Dennison
2001-11-28 19:08 ` Overriding 'Class'Input (was: List container strawman 1.1) Ted Dennison
2001-11-28 19:19 ` Ted Dennison
2001-11-28 20:40 ` Marin David Condic
2001-11-28 21:21 ` Ted Dennison
2001-11-28 21:50 ` Marin David Condic
2001-11-29 5:12 ` Nick Roberts
2001-11-29 20:04 ` List container strawman 1.2 Thomas Wolf
2001-11-16 0:01 ` martin.m.dowie
replies disabled
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox