W1301 Arrays

From Coder Merlin
Revision as of 19:42, 23 March 2019 by Chukwuemeka-tinashe (talk | contribs) (Created page with "== Background == === Overview === The '''Array Data Structure''' is a ''collection of elements'' each of which can be identified by an index. An array is stored so that the p...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Within these castle walls be forged Mavens of Computer Science ...
— Merlin, The Coder

Background[edit]

Overview[edit]

The Array Data Structure is a collection of elements each of which can be identified by an index. An array is stored so that the position of the element in memory (or other storage) can be easily calculated based only on the index. For example, consider an array of integers:

Array Data Structure


In this array, each integer requires thirty-two bits (or four bytes). Thus, there are four bytes from the beginning of each element to the beginning of the next element. This allows us to calculate the position of an integer in this array by adding the product of the element index (starting from zero) and the bytes required per element to the foundation address. In this case, the formula would be:

0x0800 + (3 * index)

Arrays are very common data structures and used in almost every program. CPUs generally enable assembly language programs to easily work with arrays. As an example, a base plus index mode enables a program to access an element by storing the foundation address in the base register and specifying the index (scaled by the size of each element) in the index register.

Properties[edit]

As an abstract data type, arrays are:

  • A collection type, meaning that a single variable conceptually “contains” many elements
  • Each item in the data structure is termed an element
  • The collection is ordered, that is, the order of the elements is maintained
  • Elements can be accessed randomly, that is, there is no need to access elements in any particular order
  • The array is homogenous, that is, all of the elements are of the same type


Swift[edit]

An array can be instantiated using a series of literals. For example:

   let oddNumbers = [1, 3, 5, 7, 9, 11]
   var states = ["California", "Florida", "Texas"]

An empty array can be instantiated by explicitly specifying its type:

    var emptyDoubleArray = [Double]()

The first element of a non-empty array is accessed using an index or subscript of 0. For example:

    let firstState = states[0]

One can determine if an array is empty using the isEmpty property and determine the number of items in the array using the count property:

    if !states.isEmpty {
        print("The array contains \(states.count) states.")
    }

A shortcut to access the first and last elements makes use of the first and last property which return a type of Element? (optional Element).

    print("The first state in the array is \(states.first!)")
    print("The last state in the array is \(states.last!)")

We can use indices to iterate over each element at a specific location in an array with a for loop:

    for index in 0 ..< states.count {
        print(states[index])
    }


A very easy way to iterate over all elements in an array makes use of a for loop:

    for state in states {
        print("State: \(state)")
    }

Adding a single element to the end of an array can be accomplished with append:

    states.append("New York")

We can also insert an element at a specific index in the array:

    states.insert("New Jersey", at:1)


This shifts the other elements in the array to “make room” for the new element.
Finally, elements can be removed with the remove method:

    states.remove(at: 2)