what do you mean by ordered list?
You cannot mean list of points with distance from a given point, as generating that distance takes too long.
It seems to me you could make a list of coords sorted by x coord.
It takes time to make, but can be re-used.
Use the sorted list to find first point to the left of the test point, calc its distance away.
That distance will be a search limiting factor, and will be refined as you move forward.
You will never need to look at points further away on the x axis than that distance.
Try the next point to the left, if its distance away is less, it becomes the new winner and the search radius is revised too.
Keep going left until you pass the search radius (smallest distance found so far).
Then repeat for the right side on x axis.
I wonder if the process could also be sped up by using three lists, sorted by x, y, and z.
The idea is to narrow down the search radius as fast as possible, to limit loops needed.
So maybe look at point to before test point in x list, then look at point before point in y list, and then z list.
I think that is the fastest way, but the initial list creation may take too long if it will not be re-used enough.
You could run tests to see what ratios are best for number of points, vs how many "nearest to" operations are needed. I tend to just assume large datasets, as small datasets are fast so why optimize them further?
You must deal with the large datasets though.
I did a similar routine for finding all intersecting lines/arcs. You use coords of bounding boxes instead of one coord. It sounds complicated, but when you need it, you need it bad. The efficiency gain is 100 fold.