Welcome to Edukum.com

lntroduction: Data Types, Data Structures and Abstract Data Types

There are a number of ways to write programs. They must, in general, have the following characteristics:

  • Easy to read and understand
  • Easy to debug
  • Easy to modify

Correct Program
One which runs in accordance with specifications.
Efficient Program
One which takes minimum time and memory.
Better running times will generally be obtained from the use of the most appropriate data structures and algorithms, rather than through removing a few statements by some clever coding.
Data types
A data type in a programming language is a set of data with values having predefined characteristics. Examples of data types are the integer, floating point unit number, character, string etc.
Computer memory is all filled with zeros and ones. If we have a problem and wanted to code it, it’s a difficult task to provide the solution in terms of zeros and ones. To facilitate the users (programmers), programming languages and compilers are equipped with data types.
For example, integer takes 2 bytes, float takes 4 bytes (actually dependent on the compiler) etc. This means that, in memory, we are combining 2 bytes and referring it as an integer. Similarly, a combination of 4 bytes is called as a float. A data type reduces the coding effort. Generally, at the top level, there are two types of data types:

  1. System defined data types (Primitive data types)
  2. User-defined data types

System defined data types (Primitive data types)
Data types already defined by the system are called primitive data types. The primitive data types provided by most of the programming languages are int, float, char, double, bool, etc.
The number of bits allocated for each of the primitive data types depends on upon the programming languages, compiler, and the operating system. For the same data type, different languages may use different memory sizes. Depending upon the size of the data types, the total available domain will also change. For example, if ‘int’ takes 4 bytes, then the possible values are between -231 to 231-1. Same is the case with other data types.

User-defined data types
In case the primitive data types are not enough, most of the programming languages allow the users to define their own data types called user-defined data types. Some examples are ‘structures’ in C/C++ and ‘classes’ in Java.
An example of a user-defined data type is shown below. This particular example shows a structure with the name ‘myType’. This gives more flexibility and comfort in dealing with computer memory.
struct myType {
int data1;
float data2;

char data;
};

Data Structure
Data structure is a particular way of storing and organizing data in a computer memory (or sometimes on a disk) so that it can be used efficiently. It means a data structure is a specialized format for organizing (arranging) and storing data. Usually, efficient data structures are key to designing efficient algorithms. Data structures can be used to organize the storage and retrieval of information stored in both main memories and in secondary memory.
General data structures include arrays, linked lists, stacks, queues, trees, graphs and so on.Depending on the organization of the elements, data structures are classified into two types:

  • Linear data structures
    Elements are accessed in a sequential order but it is not compulsory to store all elements sequentially. Examples: linked lists, stacks, and queues.
  • Non-linear data structures
    Elements of this data structure are stored/accessed in a non-linear order. Examples: trees and graphs.

Abstract Data Types (ADTs)
ADT is, roughly speaking, a way of looking a data structure: focusing on what it does, and ignoring how it does it. In an ADT, the concept of a certain kind of data structure is separated from the underlying implementation. ADTs are introduced to simplify the process of solving the problems by the combination of data structures along with their operations. An ADT consists of two parts:

  • Declaration of data
  • Declaration of operations

Commonly used ADTs include
Linked lists, stacks, queues, priority queues, binary trees, dictionaries, disjoint sets, hash tables, graphs, etc. For example, stack uses LIFO (Last-In-First-Out) mechanism data structure notes while storing the data. The last element inserted into the stack is the first element that goes deleted (popped). Common operations of it can be:

  • creating the stack
  • pushing an element onto the stack
  • popping the element from the stack
  • finding the current top of the stack
  • finding number of elements (size) in the stack, etc.

While defining the ADTs implementation details need no care. They come into picture only when we want to use them. Different kinds of ADTs are suited to different kinds of applications, and some are highly specialized to specific tasks. We want our stack to perform the required tasks, and ignore how it has been implemented (using an array or a linked list).

Advantages of Abstract Data Typing

  • Encapsulation
    To use the ADT, the user doesn’t need any technical knowledge of how the implementation works. This provides the abstraction of implementation in a simple interface when it is actually used.
  • Localization of change
    Code using an ADT object won’t be edited in case the implementation of the ADT is modified. As all the changes to the implementation still comply with the interface, changes may be made to the implementation without requiring any changes in code where ADT is used.
  • Flexibility
    Different implementations of the ADT can have all the same properties and abilities, thus are equivalent and can be used interchangeably in code that uses the ADT. This provides a great deal of flexibility when using ADT objects in different situations.

References

  1. Y. Langsam, M. J. Augenstein and A. M Tenenbaum, “Data Structures using C and C++”
  2. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, “Introduction toAlgorithms”
  3. G. Brassard and P. Bratley, “Fundamentals of Algorithms”

© 2019 EDUKUM.COM ALL RIGHTS RESERVED


#Things To Remember



1021 Views