ADT - Lists

[GoldenHaddock]

Not sure if this is quite the right forum, but here goes!

Doing a bit of revision for forthcoming exams.....

Theres a question on a past paper about lists, which is fine...but the next part of the question is:

"Suggest alternative ADT's for the following:

a) a system designed to store 10,000+ records (just sotred, rarely sorted/reports very rarely run).

b) a system designed to store 10,000+ records whre the main purpose is to sort the records and procude reports.

Any suggestsions? Would a queue be approproiate for part a?

Any advice or links most appreciated!

Thanks

 

[Polu]

a) An array
b) A balanced B-Tree

 

[chiph]

You didn't mention growth -- if the quantity of data is fairly static, then an array is good for (a). Otherwise maybe a linked-list. I agree with Polu on using a B-Tree for (b).

Chip H.


____________________________________________________________________
If you want to get the best response to a question, please read FAQ222-2244 first

 

[GoldenHaddock]

Thanks for that!

I presume B-Tree means binary?

 

[GoldenHaddock]

Also, another part of the question asks you to support your answer using Big-O. How would I calculate that for an array?

 

[Polu]

It depends on the sort algorithm you use. Most commonly will be O(n^2)