Introduction to Data Structure
Tags: datastructure, muict
Published: 2018-08-25 03:19:55

---
title: Introduction to Data Structure
published: true
description: overview and array (simple data structure knowledge xD)
tags: data structure, MUICT 
---

Since we're in the era where we deal with LOTS and lots of information, we need some efficient ways to deal with them. In computer science, we will learn how to manipulate data and/or solve computational problems (like algorithm) in data structure!

#### Still don't get the picture?
Think of the library, it would take you all day (at least) to find a book in a messy library. But if every position of the books is marked and recorded, or the books are neatly arranged, then it would take less than a minute to find a book!
![hehe](https://thepracticaldev.s3.amazonaws.com/i/o3ndywoev0ajs5sz09h3.png)

Now, this post will cover an introduction of _array_ and _big O notation (Asymptotic Upper Bound)._ Let's start with **Big O**.

---

#### Analysis of **Algorithm**
 - Talks about _time_ and _space_.
 - We use the term **big O** -> Asymptotic Upper Bound (Big O notation)
    - The greatest or maximum term in function
![Big O comparison](https://cdn-images-1.medium.com/max/1200/1*HwLR-DKk0lYNEMpkH475kg.png)

> Properties: 
> - Transitivity : if f(n) = O(g(n)), and g(n) = O(h(n)), then f(n) = O(h)n)) also.
> - Sums of function : if f(n) and g(n) = O(h(n)), then f(n) + g(n) = O(h(n)).
> - Polynomial : let f(n) be the polynomial of degree "d", then f(n) = O(n^d ).

for more information, [click here](https://medium.freecodecamp.org/my-first-foray-into-technology-c5b6e83fe8f1)!

#### Array
As I've said, there really are many ways to store the data, and array is one of them. But it is the very fundamental data structure. Now let's look at its property.

> Properties: 
> - data stored _contiguously_
> - data accessible by an index (e.g. A[i])
> - The size of the array is determined beforehand (meaning it's fixed)

There are _two_ types of array; _ordered and unordered_. What's the different? Well, the difference can be seen in the time and algorithm used to do some operations.

> Basic operations: 
> - Insertion
> - Searching
> - Deletion

And here's the table to compare the two: 

| | Ordered Array | Unordered Array |
|    :----:    | ---- | ---- |
| **Insertion** | **Slow** (Because you have to search first, then you might have to move the element/data in the array to put the data in) | **Quick** (Just add to the latest position; O(1) |
| **Searching** | **Quick** (if you use binary search; O(logN), but still slow using linear search; O(N/2) -> average time used) | **Slow** (can only use linear search; O(N/2)) |
| **Deletion** | **Also Slow** T_T (Search the chosen data using binary search; O( logN), delete, then move all the data[^1]; O(N/2) | **Slow** (same process, except linear search; O(N)) |

#####Syntax in Java

::Creating an array::
```java
int[] intArray;
intArray = new int[100];
```
or
```java
int[] intArray = new int[100];
```
::Accessing Array elements::
```java
temp = intArray[4];
intArray[25] = 7;
```

[^1]: After the deletion, there will be a space between data, so the data has to be moved so there won't be a gap because _arrays are contiguous_.