Array

Unlike fragmented Linked List, a classic Array occupies contiguous Memory Cells. In low-level languages, every piece of Data usually has the same Type across the whole Array, so you cannot mix Strings with Numbers or Booleans inside the same raw array. Higher-level languages may expose more flexible list-like structures, but the core idea is still indexed storage. Each element in this collection is identified by the Index.

Quick Access To Elements

Thanks to its linear, continuous and fixed-length character, this Data Structure gives constant-time access when you already know the Index.

Picture shows an Array which contains 10 elements. Each of them is String (Character) and together they make String “HELLOWORLD”. Above there are Memory Cells numbers, below you can see Indexes. It’s worth to mention that Array is also called a table. Well, why not - it has columns and one row, thus table seems proper definition. In the following part, you will see that this structure can be even more table than in example above.

In programming, if we want to declare an Array we need to assign it to the variable. In Python this example is really a list, not a low-level fixed array, but it is good enough to show indexed access:

greetings = ["H", "E", "L", "L", "O", "W", "O", "R", "L", "D"]

Now, if we want to get value of the third element, we have to call it by its Index value. Since Arrays are zero-based, meaning their first Index value is always zero, for the third element Index value will be equals to 2. Instruction below will print Character “L” to the screen.

print(greetings[2])

Looking at dimensions-wise, above Array is called a one-dimensional (1D). It has one row, it is processed linearly.

Dimensions

One of the most important facts about Array is that it can be multidimensional. So far you have learned about one-dimensional form of this structure, let’s find out about the others.

2D Array

Two-dimensional Array is a first-class table. Every element has its “coordinates”, which is row’s and column’s Index value. It may be confusing at first how to store multidimensional structure in linear memory, but don’t worry, it will become clear in a minute.

On the figure below there are two items. First one visualizes 2D Array as rows and cols, second one show how such structure is stored in a memory.

When it comes to Python code, we declare it as follows:

hello = [["H", "E", "L"], ["L", "O", "J"], ["O", "H", "N"]]

Now, we want to print the last character of our greetings, this is how it can be done:

print hello[2][2]

3D Array

Adding third dimension means to extend a 2D Array with a depth parameter next to existing width and height. Three-dimensional arrays can represent images, volumes, simulations, or any data with three coordinates. A color image is often treated like height, width, and channel, where the channel may hold RGB values. Because the third dimension is fairly complicated it won’t be covered in details in this tutorial.

Operations

Linked List is slow when it comes to read values, but it shines when insertion or deletion are made. In case of Array it’s quite contrary. Thanks to the direct mapping between Memory Cell Address and array Index, we can access desired element in constant time when know Index beforehand. Remember, Array is a fixed-length structure. When it comes to Insertion or Deletion, next to appending or popping element we have to shift all existing elements, so they are allocated continuously. Such an operation is extremely expensive.

Summary

Yet another DS for you to know. As you perceive, Linked List and Array have quite different characteristics. LL is good choice when you deal with Data which is mostly written and deleted. Its length is also dynamic, what gives you more freedom than Array. On the other hand, Array’s length is fixed what gives the advantage of ultra-fast read, but inserting and removing elements from it is expensive.