Currently, I have a simple database program that reads keys from a text file and stores them in a doubly linked list (values are read later if necessary). I am currently doing a sequential search on a list, but this is clearly quite slow. I was hoping there was another way. I read about binary trees (in particular red black trees), but I don’t know much about them, and hoped that I could pull something out of stackoverflow hivemind :) I suppose my question is what is the fastest way search a doubly linked list?
EDIT: Forgot to say the list is sorted. I don’t know that this will not change anything. Also, the reason I only read in keys is because the maximum length of the value is 1024 * 32 bytes, which I consider to be too large. Please note that this is for assignment, so “typical use cases” do not apply. Professors are likely to experience stress testing the hell out of this thing, and I don't want big blocks, big ones.
source
share