Recent Posts

Thursday, 28 December 2017

Introduction to Data Structures


What is Data Structure?
     Whenever we want to work with large amount of data, then organizing that large amount data is very important. If that data is not organized effectively, it is very difficult to perform any task on that data. If that data is organized effectively then any operation can be performed easily on that data. A data structure can be defined as follows:
     "Data structure is a method of organizing large amount of data more efficiently so that any operation on that data becomes easy". Based on the organizing method of a data structure, data structures are divided into two types. 
1. Primitive Data Structures
2. Non-Primitive Data Structures
1. Primitive Data Structures
* Primitive data structures are the data structures available in most of the programming languages.
* These data structures are used to represent single value.
* Primitive Data Structures are the basic data structures that directly operate upon the machine instructions. 
* Integers, floating point numbers, character constants, string constants, Boolean constants and pointers come under this category.

Data Types
     In java every variable and every expression should has some type. Each and every type is clearly defined. Every assignment should be checked by compiler for type compatibility. Because of above reason we can conclude Java language is Strongly typed programming language. 
     Java is not considered as pure object-oriented programming language. Because several OOP principles are not satisfied by Java (like operator overloading, Multiple inheritance etc.). Moreover, we depending on primitive data types which are not objects.
     Based on the data type of a variable, the operating system allocates memory and decides what can be stored in the reserved memory. There are two data types available in Java:
1. Primitive Data Types
2. Reference/Object Data Types 
To Learn more about above 2 data types Refer Java Language Fundamentals

2. Non-Primitive Data Structures
* Non-primitive data structures are more complicated data structures and are derived from primitive data structures.
* Non-Primitive data types are used to store group of values.
* Array, Stack, Queue, Lists, Graphs etc. Comes under this category.
* Non-Primitive Data Structures again divided into 2 types
    * Linear Data Structures
    * Non - Linear Data Structures

1. Linear Data Structures
     If a data structure is organizing the data in sequential or linear order, then that data structure is called as Linear Data Structure. Data elements in a liner data structure are traversed one after the other and only one element can be directly reached while traversing.  Examples of linear data structures are Array, Stack, Linked List and Queue.

Operations on linear Data Structures
1. Traversal: Visit every part of the data structure
2. Search: Traversal through the data structure for a given element
3. Insertion: Adding new elements to the data structure
4. Deletion: Removing an element from the data structure.
5. Sorting: Rearranging the elements in some type of order (e.g Increasing or Decreasing)
6. Merging: Combining two similar data structures into one.

2. Non - Linear Data Structures
     The data structure where data items are not organized sequentially is called Non-Linear data structure. In other words, if a data structure is organizing the data in random order, then that data structure is called as Non-Linear Data Structure. Examples of Non-Linear data structures are Tree, Graph, Dictionaries, Heaps etc.

Abstract Data Types (ADTs)
     Before defining abstract data types, let us consider the different view of system-defined data types. We all know that, by default, all primitive data types (int, float, etc.) support basic operations such as addition and subtraction. The system provides the implementations for the primitive data types. For user-defined data types we also need to define operations. The implementation for these operations can be done when we want to actually use them. That means, in general, user defined data types are defined along with their operations.
     To simplify the process of solving problems, we combine the data structures with their operations and we call this Abstract Data Types (ADTs). An ADT consists of two parts:
1. Declaration of data
2. Declaration of operations
     Commonly used ADTs include: Linked Lists, Stacks, Queues, Priority Queues, Binary Trees, Dictionaries, Hash Tables, Graphs, and many others. For example, stack uses LIFO (Last-In-First-Out) mechanism while storing the data in data structures. The last element inserted into the stack is the first element that gets deleted. Common operations of it are: creating the stack, pushing an element onto the stack, popping an element from stack, finding the current top of the stack, finding number of elements in the stack, etc.
     While defining the ADTs do not worry about the implementation details. They come into the picture only when we want to use them.

2 comments: