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=-2.9 required=5.0 tests=BAYES_00,MAILING_LIST_MULTI autolearn=unavailable autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 103376,a676349b69fa778f X-Google-Attributes: gid103376,public X-Google-ArrivalTime: 2001-02-12 13:20:03 PST Path: supernews.google.com!sn-xit-03!supernews.com!news-out.usenetserver.com!news-out.usenetserver.com!diablo.theplanet.net!newsfeed00.sul.t-online.de!newsfeed01.sul.t-online.de!t-online.de!fr.clara.net!heighliner.fr.clara.net!opentransit.net!jussieu.fr!enst!enst.fr!not-for-mail From: schwarza@gdls.com Newsgroups: comp.lang.ada Subject: Re: Help: my list adt is broken Date: Mon, 12 Feb 2001 16:14:00 -0500 Organization: ENST, France Sender: comp.lang.ada-admin@ada.eu.org Message-ID: Reply-To: comp.lang.ada@ada.eu.org NNTP-Posting-Host: marvin.enst.fr Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: avanie.enst.fr 982012512 30157 137.194.161.2 (12 Feb 2001 21:15:12 GMT) X-Complaints-To: usenet@enst.fr NNTP-Posting-Date: Mon, 12 Feb 2001 21:15:12 +0000 (UTC) To: comp.lang.ada@ada.eu.org Return-Path: X-Mailer: Lotus Notes Release 5.0.1a (Intl) 17 August 1999 X-MIMETrack: Serialize by Router on STL01/SRV/LS/GDYN(Release 5.0.5 |September 22, 2000) at 02/12/2001 04: 13:58 PM, Itemize by SMTP Server on STLHUB/SRV/LS/GDYN(Release 5.0.5 |September 22, 2000) at 02/12/2001 04: 13:59 PM, Serialize by Router on STLHUB/SRV/LS/GDYN(Release 5.0.5 |September 22, 2000) at 02/12/2001 04: 14:01 PM, Serialize complete at 02/12/2001 04: 14:01 PM Errors-To: comp.lang.ada-admin@ada.eu.org X-BeenThere: comp.lang.ada@ada.eu.org X-Mailman-Version: 2.0 Precedence: bulk List-Help: List-Post: List-Subscribe: , List-Id: comp.lang.ada mail<->news gateway List-Unsubscribe: , List-Archive: Errors-To: comp.lang.ada-admin@ada.eu.org X-BeenThere: comp.lang.ada@ada.eu.org Xref: supernews.google.com comp.lang.ada:5196 Date: 2001-02-12T16:14:00-05:00 Chris; There are exactly two (2) ways of implementating a doubly-linked list (unless I become reasonable - nah, never happen): [1] Each end of the doubly linked list terminates in a null and the list head points to the first element of the list: ptr -> null <- cell -> ... <- cell -> null [2] There is a unique list header which points to both the list header and tail (and is itself a list cell) with a pointer to the header cell being the external 'name' of the list: ptr -> unique list header cell top -> <- cell -> ... <- cell -> . bot -> | ^ | | | .---------------------------------. I prefer two to one (2 to 1) but that is not material. Now, to do any list switching the order of operations is very, very important. If you don't do things in the proper order, carefully, things get fouled up fast. So let's see: Suppose we do the following: 1. Save the left pointer of the first cell. 2. Put into the left pointer of the first cell, the left pointer of the 'new cell'. 3. Put into the left pointer of the second cell, the (saved) left pointer of the first cell. 4. Put into the right pointer of the cell pointed to by the second cell a pointer to the current cell. And here is where the two implementations differ. For [1], it is possible for the left pointer of the second cell to be null. For [2] there is no such worry (it works in all cases). 5. Repeat for the right pointers. 6. If you have implemented [1], then some fixup is required: a. If the second cell is the list top, then the 'ptr' must be changed to the first cell (the new list top). b. If the first cell is the list top then the contrawise operation has to be done. And now for the kicker. This is not a place to get your homework assignments done. Having said that, let me amplify a comment concerning debugging (instrumenting your code with output statements). Code for failure!! Assume nothing (NOTHING) will work correctly and provide print statements accordingly. It's easier than asking questions. And, allow the print statements to be turned on or off, as in: if this_is_some_kind_of_debug_thing then PRINT; Disappointingly you will find that the volume of code required to code for failure is larger than that for your actual classroom assignments. Encouragingly you will shine amongst your peers because you will be able to identify your errors quickly and solve them even more quickly. art PS: If any of you are real, real old programmers then [2] is SLIP (Symmetric LIst Processor) from way, way back (circa 1960). I believe that Eliza was programmed in SLIP and in FORTRAN at MIT. PSST: I am a real, real old programmer and still have copies of the original SLIP implementation circa 1964 at the University of Wisconsin; in FORTRAN.