The data structure “r-Train” (“Train” in short) where r is a natural number is a new kind of powerful robust data structure that can store homogeneous data dynamically in a flexible way, in particular for large amounts of data. But a train cannot store heterogeneous data (by the term heterogeneous data, the authors mean data of various datatypes). In fact, the classical data structures (e.g., array, linked list, etc.) can store and handle homogeneous data only, not heterogeneous data. The advanced data structure “r-Atrain” (“Atrain” in short) is logically almost analogous to the data structure r-train (train) but with an advanced level of construction to accommodate heterogeneous data of large volumes. The data structure train can be viewed as a special case of the data structure atrain. It is important to note that none of these two new data structures is a competitor of the other. By default, any heterogeneous data structure can work as a homogeneous data structure too. However, for working with a huge volume of homogeneous data, train is more suitable than atrain. For working with heterogeneous data, atrain is suitable while train cannot be applicable. The natural number r is suitably predecided and fixed by the programmer depending upon the problem under consideration and also upon the organization/industry for which the problem is posed.
TopIntroduction
Data structures are generally based on the ability of a computer to fetch and store data efficiently at any place in its memory. The data structures record and array are based on computing the addresses of data items with arithmetic operations; while the linked data structures are based on storing addresses of data items within the structure itself. Data structures can be classified in several ways, viz. Primitive/Non-primitive, Homogeneous/Heterogeneous, Static/Dynamic, Linear/Non-linear, etc. The cost of memory space to store data using the data structure array is least. At the same time a basic demerit of using array is that it needs contiguous free bytes of memory which may not be always available if the array size is large, even if huge amount of free bytes be available in the memory at different locations. For example, at some point of time it may happen that 220 number of free bytes available in the memory whereas 27 free contiguous bytes are not available. Consequently, an array of 65 positive integers can not be accommodated in the memory at this point of time, whereas a linked list of a large number of integers can be accommodated easily here. This is one of the basic advantages of using linked list. However, linked lists require more memory space compared to arrays because of an extra field in each node where address of the next node is stored. There are a number of useful data structures viz. Splay Trees and Dynamic Trees (Sleator & Tarjan, 1983; Sleator & Tarjan, 1985), hash table, AVL Trees (Velskii & Landis, 1962), B-Trees (Bayer & McCreight, 1972), Red-black trees (Bayer, 1972), Treaps (Seidel & Aragon, 1996), HAT (Sitarski, 1996), Graphs, Multigraphs (Biswas, Alam, & Doja, 2012; Biswas, Alam, & Doja, 2013), etc. developed by different authors for various purposes with different philosophy for different kind of requirements (one could see any good book for details viz. Aho, Hopcroft, & Ullman, 1983; Shaffer, 2001; Knuth, 1968; Lynch, 1996; Cormen, Leiserson, Rivest, & Stein, 2001). There are some situations where we need to create an entirely new type of data structure of generalized nature, and creating such a new but simple data structure is not always a straightforward task.
In this chapter we discuss about two new powerful data structures “r-Train” (or ‘Train” in short) and “r-Atrain” (or “Atrain” in short) which are very suitable for storing huge volume of data. The natural number r is suitably pre-decided and fixed by the programmer depending upon the problem under consideration and also upon the organization/industry for which the problem is posed.
While train stores homogeneous data, atrain is suitable for the purpose of storing heterogeneous data. The term “Atrain” is an abbreviation for “Advanced train”. The two data structures r-train and r-atrain do not have any conflict of interest at all, although both are potential enough to accommodate huge volume of data. There is no competition between r-atrain and r-train in application areas, because r-train can not be applicable for heterogeneous data and r-atrain is not more suitable data structure than r-train if the data are homogeneous.