This is a question regarding the design of a collection of ordered nodes which have some requirements that I am struggling to satisfy.
In the problem area that I am dealing with we have routes which are an ordered collection of nodes. A route will be between 1000 and 25000 nodes. A node itself is a complex object.
I need to be able to persist the nodes, ideally to a relational database (as the wider application is currently delivered using an architecture that uses a relational database for persistence). I have two separate requirements which present a difficultly in how to model the data.
- I need to be able to insert nodes (or pointers to nodes) into the middle of the list and reorganise the list on the fly.
- I need to be able to retrieve the list in it's correct sequential order with both an efficient index and the ability to random access.
The only way I think that I can satisfy the first requirement is to model the data as a linked list where every node points to the next node in the list, which would allow the list to be edited and reorganised on the fly.
The only way I think that I can satisfy the second requirement would be to sequentially order the list so each node has a reference to it's position in the list and order/access the list by the position.
Is there any other method that I could use that can satisfy the two requirements or am I stuck with building a hybrid that employs both methods at various times depending on operational context and that keeps the two referencing types in synch?