From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=ham autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 103376,a644fa9cd1a3869a X-Google-Attributes: gid103376,public X-Google-ArrivalTime: 2001-11-12 09:53:10 PST Newsgroups: comp.lang.ada Path: archiver1.google.com!news1.google.com!sn-xit-02!supernews.com!newsfeed.direct.ca!look.ca!feed2.onemain.com!feed1.onemain.com!uunet!dca.uu.net!ash.uu.net!xyzzy!nntp From: Jeffrey Carter Subject: Re: List container: Insert and Delete X-Nntp-Posting-Host: e246420.msc.az.boeing.com Content-Type: text/plain; charset=us-ascii Message-ID: <3BF00475.A7B11907@boeing.com> Sender: nntp@news.boeing.com (Boeing NNTP News Access) Content-Transfer-Encoding: 7bit Organization: The Boeing Company X-Accept-Language: en References: <9sn4qm$13g29j$2@ID-25716.news.dfncis.de> Mime-Version: 1.0 Date: Mon, 12 Nov 2001 17:18:45 GMT X-Mailer: Mozilla 4.73 [en]C-CCK-MCD Boeing Kit (WinNT; U) Xref: archiver1.google.com comp.lang.ada:16345 Date: 2001-11-12T17:18:45+00:00 List-Id: Nick Roberts wrote: > > (b) For a list based on an array, the operation: "delete the third item" is > easy to implement, and fairly efficient for short lists; "insert before the > third item" is ditto; and "replace the third item" is both easy and > efficient (for any length of list). For a list based on a linked-list, the > implementations of these operations are easy, and pretty efficient for short > lists and for operations near to either end of the list. For a bounded list (based on an array), deleting the third item is no easier to implement than for an unbounded list, just as finding the Ith item is O(N) for both types of list, unless a very poor implementation is chosen for the bounded list. -- Jeffrey Carter