From owner-ootincse@LISTSERV.ARIZONA.EDU Wed May 3 11:16:51 2000 Received: from dns.ccit.arizona.edu (dns.CCIT.Arizona.EDU [128.196.139.46]) by jupiter.cs.uml.edu (8.10.0/8.10.0) with SMTP id e43FGli05011; Wed, 3 May 2000 11:16:48 -0400 (EDT) Received: from dist (dns.CCIT.Arizona.EDU [128.196.139.46]) by dns.ccit.arizona.edu (8.8.8/8.8.8) with ESMTP id IAA09632; Wed, 3 May 2000 08:12:20 -0700 Received: from LISTSERV.ARIZONA.EDU by LISTSERV.ARIZONA.EDU (LISTSERV-TCP/IP release 1.8d) with spool id 15641596 for OOTINCSE@LISTSERV.ARIZONA.EDU; Wed, 3 May 2000 08:11:08 -0700 Received: from callisto.gac.edu (mail@callisto.gac.edu [138.236.128.19]) by listserv.arizona.edu (8.8.8/8.8.8) with ESMTP id IAA34154 for ; Wed, 3 May 2000 08:11:07 -0700 Received: from solen.gac.edu (solen.gac.edu [138.236.128.18]) by callisto.gac.edu (8.10.0/8.10.0/1.0) with ESMTP id e43FB7p21915 for ; Wed, 3 May 2000 10:11:07 -0500 Received: from max.mcs.gac.edu (IDENT:root@max.mcs.gac.edu [138.236.64.64]) by solen.gac.edu (8.9.3/8.9.3/GAC-HUB-2.43) with ESMTP id KAA28360 for ; Wed, 3 May 2000 10:11:08 -0500 (CDT) Received: (from max@localhost) by max.mcs.gac.edu (8.9.3/8.8.7/GAC-SPOKE-2.17) id KAA03275; Wed, 3 May 2000 10:11:05 -0500 X-Authentication-Warning: max.mcs.gac.edu: max set sender to max@max.mcs.gac.edu using -f References: <200005031341.GAA40010@listserv.arizona.edu> Message-ID: <200005031511.KAA03275@max.mcs.gac.edu> Date: Wed, 3 May 2000 10:11:05 -0500 Reply-To: Max Hailperin Sender: OO Technology in CS Education From: Max Hailperin Subject: Re: A simple question of linked lists To: OOTINCSE@LISTSERV.ARIZONA.EDU In-Reply-To: <200005031341.GAA40010@listserv.arizona.edu> (berginf@PACE.EDU) X-Status: Status: RO Date: Wed, 3 May 2000 09:40:54 -0400 From: Joseph Bergin I found the reference.These have been called intrusive data structures. You can read a defense of them at: http://www.codefarms.com/publications/intrusiv/intr.htm Not my cup o' tea, but worth a look. Joe It appears that "intrusive" is a relatively recent coinage, perhaps by that web page's author. The web page itself is undated, but its references range from 1990 to 1996. My intention in my earlier message had been to use nomenclature with a longer tradition by speaking of "intrinsic" and "extrinsic." It turns out, however, that my memory was playing tricks on me. Upon actually looking it up, I see that the older nomenclature is actually "endogenous" and "exogenous": "We call a linked data structure defining an arragement of notdes *endogenous* if the pointers forming the 'skeleton' of the structure are contained in the nodes themselves and *exogenous* if the skeleton is outside the nodes." (p. 9, Tarjan 1983) Although it is a side issue for him, Tarjan also does briefly mention a principal tradeoff between the two: "Endogenous structures are more space-efficient than exogenous ones, but they require that a given element be in only ... a fixed number of structures at a time." (p. 11, Tarjan 1983) (BTW, if you want to take a somewhat anthropological approach by looking at what the norms are in different subcultures of software development, you can find a good example of where the norm seems to be the use of endogenous structures by taking a look at just about any OS kernel. You typically find structures with a zillion pointers to the next (and sometimes previous) one in various lists. A task might have a pointer to the next task of the same priority, the next task in the list of runnable tasks, the next task waiting for the same resource, etc., etc.) Reference: Robert Endre Tarjan, Data Structures and Network Algorithms, SIAM, 1983.