Browse Prior Art Database

A method of selecting data structure implementation by usage pattern Disclosure Number: IPCOM000201646D
Publication Date: 2010-Nov-17
Document File: 2 page(s) / 44K

Publishing Venue

The Prior Art Database


This article describes how the factory model can be applied to the implementation of data structures, allowing programmers to instantiate data structures based on how the program will use the data structure.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 53% of the total text.

Page 01 of 2

A method of selecting data structure implementation by usage pattern

Disclosed is a method for instantiating a data structure based on the way the structure is to be used in the application which reduces the requirement for the programmer to have intimate knowledge of how the data structure behaves. This is achieved by allowing the programmer to specify how the data structure will be used, and a factory method then supplies an implementation to satisfy that usage pattern.

    When an application programmer using a language such as Java utilizes a data structure object, they have two choices to make. Firstly, they must decide which type of data structure is most appropriate (e.g. list, tree, key/value mapping, etc.) which is usually dictated by requirements. Having selected the data structure, they usually have a choice of a number of different implementations of that data structure which exhibit different behaviour.

    For example, in Java the List interface describes a list based data structure, and available implementations include ArrayList, CopyOnWriteArrayList, LinkedList, and Vector. Each of these behave differently with regards to:
1. Whether or not modifications are synchronized (thread safe)
2. Whether or not retrievals and traversals are synchronized
3. Whether they are optimized for smaller or larger collection sizes
4. Whether they are optimized for collections that change often or rarely
5. Whether they are optimized for different ratios of modifications to traversals
6. Whether they are modified after elements are initially added
7. Whether or not null elements are permitted
8. Whether or not duplicate elements are permitted (and more)

    In Java, most data structure objects can be made synchronized by wrapping them in a lightweight wrapper, but many attributes are strongly tied to the implementation.

    The programmer knows how the application is going to use the data...