Unit 1: Introduction to Data Structures & Algorithms

1.1 Data types, Data structure, and Abstract data type

   Introduction to Data Structures and Algorithms

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. For example, we have some data which has, player's name "Paras" and age 30. Here "Paras" is of String data type and 30 is of the integer data type.

We can organize this data as a record like Player record, which will have both player's names and ages in it. Now we can collect and store player's records in a file or database as a data structure. For example "Sarad" 28, "Sompal" 25, "Sandip" 20

If you are aware of the Object-Oriented Programming concept, the class also does the same, it collects the different types of data under one single entity. The only difference being, data structures provides for techniques to access and manipulate data efficiently.

In simple language, Data Structures are structures programmed to store ordered data, so that various operations can be performed on it easily. It represents the knowledge of data to be organized in memory. It should be designed and implemented in such a way that it reduces the complexity and increases the efficiency.

The Video below is helpful in building the concept of data structures.



Data Type and Abstract Data Type

The Data Type is basically a type of data that can be used in a different computer program. It signifies the type like integer, float, etc, the space like integer will take 4-bytes, the character will take 1-byte of space, etc.

The abstract data type is a special kind of datatype, whose behavior is defined by a set of values and a set of operations. The keyword “Abstract” is used as we can use these data types, we can perform different operations. But how those operations are working that is totally hidden from the user. The ADT is made of primitive datatypes, but operation logics are hidden.

Some examples of ADT are Stack, Queue, List, etc.

Let us see some operations of those mentioned ADT −

  • Stack −
      • isFull(), This is used to check whether the stack is full or not
      • isEmpty(), This is used to check whether the stack is empty or not
      • push(x), This is used to push x into the stack
      • pop(), This is used to delete one element from the top of the stack
      • peek(), This is used to get the topmost element of the stack
      • size(), this function is used to get a number of elements present into the stack
  • Queue −
      • isFull(), This is used to check whether the queue is full or not
      • isEmpty(), This is used to check whether the queue is empty or not
      • insert(x), This is used to add x into the queue at the rear end
      • delete(), This is used to delete one element from the front end of the queue
      • size(), this function is used to get a number of elements present into the queue
  • List −
      • size(), this function is used to get a number of elements present into the list
      • insert(x), this function is used to insert one element into the list
      • remove(x), this function is used to remove given element from the list
      • get(i), this function is used to get the element at position i
      • replace(x, y), this function is used to replace x with a y value
  • The Video below is helpful in building the concept of data structures.


                    1.2 Dynamic memory allocation in C
                    1.3 Introduction to Algorithms
                    1.4 Asymptotic notations and common functions
                    Lab: Write a program to implement dynamic memory management functions [malloc(), calloc(), realloc() and free()]