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?
Maintaining a list of nodes with challenging requirements
design;data structures;modeling
A hybrid in form of linked arrays sounds like a compromise between the two structures. You still fast index access, relatively low overhead with random insertions and really low when inserting in batches.Wikipedia names this an unrolled linked list