Arrays Or Linked Lists?

Arrays Or Linked Lists?

Arpan Pandey
·Jan 16, 2022·

4 min read

Subscribe to my newsletter and never miss my upcoming articles

Play this article

Table of contents

  • How data is stored in memory?
  • An Array
  • A Linked List
  • What should I choose?
  • But, which should I choose?
  • Concluding...

Data is stored in memory from the hard drive to memory, it is accessible to the computer at all times. To store data in memory we use 3 types of data structures, namely array, linked list and hash table. We will discuss how is data stored in memory. Then we will discuss how arrays and linked lists work? We will also discuss the advantages and drawbacks of each.

How data is stored in memory?

Let's start by picturing how data is represented in memory, visually. MemoryVisualisation.png As you can see, the data is kept in a kind of cell (a byte) of data. We can use that as a reference. Now, let's get to what are arrays and what are linked lists.

An Array

In an array, the data is stored in a continuous space. Let's imagine this space as a set of drawers. Drawers1.png Now you put your stuff in the first two drawers. This little setup here represents an array of size 2. This is all there is to it. An array is just a continuous list, if you will, of stuff. But then, what is a linked list?

A Linked List

Now coming to linked lists. A linked list is a list that is not continuous. One item may be here, one there. This is by design. Let's go back to our drawers example. Drawers2.png In this arrangement, you put stuff in any random drawer that is free. But, you may ask then, how will we know where the next thing is?
Every item (or drawer) has an address of where the next one is. And this is where the linked in the linked list comes from.

What should I choose?

Note:- Remember that a computer cannot look at more than one part in the memory. So considering that we can go ahead.

Let's get, once again back to our drawers example. Let's say you want to add something to our array. But, when you go to add it, you discover that the next drawer is occupied. Drawers3.png What can you do now? Well, the only thing that can be done in this case, that is if it is an array, is to move the entire array to a place where enough continuous drawers are available. Drawers4.png Quite troublesome, isn't it? These are the drawbacks of an array. Let's see how does a linked list perform, shall we?
In a linked list, you don't need to move stuff. You can just put stuff in a drawer and tell the drawer before it where the next one is. Drawers5.png Interesting, isn't it? But, what are the trade-offs?
Well, to begin with, you have to go through every drawer to get to the drawer you need. Also, it takes a lot of memory to remember where the next drawer is. Confused? Good.

  • First of all, since only the previous drawer knows where the next drawer is. We would need to go through every drawer to go to the next, so we would need to, essentially, iterate through all the elements in the list. In an array, you can just say I want to go to the nth element and boom you are there.
  • Also, you need to store the pointer (or the number of the drawer in our case) of the next drawer in the list. This takes up essential space. While in an array, you can just compute that the nth element is there, saving up a lot of space.

But, which should I choose?

Well, as always, it is a trade-off. Let's put it here again in brief.

  • If you need to constantly access items randomly and not need to add that many items. You are better off with an array.
  • While, if you, for example, need to constantly add elements, can spare some more memory and most importantly go through all the elements each time. You are better off with a linked list.

Concluding...

Well, that's it for today, see you in the next one.

Did you find this article valuable?

Support Arpan Pandey by becoming a sponsor. Any amount is appreciated!

See recent sponsors Learn more about Hashnode Sponsors
 
Share this