The array is one of the most basic data structures in computer science. We assume that you have worked with arrays before, so you are aware that an array is simply a list of data elements. The array is versatile, and can serve as a useful tool in many different situations, but let’s just give one quick example.

One of the key differences is that arrays have indices, while lists do not. To understand this, it helps to know how arrays are stored in memory. When an array is created, it is always given some initial size - that is, the number of elements it should be able to hold (and how large each element is). The computer then finds a block of memory and sets aside the space for the array. Importantly, the space that gets set aside is one, continuous block. That is, all of the elements of the array are contiguous, meaning that they are all next to one another in memory. Another key characteristic of an array is that all of the elements are the same size. When we represent an array visually, we often draw it as a series of boxes that are all of the same size and all right next to one another.

Because all of the elements are:

  1. next to one another
  2. the same size, this means that if we know the location of the first element, we can calculate the location of any other element.

For example, if the first element in the array is at memory location 00 and the elements are 24 bytes, then the next element would be at location 00 + 24 = 24. And the one after that would be at 24 + 24 = 48, and so on. Since we can easily calculate the location of any item in the array, we can assign each item an index and use that index for quickly and directly access the item.

List Cheat Sheet

Arrays #1 Educative

Name Notes
Remove Even Integers from List Naive method check if it is not even - modulo. If it is odd, the element is appended to a new list. List comprehension
Merge Two Sorted Lists Two indices, then, compare the current elements of both. Next list.insert(i, elem). Append whatever is left of list2 to list1
List of Products of All Elements Multiply everything by everything. From left side multiply every element. Then multiply everything from right side - for i in range(len(lst)-1, -1, -1)
Find Minimum Value in List Sort. Iterative. Sort. Iterative. Merge sort, Split table by half, then recursive calls of merge sort. Two iterators foreach half. While loop to compare, iterate over the list indices. End find minimum
Find Second Maximum Value in a List Initialize two variables max and secondmax to -inf. if the current element in the list is greater than the maximum value, then set secondmax to max and max to the current element
Right Rotate List Pythonic k = k % len(lst)
Rearrange Positive & Negative Values Iterate over the entire list and, if we encounter a negative element, we simply swap it with the leftmost positive element
Rearrange Sorted List in Max/Min Form lst[i] += (lst[maxIdx] % maxElem) * maxElem
Maximum Sum Sublist Kadane’s Algorithm. currentmax for the current list index and a globalmax

Additional materials: