On Data Structures: Arrays or Linked Lists?

In computer science, one can organize data in many different ways. When I say data, I mean any kind of data whatsoever. The data could be names of restaurants, lists of students with their grades, or words in a dictionary.

When the amount of data to be stored is small, the data structure you use to organize it is not all that important. However, when you have a lot of data to be stored, your data structuring becomes quite relevant. The structure the data is stored in directly impacts how much room the data takes up on a computer, how quickly anything can be retrieved from it, and how long it takes to add or remove data.

Two of the simplest data structures are arrays and linked lists. In this article, I will be describing the benefits and drawbacks for each.

Pros and Cons

Say you have a big list of possible franchises that you could invest in. You designed a program to go around the internet and put all possible franchise opportunities into a list for you, and it turns out that you came out with a really, really big list.

You want to search through the list and find the best franchise opportunities, but you absolutely don’t want to go look through each option one at a time. It would take forever to look at each franchise, see if the investment matches your budget, then compute the return on it.

So you decide to have the computer organize this huge list by the dollar amount each franchise requires for your investment. That way, you can completely ignore any franchises that want more than you can give or want less than you think is worth the effort.

You have the option of making a linked list or an array to contain all these franchises.

The largest benefit to having an array of items is that you can access any point in the array instantly. If you wanted the 1578th item, you could access it just as quickly as you could access the 7th item. With linked lists, you need to access every item before the item you’re searching for, so accessing the 100th item take 10 times as long as accessing the 10th.

The major drawback to having an array, however, is that in order to have this instantaneous access time, your computer had to store all that information in one big clump of memory. So, if each franchise took 10 KB to store and you had 1,000,000 of them, your computer would have to find a place in your hard drive with 10,000,000 KB (kilobytes) of empty space.

If you had to store 1,000,000 franchises in a linked list, each link on the list has a reference to the next one, so they don’t have to be next to each other in memory. Your computer only has to find 10 KB of empty space in your hard drive, but it needs to do it 1,000,000 times.

In this situation, I personally would have chosen neither. There are other data structures that would suit this need better. If forced to choose between the two, however, I usually tend to favor arrays because memory is cheap these days. It isn’t that hard to find 10,000 KB of sequential free space on a 2 TB (terabyte) hard drive.

Leave a Reply

Your email address will not be published. Required fields are marked *