## DEV Community

imrinzzzz

Posted on • Originally published at medium.freecodecamp.org

# Introduction to Data Structure

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!

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

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(nd ).

#### 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 data1; O(N/2) Slow (same process, except linear search; O(N))
##### Syntax in Java

::Creating an array::

``````int[] intArray;
intArray = new int[100];
``````

or

``````int[] intArray = new int[100];
``````

::Accessing Array elements::

``````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. Β β©