Introduction to Data Structures: Lecture 4

Department: MCA
Semester    : II

Subject       : Data Structures through C++

Paper          : CCMCA 203

Faculty       : Avinash Kumar

   Syllabus covered in  this blog

      Data structures: Classification, Operations & Applications

Data Structures:

A data structure is a specialized format for organizing, processing, retrieving and storing data. While there are several basic and advanced structure types, any data structure is designed to arrange data to suit a specific purpose so that it can be accessed and operated in appropriate ways.

Data Structure is a way of collecting and organizing data in such a way that we can perform operations on these data in an effective way. Data Structures is about rendering data elements in terms of some relationship, for better organization and storage.

Classification of Data Structures:

Primitive:

Primitive Data Structures are the basic data structures that directly operate upon the machine instructions. They have different representations on different computers. Integers, character constants, string constants, etc. come under this category.

Non-primitive:

Non-primitive data structures are more complicated data structures and are derived from primitive data structures. They emphasize on grouping same or different data items with relationship between each data item. Array, List, etc., come under this category.

Linear:

 In Linear data structure, the data items are arranged as well as accessed in a linear manner. Array, Stack, Queue come under this category.

Non-Linear:

In Non-Linear data structure, the arrangement and accessibility of data items is random. Tree and Graph come under this category.

Homogeneous:

In homogeneous data structure, all the elements are of similar type. Array comes under this category.

Non-Homogeneous:

In Non-Homogeneous data structure, the elements are of different type. Structure, Class, etc., come under this category.

Static:

Static data structures are those whose storage is associated with fixed memory locations i.e. their storage space is allocated during the compile time. For example: Array.

Dynamic:

Dynamic data structures are those whose storage is associated with variable memory locations i.e. their storage space is allocated during the runtime or the execution time. For example: Linked List.

Basic operations on data structures

Traversing:

This operation is used to access each data item exactly once so that it can be processed.

Searching:

This operation is used to find out the location of a given data item if it exists in the given collection of data items.

Inserting:

This operation is used to add a new data item in the given collection of data items.

Deleting:

This operation is used to delete an existing data item from the given collection of data items.

Sorting:

This operation is used to arrange the data items in some specified order i.e. in ascending or descending order in case of numerical data and in dictionary order in case of alphanumeric data.

Merging:

This operation is used to combine the data items of two sorted collection of data items into one.

Applications of Data Structures

1.           Queues are used during inter-process communication.

2.           Stack is used when a function call is initiated.

3.           Circular Linked lists are used in time sharing problem used by the scheduler during the scheduling of the processes in the operating system.

4.           Heaps are used to implement priority queues, which are used for scheduling processes by operating system.

5.           Binary Search Trees are used for implementing maps and sets.