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:

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

Comments

[dalacarte]

Please have native English speakers proof read.

[imrinzzzz]

Thank you for the advice, I'll try to be more grammatically correct next time. But one thing, though, I am writing all these articles to serve as a review for me, so I might have slipped. I admit that I might not put in every effort to write this article, but I tried to not write any incorrect fact, at the very least.