I read a while back about how linked lists were not included in the standard Swift library because they are something that only gets used in classroom situations where people are learning about algorithms., or some such nonsense (in my humble opinion). But then I did a test and the inserting and deleting of data in a small array in Swift are faster than the same type of insertion and deletion in a linked list (of my own design). So I switched to using arrays. So be it.
Today, I was working on the code for the Linkage app for the Mac and I found a situation where I really missed the linked list. Now this might just show how bad I am at designing data structures but I’ll admit what I did and maybe it will make sense; I have an array of elements for a spline and the elements are either nodes or segments. The two are interleaved (alternating) in the array in the same way they are interleaved visually. My spline nodes have information about the visual type of the node and a point for where it is located. The segments have visual information and optionally if the segment is a Bezier curve, some control points. In order to draw a Bezier curve or even save the segment to the output file, the code needs four points. To get four points from a segment, the code must go back one element in the array to get the previous node and also go forward one element. If the segment is the closing segment then the first node of the entire spline is the end node for the segment. This is easy using a linked list and slow and ugly using an array.
The solution for this data problem in an array is to have a function to request the four Bezier points as part of the spline itself. When given a segment object, this function will search the array for the segment and then, using the index where it finds the segment, get the nodes before and after, and return the four points.
Is there another solution? Without access to the array, the code stepping through the segments could be made to step through the elements and save data when encountering nodes. Or it could use indexes and when it finds segment, just index back one for the previous node and index forward one (or to zero) for the next node. The reason I didn’t do this is that I have a cool array function in the spline that will return just an array of segments for iteration. That segment array function makes the code very easy to understand up to the point of this next/previous node problem. So maybe the solution is to make a function return the indexes of all of the segments in the element array and then integrate through those indexes. I’m going to try it and see if it looks cleaner or if it’s just as clear but yields better performance (in theory). To be honest, a few extra traversals of a short-ish array might not make a difference here.