Array or doubly linked list?

[TheBigH]

Hi everyone,
I am looking to numerically solve a system of differential equations of the sort
dy/dx = f(x,y,a,b,c,d,...)
da/dx = g(x,y,a,b,c,d,...)
and so on. I've created structs that look like

struct univ {
   double x;
   double y;
   ...
};

to hold x and the dependent variables y,a,b,... . I will be using finite differences on an arbitrarily spaced grid.

My question is this: should I use an array of univs, or a doubly linked list of them, to represent my system? If I use an array the benefit is that accessing them is transparent. However, I will most likely find a few places where dy is large compared to y; that is, the function y(x) is steep. In that case I would like to temporarily insert new grid points at those places to improve the resolution and clearly a doubly linked list makes this simple.

Has anyone here done something similar in C? Does the speed and ease of comprehension of arrays outweigh the flexibility of a linked list? Is there maybe a way of getting the best of both worlds from some clever blend of the two? Advice and insights would be very welcome.

Cheers,
H.

[anduril462]

Haven't done differential equations in years, and don't remember much about them. In my opinion, linked lists would be too much for this problem. Arrays would be better, but instead of assuming your y array always has a fixed distance between cells and not having an x array, use parallel arrays. One array will hold the x values, and another the corresponding y values:

x = 1  2  3  4  5  6  6.1  6.2  6.3  6.4  6.5
y = 2  4  6  8 10 12 12.2 12.4 12.6 12.8 13.0

That would be y = 2x, with varying distances between x coordinates.

[TheBigH]

Yeah, that's pretty much what my structures are for:

i      = 0  1  2  3  4  5  6    7    8    9    10
a[i].x = 1  2  3  4  5  6  6.1  6.2  6.3  6.4  6.5
a[i].y = 2  4  6  8 10 12 12.2 12.4 12.6 12.8 13.0

In linked list format they would look like

...   a->prev   a   a->next   ...
.x      6.1     6.2   6.3
.y     12.2    12.4  12.6

The point being, if I need to insert a new grid point between 6.2 and 6.3, say, I can do that easily with a linked list but not with an array. The drawback is that the code doesn't look as clean and is harder to understand and debug. Is it faster to run through each element of an array with a for loop than it is to follow the chain of pointers of a linked list?

[anduril462]

Yeah, you will want a linked list for this if you have to change your intervals at run time. It wont be as clean, but it should be almost as fast for sequential processing. It will only be marginally slower for adding or deleting an element. The downside to linked lists is that there is no random access, so finding the 17th element takes 17 iterations of your search loop, basically it's a linear search, so it's O(n). For arrays, lookup by index is constant time.