Amazon Prime

  • Data Structure

    Data Structures with Real Time Examples


    Data structure is a collection of elements of a specific data type(primitive or non-primitive) in which the elements can be accessed efficiently. Data structure is a format for storing and manipulating the data. In simple words data structure is a way of storing data in memory.

    To design an algorithm, data structure plays a vital role as the computational complexity and efficiency of the algorithm always depends on the data structures that are being used for the algorithm. The choice of data structure should be considered the one which effectively processes the data.



    Real Time Examples

    • For instance if we goto any ticket counter, there will be two open points, one is entry and other is exit. At exit point tickets will be issued and the person who is near the exit point will collect the ticket and leave the premises. If we notice, whoever enters first will leave first. This is called First in First out (FIFO order). Queue is the data structure which maintains FIFO order.

    • To store undo/redo operations in word processors like notepad, Stack is the efficient data structure being used.

    • To design a phone directory, in which for every name there will be one or more than one phone number. When we want to search for a phone number, based on the letter which we enter, the names will be filtered and the results will be shown. Trie is the efficient data structure to use this use case.

    • Any social network like Facebook or Instagram in which each user is connected to his/her friends, and each friend again has some connections. Graph is the efficient data structure to implement any social network.

    Video Explanation

    Abstract Data Type (ADT)

    Data Type

    In computer science data type is a classification which specifies what kind of data a variable is stored. Examples : int, float, double etc.

    For instance, if we want to represent a student’s age, we can represent the age of the student using a variable which is declared using int. Similar way to represent student gender in computer science we can use with single character F or M, here char data type is used. To represent student name char array is being used.

    User Defined Data Type

    Suppose if we want to represent a point in geometry, and we know that each point comprises x coordinate value and y coordinate value, with normal data type this is not possible and in these cases we tend to use User Defined Data Types. In user defined data types, values and operations are not defined in language itself and the user is responsible to define both values and operations depending on the need or use case. User defined data type allows to declare multiple data types in a wrapped way. If we consider student examples, each student has name, age, gender and if we want to combine all these values in a wrapped manner, user defined data type is being used.

    In C language user defined data types are implemented by using struct, union, enum etc, Incase of java programming user defined data types are developed by using the features of classes and interfaces.

    1. java
    2. c

    1// User Defined Data type Student in JAVA
    2public class Student {
    3 String name;
    4 int age;
    5 char gender;

    Abstract Data Type (ADT)

    An abstract data type is a mathematical model of a data structure that describes the type of data stored and the operations supported. Abstract data type specifies what each operation does but not about how they are implemented. Abstract data type talks about logical views of the data structures not about implementation. To make a user defined data type to ADT, we should be able to perform few operation which are mentioned below :

    • Insert : Add an element to the data structure
    • Delete: Delete an element from the data structure
    • IsEmpty : checks whether the data structure has any element in it or not

    Examples : Stack, Queue, Linked List etc.

    Data Structures Classification

    Based on the organization of the elements, data structures are classified into two types :

    Linear Data Structure

    In Linear data structure, the elements are connected in a linear fashion. For example, in case of arrays, the elements are arranged in contiguous memory locations, whereas in case of linked lists, linear structure between elements represented using pointers or links between the elements. Examples : Arrays, LinkedLists, Stacks and Queues

    Non Linear Data Structure

    In Non-linear data structure, the elements are not arranged in a sequence, rather the elements form hierarchical order. Examples : Trees, Graphs, Tables and Sets

    Data Structures Classification

    Linear vs NonLinear DataStructures

    Linear Data StructuresNon-Linear Data Structures
    Elements are related to each other in linear fashion Elements form hierarchical order
    Elements can be accessed in single traversal All elements are not able to access in single traversal
    Implementation of linear data structure is easy Implementation of non-linear data structure is complex
    Memory utilization is not effectiveMemory utilization is effective
    Examples: Array, Linked list, Stack, Queue Examples: Tree, Graph

  • Data Structure