Above, I attached a table of common data structure operations from Big-O cheat sheet . And we will focus on Array for now.
As you can see, there are four operations to take notice of. Those are access, search, insertion, and deletion. With each of these actions, there's Big-O notation to indicate their time complexities.
Let's think of these operations in the example of our library books.
- If you want to grab a book from the bookshelf, and you know exactly where it is, it will only take one step to get there. It really doesn't matter how many books there are in the library. You'll just focus on the one item that you already have a code of.
- If you don't know yet what you are looking for. If you are, like me, wandering the library in hope of encountering a good book, you will, theoretically, look through each of the books, until you find a good one. The worst case is that we will go through every book of a library, which is unlikely to happen because we are "rational" human.
- If you want to add a new book to your library, what do you do? Here, let's assume that your bookshelves fit perfectly with the books you are having. Every book has a fixed place on the shelf, and you want to add a new book on the third row. What you need to do, when there's no extra space, is that you have to shift everything from the third row down to the second row and then the last row. You have to shift everything after the place you insert a new book just to make room for it. The worst case is when you want to add the book at the beginning of all shelves, and you'll have to shift the entire library to make space for such an insignificant newcomer.
- Last but not least, you gotta get rid of a book... It's not an idea book-lovers would love, but let's assume you take books out to donate sometimes. How long does it take? What is the time complexity of doing such a thing? When you take out a book, you'll have to fill in the empty space left behind by that book. This means that you'll shift the entire library to the left one space, and this will be a hazard when your library has millions of books.
Source: news.blogs.lib.lsu.edu
A library, as I said, is a good example of an array. Accessing element in an array will only take O(1) time because it doesn't matter how many books are there, you'll go ahead and get to that book on your first trial since you already know what the location is. In contrast, searching, inserting, and deletion will take O(n) time in the worst case (remember when talking Big-O, we mean worst case) because these operations involve working through your entire library.
Source: thecrazyprogrammer.com
So here, what's the pros and cons of an array?
The idea of accessing with O(1) time is really great, and this is the pros of an array. As we'll learn later on, a linked list or other data structures might not have such an advantage.
However, if we want to perform other operations, it'll cost greatly. This is the reason why in many cases, it's important we understand a variety of data structures (or storages) to get the best result.
In the next blog post, I'll go into linked list. Such a data structure will resolve some of our problems, but it'll have the disadvantage of hard to access, unlike arrays. I'll see you then.