Re: Optimal Structure for Inserting and Deleting

> My questions yesterday about linked lists were related to my use of them as
> a structure that easily allows insertions and deletions while maintaining
> existing order.  Is there something better I can use?

        'better' as in 'faster' ?

        Inserting/deleting from a linked list is considered O(1). Though,
finding the element to delete is O(n). If you don't have an index where the
elements are, i.e. your linked list doesn't have a dictionary attached to it
which is used to find elements to delete quickly (which is O(1) for lookups),
a linked list can be slow with many objects, as finding the element to delete
is a linear search.

        I think, it's easier to use a self balancing binary search tree which
is sorted by default, and has O(log n) for insert/delete and find.

        But above all, what do you want to do with the list? For example, if
you want to have the list to be a heap, i.e. a structure which always supplies
you with the highest ranked value (or object), you should look at implementing
a fibonacci-heap.

                FB



===================================
This list is hosted by DevelopMentor®  http://www.develop.com

View archives and manage your subscription(s) at http://discuss.develop.com