Data Structure – Part 1: An introduction

1. Introduction to Data Structure

Data structures are essential part of any programming language that provide a way to organize the data for the program in a way that is efficient and easy to use.

It allows us to perform three basic operation on the data which are adding, accessing and modifying.

Each data structure is designed to be good at one kind of usage pattern, often at the expense of another

The decision of which data structure to use is based on the analysis of how the data is likely to be used.

Following is an overview of data structures which are discussed in details in this series

2. Big O

It’s a kind of framework for analyzing performance, that gives us a sense of how many steps it will take to complete a task or algorithm.

For example, following code result in function of O(n) called “linear time” since it will be executed n times.

//Compute n factorial n!
int NFactorial(int n) 
{
     int result = 1;
     for (int i = n; i > 0; i--)
     {
          result *= i;
     }
     return result;
}

Here are several common running times and their Big O notation, order from fastest to lowest:

Constant time	O(1)
Log n time	O(Log(n))
Linear time	O(n)
Quadratic time	O(n2)
Factorial time	O(n!)

Note:

• When expressing a function’s running time in Big O, only the most significant term of the function is written. E.g. O(n^2 + 2n + 1) = O(n^2)

In general, there are two approaches to complete a certain task

Approach	Consideration
Brute force	Useful with small data sets which doesn’t require any set-up cost
Clever	Useful with big data set in which the hidden costs due to set-up is worthwhile

3. Generic

Generics provide a way to reuse code while still having type safety. Generic was added since C# 2.0.

The <T> bit means a class is a generic class, specialized on some type that will be called T, when someone comes along to use our class, they replace the T with the type whey want.

Code example

class MyGeneric<T> 
{
    private T data;
    public T Data
    {
         get { return data; }
         set { data = value; }
    }
}

MyGeneric<int> data1 = new MyGeneric<int>();
data1.Data = 10;

MyGeneric<string> data2 = new MyGeneric<string>();
data2.Data = "This is awsome!"

To be continued…