Newsgroups: comp.sys.mac.programmer Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!magnus.acs.ohio-state.edu!scasterg From: scasterg@magnus.acs.ohio-state.edu (Stuart M Castergine) Subject: Re: How to best do a linked list on Mac Message-ID: <1991Jun13.021847.10193@magnus.acs.ohio-state.edu> Sender: news@magnus.acs.ohio-state.edu Nntp-Posting-Host: bottom.magnus.acs.ohio-state.edu Organization: The Ohio State University References: <1991Jun10.002416.5656@gn.ecn.purdue.edu> <14026@goofy.Apple.COM> Date: Thu, 13 Jun 1991 02:18:47 GMT Lines: 53 In article <14026@goofy.Apple.COM> casseres@apple.com (David Casseres) writes: >In article , >francis@zaphod.uchicago.edu (Francis Stracke) writes: > >> My favorite solution is to declare an array type, then allocate a >> handle to such an array, and resize it dynamically. >> >> That way you can do it with only one handle (though you may want to >> have an array of handles, if your records are large), and you can >> index into the array rather than searching the list. > >This works fine but it isn't a linked list -- it's a dynamically sized >array. It's good as long as all you will do is add elements at the end >or remove them from the end, but it doesn't allow you to add elements >in the middle, or remove them from the middle and reclaim their storage >space. > >David Casseres Here's something I learned long ago in a Pascal Class at OSU. I don't program enough to remember the code, but it went something like this in english: pointer item record item pointer prev real data pointer next Then you can dynamically create lists of any size, by having the pointers in each item point to the previous and next items. You can even make your list circular by having the end point back around to the beginning. The routines for navigating through the list are pretty simple, as I remember. You just have a "thumb" that you use to point to your current record, and maybe the first record, so you don't get lost :-) I suspect you could have multiple thumbs. You can easily add items anywhere in the list by creating a pointer to a new record and changing the pointers of the surrounding items to refer to it. I'd like to get back in the habit of programming enough to actually remember this stuff (see my previous post). -- scasterg@magnus.acs.ohio-state.edu Stuart M Castergine "Step by step they were led to practices which disposed to vice -- the lounge, the bath, the elegant banquet. All this in their ignorance they called civilisation, when it was but part of their servitude."