Clever Geek Handbook

Which one to use linked list or static arrays?

I have a structure in C that is similar to the record structure of a database table. Now when I query the table using select, I don't know how many records I will get. I want to store all returned records from a select query in an array of my struct data type.

Which method is better?

Method 1: find the size of the array and allocate

  • first get the record count by doing select count (*) from the table
  • allocate static array
  • run select * from the table and then store each entry in my structure in a loop.

Method 2: use a single list

while ( records returned )
{
    create new node 
    store the record in node 
}

What's the best implementation?

My requirement is that when I have all the records, I will probably make copies of them or whatever. But I don't need random access, and I won't search for a specific record.

thank

+1


source to share


7 replies


And I forgot option # 4. Allocate a fixed size array. When this array is full, select another one. You can keep track of arrays by linking them in a linked list or having a higher level that stores pointers to arrays of data. This two-tier scheme is great when you need random access, you just need to split your index in two.



+3


source


The problem with 'select count (*)' is that the value can change between calls, so your "real" selection will contain a few different items than expected.



I think your "2" is the best solution. Instead of a linked list, I would personally allocate an array (reallocating as needed). This is easier in languages ​​that support growing arrays (for example, std::vector<myrecord>

C ++ and List<myrecord>

C #).

+1


source


You forgot option 3, it's a little more complicated, but it might be better for your specific case. This is usually done in C ++ std :: vector.

Allocate an array of any convenient size. When this array is full, allocate a new larger array of 1.5x to 2x the size of the filled one, then copy the filled array into this. Free the original array and replace it with a new one. Wet, rinse, repeat.

+1


source


There are many possible criticisms.

  • You are not talking about a static array at all - a static array will have a predefined size, fixed at compile time, and local to the source file or local to the function. You are talking about a dynamically allocated array.

  • You do not specify the size of the record or the number of records, nor the dynamics of the database below it (i.e. any other process can change any of the data while it is running). Calibration information is not critical, but there is another factor. If you are doing some kind of report, then fetching data into memory is fine; you are not going to modify the database and the data is an exact snapshot. However, if other people can change records while they change records, your main decision is a prime example of how to lose other people's updates. This is a NECESSITY!

  • Why do you need all the data in memory at once? Ignoring size limitations, what is the benefit of doing this versus processing each respective record once in the correct sequence? You see, the DBMS have gone to a lot of effort to select the appropriate records (WHERE clauses) and the corresponding data (SELECT lists) and let you specify the sequence (ORDER BY clauses), and they have the best sorting systems they can (better than the ones you or I will most likely create).

  • Beware of quadratic behavior if you allocate your array in chunks. Every time you reallocate, there is a decent chance that the old memory must be copied to a new location. This will fragment your memory (the old location will be reusable, but by definition too small to reuse). Mark Ransome points to a reasonable alternative - not the world's simplest schema as a whole (but it avoids the quadratic behavior I talked about). Of course, you can (and will) abstract from this with a set of suitable functions.

  • Bulk fetch (also mentioned by Mark Ransom) is also helpful. You want to preallocate the array into which you will select a bulk sample so that you don't have to do additional copying. This is just linear behavior, so it is less severe.

0


source


Create a data structure to represent your array or list. Imagine that you are in the OO language and create accessors and constructors for everything you need. Inside this data structure, store the array and as others have said, when the array is full to capacity, allocate a new 2x array as large as possible and copy it over. Access the structure only through specific subroutines to access it.

So Java and other languages ​​do it. Internally, this is even how Perl is implemented in C.

I was going to say your best bet is to look for a library that already does this ... perhaps you can take Perl C to implement such a data structure. I'm sure this is more well tested than anything you or I could roll up from scratch. :)

0


source 


while(record = get_record()) {
  records++;
  records_array = (record_struct *) realloc(records_array, (sizeof record_struct)*records);
  *records_array[records - 1] = record;
}

This is strictly an example - please don't use realloc () in production.

0


source


A linked list is a good, simple option. I would go with that. If you prefer a growing array, you can find an implementation as part of Dave Hanson's C Interfaces and Implementation , which also provides linked lists as a bonus.

This looks like a design decision that is likely to change as your application evolves, so you should hide the view behind a suitable API . If you don't know how to do this yet, Hanson's code will give you some nice examples.

0


source






More articles:


All Articles