There are modern languages that come with standard libraries implementing the most common of the data structures. Some example of such languages are java collections frame work, C++ standard template library, Microsoft’s .Net frame work etc.
Modular programming (it is the separation between the interface of the module and its implementation) is generally supported by the modern languages. Some languages are known to provide opaque data types, thus enabling the users to keep the implementation details hidden. However, classes are used for this purpose by the object oriented programming languages such as the .Net frame work, java, C++ etc.
How to implement a Data Structures?
– First step in the implementation of a data structure is writing a set of procedure that would be followed for the creation and manipulation of the instances of that particular data structure.
– The efficiency of the data structure is analyzed together with that of the operations.
– This observation served as a motivation for the theoretical concept of the abstract data type.
– There are many assembly languages as well as some low level languages such as basic combined programming language which do not provide support for the data structures.
– On the other hand, there are certain high levels programming languages (for e.g., MASM) which come with a special syntax as well as built in support for the structures like vectors, multi-dimensional arrays and so on.
– A sort of library feature is exhibited by some of the programming languages using which the data structure implementations can be reused by several programs.
– Most of the data structures make use of both the principles sometimes as single or sometimes combined in different ways.
What are Concurrent Data Structures and how they are implemented?
– Concurrent versions are known to exist for many of the known data structures.
– The benefit of having concurrent versions is that the multiple computing threads can be allowed simultaneously to the access the data structures.
– A concurrent data structure provides a unique way for the storage and organization of the data by means of accessing multiple processes or threads on a computer system.
How these structures are actually designed and implemented?
Usually many difficulties are faced while designing the concurrent data structures. The major source of the difficulties that are faced is the concurrency itself since it is required that the threads or processes must be considered to be as completely asynchronous.
These threads are subjected to the pre – emption of the following factors:
1. Operating system
2. Large faults
3. Big interrupts and so on.
For the machines and systems of today, the performance is influenced by the following factors:
1. Layout of memory and processors
2. Layout of data present in the memory
3. Communication load up on the multiprocessor elements
4. Architecture and so on.
– In addition to all this, there exists a tension between the performance and the correctness.
– This tension can be further detailed as the difficulty in designing and verifying the implementation of a correct data structure that occurs because the algorithmic enhancements that seek the performance improvement.
– The level of memory contention (i.e., the overhead that is experienced in data traffic to and from memory because of the threads or multiple processes trying to access the same memory locations.) is one of the chief issues with the implementation of the concurrent data structures.
– However, this issue is addressed by the use of locks with the blocking implementations which control the access to the locations.
– For acquiring a lock it is necessary for the thread to repeatedly attempt for the modification of the location.