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(n^d ).

for more information, click here!

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:

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.  ↩