Introduction to Data Structures | Raveling Tech

Data Structures


    What is Data Structure?

    A data structure (DS) is a way of organizing data so that it can be used effectively. It is a way of organizing data in some fashion so later on it can be accessed reread or update the data quickly and easily. 

    Why Data Structure?

    They are essential ingredients in creating fast and powerful algorithms. They help to manage and organize data. They make code cleaner and easier to understand.

    Abstract Data Types Vs Data Structure.

    Abstract Data Types (ADT) is the logical view of data and the operations to manipulate the data while Data structure is the actual representation of data and the algorithms to manipulate the data.

    Abstract Data Type.

    An abstract data type (ADT) is an abstraction of a data structure which provides only the interface to which a data structure must adhere to. The interface does not give any specific details about how something should be implemented or in what programming language.

    Examples

    Abstractions (ADT) Implementation (DS)
    List Dynamic Array
    Linked List
    Queue Linked List Based Queue
    Array Based Queue
    Stack Based Queue
    Map Tree Map
    Hash Map / Hash Table
    Vehicle Golf Cart
    Bicycle
    Smart Car


    Advantages of Data structures.

    Efficiency: The efficiency of a program depends on the proper choice of the data structure according to the condition. For example: If you want to have to perform insertion and deletion operation more frequently then it is better to use Linked List than an array.

    Reusability: Data structure can be used again and again after its implemented once. You can save the implementation of any particular data structure into libraries.

    Abstraction: ADT provides the level of abstraction to a data structure so the client can use a different data structure without knowing about the actual implementation process.

    Linear and Non-Linear Data Structure.

    Linear Data structure: In linear data structure all the elements are arranged in a linear order. In the linear data structure, every element has only one successor and one predecessor, except the first and the last element. Example: Array, Linked list, Stack, and Queue.

    Non-Linear Data structure: In the non-linear data structure, the elements are not arranged in linear order. Example: Trees and Graphs.

    Static and Dynamic Data structure.

    Static data structure: Memory allocation is done at compile time in a static data structure. The maximum size of the static data structure is fixed and it cannot be changed at run time. It provides faster access to elements but insertion and deletion are quite expensive. Example: Array

    Dynamic Data structure: Memory is allocated at run time in a dynamic data structure. The size of the dynamic data structure is not fixed, they are flexible in size. It allows faster insertion and deletion but access to elements is quite expensive. Example: Linked List

    Computational Complexity Analysis.

    As programmers, we often find ourselves asking the same two questions over and over again:

    • How much time does this algorithm need to finish?
    • How much space does this algorithm need for its computation?


    To standardize the way of talking about how much time and how much space is required for an algorithm to run computer scientist has invented Asymptotic notations like Big-O Notation, Big-Omega, and Big-Theta but we are mostly interested in Big-O Notation.

    Big-O Notation: Big-O Notation gives an upper bound of the complexity in the worst case, helping to quantify performance as the input size becomes arbitrarily large.

    For example, we have an unordered list of unique numbers and you are searching for the position of the number 7 on that list. If you search the list linearly then the worst case is when the number is present at the last in the list.

    Big-O Properties.

    • O(n+c) = O(n)
    • O(cn) = O(n), c > 0 we just ignore the constants.

    Let f be a function that describes the running time of a particular algorithm for an input of size n:
    f(n) = 7log(n)^3 + 15n^2 + 2n^3 + 8
    O(f(n)) = O(n^3), because the n^3 is the most dominant term in the above equation. 

    Big-O Notation.
    Big-O

    If you like this post and find it useful then you can show your support by donating a small amount from your heart. You can also show your support by following us on Facebook and Twitter. 

    Post a Comment

    Previous Post Next Post