Fast append can be implemented on an array language without linked lists -- the mechanism involves leaving some empty memory at the end of arrays and using that for append when there's only one reference to the array and that reference is being updated.
For multi-key indexing, what you would do instead is maintain multiple "generations" of the data. The big/slow instance gets updated rarely (folding in the fast/small instance and doing the sorts then during those updates). At read time you check both of them. The update overhead here winds up being analogous to the garbage collection overhead for linked lists. And the traversal overhead can vary - both linked lists and arrays have overhead, though the details differ, but in my experience it's straightforward to get the array code to perform quickly. Thanks, -- Raul On Tue, Nov 19, 2019 at 3:49 PM 'Rob Hodgkinson' via Programming <programm...@jsoftware.com> wrote: > > I disagree on this point Devon, linked lists are a very powerful data > structure and can be “overlaid” atop dynamic arrays to maintain a desired > index order. > > Without such a structure the only practical way is to append and (re)sort to > maintain an array in a suitable form. > > An example of this is the construction of an order book in a real time > trading system, VERY impractical in an array only language. > However if the array could overlaid with a linked list, then the orders could > be “appended” on receipt (fast) and a linked list used to update the sort > order, so the order book can be traversed very efficiently by attributes such > as Price/Time. > Without it, one must sort the order book to find the best Price/Time for > matching … and repeat that on each new order received. > > I do use C for this for matching engine rules, but have often thought a > linked list overlay would be a very powerful way to maintain an ordered array > for such a purpose. > > …/Regards Rob > > > On 18 Nov 2019, at 8:06 am, Devon McCormick <devon...@gmail.com> wrote: > > > > Linked lists make no sense in a language with dynamic arrays for much the > > same reason since a linked list is mainly a way of implementing dynamic > > arrays but has benefit only in a language which lacks these natively. > > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
