Arrays [the easy guy]

I would like to announce the start of a series of articles on Data Structures and Algorithms (DS&A). I will be writing about these topics in the simplest way possible, so please follow along and do not hesitate to send in your questions, arguments, and corrections.

I am assuming that if you are reading this, you have a basic understanding of the fundamental data types in computing and you are proficient in writing Python code. I will be using Python to demonstrate examples and write code throughout the series.

I hope you find this series informative and helpful. Please let me know if you have any feedback.

What is an Array

An array is a data structure that stores a linear collection of elements of the same data type in contiguous memory locations. This means that the elements of an array are stored next to each other in memory, and they all have the same data type. For example, an array could store the numbers 1, 2, 3, 4, and 5, all of which are integers.

Arrays are indexed, which means that each element in the array has a unique identifier called an index. The index is used to access the element in the array. For example, the index 0 refers to the first element in the array, the index 1 refers to the second element, and so on.

Arrays are a fundamental data structure that are used in a wide variety of applications. For example, arrays are used to store the elements of a list, the characters of a string, or the numbers in a mathematical equation.

In the above diagram, we see a linear collection of integers with their indexes beside them. In computing, we are all aware of the 0-indexing convention, which means that the first element in an array is indexed as 0, not 1. As a result, while there are 5 elements in the array, the highest index is 4.

Arrays are linear, which means that the elements are stored in a single, continuous sequence. This makes it very easy to traverse an array, as you can simply iterate over the elements using a for loop.

Arrays can also be quickly and easily searched, as you can use a linear search algorithm to find the element you are looking for. Insertion and deletion are also relatively quick, as the elements can be simply moved to make room for the new element.

Sorting is slightly more complex, as it requires you to compare each element to the elements around it. However, there are many efficient sorting algorithms that can sort an array in linear time.

Arrays are a versatile data structure that can be used in a wide variety of applications. They are particularly useful for storing and manipulating collections of data that are accessed in a sequential order.

Types of Arrays

There are two main types of arrays: static arrays and dynamic arrays.

Static arrays are arrays that have a fixed size. This means that the number of elements in the array cannot be changed after the array is created. Static arrays are allocated on the stack, which means that they are stored in a fixed area of memory.

Dynamic arrays are arrays that can grow and shrink in size. This means that you can add or remove elements from the array after it is created. Dynamic arrays are allocated on the heap, which means that they are stored in a variable area of memory.

In Python, lists are dynamic arrays. This means that you can add or remove elements from a list at any time.

When a dynamic array reaches capacity, it will be reallocated to a larger size. This can cause a performance penalty, so it is important to choose the right size for your dynamic array.

//array example
array_ex_int = [1,2,4,8,16]
array_ex_st = ['John', 'James', 'Max']

//to show static arrays 
//i.e there are no static arrays in python
static_ex = [0]*(5)
//[0,0,0,0,0]

dynamic_ex = array_ex_st.append('Mary')
//['John', 'James', 'Max', 'Mary']

Array Slicing

Arrays can be dissected and segmented by leveraging their indices as references. The process of array slicing essentially entails extracting a subset of the array and allocating a fresh array in memory specifically for that subset. It is important to bear in mind that by harnessing the principle of zero indexing, one can conveniently access the desired number of elements through array slicing.

array_ex = [1,2,4,5,6]
new_array = array_ex[1:4]
print(new_array)
//[2,4,5]

Please note that when performing array slicing, it is crucial to remember the syntax [start: stop:step]. In other words, the slicing operation commences at the start index and concludes at the stop-1 index. For instance, if the stop value is 4, as demonstrated in our example, the slicing process terminates at index 3, as indicated above.

Operations on Arrays and their time cost

Here are some of the most common operations carried out on arrays and their time and space cost implications: