Unlike fragmented Linked List, Array needs to occupy contiguous Memory Cells. Every piece of Data must have the same Type across whole Array, thus you cannot mix Strings with Numbers or Booleans. Each element in this collection is identified by the Index (you already know this term).
Quick Access To Elements
Thanks to its linear, continuous and fixed-length character, this Data Structure lets you navigate between elements with no time.
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. If we use Python, it will look like this:
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 are mostly used to represent an image. For every pixel there is three-element 1D Array containing RGB values. Because third dimension is fairly complicated it won’t be covered in details in this tutorial. We will come back later to this topic during image processing lessons.
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 form it is expensive.