The first data structures we will explore are contiguous data structures. These linear data structures are index-based, where each element is accessed sequentially in a particular order.

Arrays

The array data structure is the most well-known data storage structure and it is built into most programming languages, including Swift. The simplest type is the linear array, also known as a one-dimensional array. In Swift, arrays are a zero-based index, with an ordered, random-access collection of elements of a given type.

For one-dimensional arrays, the index notation allows indication of the elements by simply writing ai, where the index i is known to go from 0 to n:

For example, give the array:

α = (3 5 7 9 13)

Some of the entries are:

α₀ = 3, α₁ = 5, ..., α₄ = 13

Another form of an array is the multidimensional array. A matrix is an example of a multidimensional array that is implemented as a two-dimensional array. The index notation allows indication of the elements by writing aij, where the indexes denote an element in row i and column j:

Given the matrix:

Some of the entries are:

α₀₀ = 2, α₁₁ = 3, ..., α₂₂ = 4

var myIntArray: Array<Int> = [1,3,5,7,9] 

var myIntArray: [Int] = [1,3,5,7,9] 

var myIntArray = [1,3,5,7,9] 

var myIntArray: [Int] = [] 

var my2DArray: [[Int]] = [[1,2], [10,11], [20, 30]] 

1> var myIntArray: [Int] = [1,3,5,7,9]
myIntArray: [Int] = 5 values {
  [0] = 1
  [1] = 3
  [2] = 5
  [3] = 7
  [4] = 9
}
  2> var someNumber = myIntArray[2]
someNumber: Int = 5

1> var myIntArray: [Int] = [1,3,5,7,9]
myIntArray: [Int] = 5 values {
  [0] = 1
  [1] = 3
  [2] = 5
  [3] = 7
  [4] = 9
}
  2> for element in myIntArray {
  3.     print(element)
  4. }

1
3
5
7
9

1> var myIntArray: [Int] = [1,3,5,7,9]
myIntArray: [Int] = 5 values {
  [0] = 1
  [1] = 3
  [2] = 5
  [3] = 7
  [4] = 9
}
2> var someSubset = myIntArray[2...4]
someSubset: ArraySlice<Int> = 3 values {
  [2] = 5
  [3] = 7
  [4] = 9
}

1> var my2DArray: [[Int]] = [[1,2], [10,11], [20, 30]]
my2DArray: [[Int]] = 3 values {
  [0] = 2 values {
    [0] = 1
    [1] = 2
  }
[1] = 2 values {
  [0] = 10
  [1] = 11
}
[2] = 2 values {
  [0] = 20
  [1] = 30
}

}
  2> var element = my2DArray[0][0]
element: Int = 1
3> element = my2DArray[1][1]
4> print(element)
11

1> var myIntArray: [Int] = [1,3,5,7,9]
myIntArray: [Int] = 5 values {
  [0] = 1
  [1] = 3
  [2] = 5
  [3] = 7
  [4] = 9
}
  2> myIntArray.append(10)
  3> print(myIntArray)
[1, 3, 5, 7, 9, 10]

1> var myIntArray: [Int] = [1,3,5,7,9]
myIntArray: [Int] = 5 values {
  [0] = 1
[1] = 3
[2] = 5
[3] = 7
[4] = 9
}
2> myIntArray.insert(4, at: 2)
3> print(myIntArray)
[1, 3, 4, 5, 7, 9]

1> var myIntArray: [Int] = [1,3]
myIntArray: [Int] = 2 values {
  [0] = 1
  [1] = 3
}
  2> myIntArray.removeLast()

$R0: Int = 3
  3> print(myIntArray)
[1]

1> var myIntArray: [Int] = [1,3,5,7,9]
myIntArray: [Int] = 5 values {
  [0] = 1
  [1] = 3
  [2] = 5
  [3] = 7
  [4] = 9
}
  2> myIntArray.remove(at: 3)
$R0: Int = 7
  3> print(myIntArray)
[1, 3, 5, 9]

Linked structures are composed of a data type and bound together by pointers. A pointer represents the address of a location in the memory. Unlike other low-level programming languages such as C, where you have direct access to the pointer memory address, Swift, whenever possible, avoids giving you direct access to pointers. Instead, they are abstracted away from you.

We're going to look at linked lists in this section. A linked list consists of a sequence of nodes that are interconnected via their link field. In their simplest form, the node contains data and a reference (or link) to the next node in the sequence. More complex forms add additional links, so as to allow traversing forwards and backwards in the sequence. Additional nodes can easily be inserted or removed from the linked list.

Linked lists are made up of nodes, which are self-referential classes, where each node contains data and one or more links to the next node in the sequence.

In computer science, when you represent linked lists, arrows are used to depict references to other nodes in the sequence. Depending on whether you're representing a singly or doubly linked list, the number and direction of arrows will vary.

In the following example, nodes S and D have one or more arrows; these represent references to other nodes in the sequence. The S node represents a node in a singly linked list, where the arrow represents a link to the next node in the sequence. The N node represents a null reference and represents the end of a singly linked list. The D node represents a node that is in a doubly linked list, where the left arrow represents a link to the previous node, and the right arrow represents a link to the next node in the sequence.

Singly and doubly linked list data structures

We'll look at another linear data structure, this time implemented as a singly linked list.

class LinkedList<T> {
    var item: T?
    var next: LinkedList<T>?
}

In studying algorithms, we often concern ourselves with ensuring their stingy use of resources. The time and space needed to solve a problem are the two most common resources we consider.

Specifically, we're interested in the asymptotic behavior of functions describing resource use in terms of some measure of problem size. We'll take a closer look at asymptotic behavior later in this chapter. This behavior is often used as a basis for comparison between methods, where we prefer methods whose resource use grows slowly as a function of the problem size. This means we should be able to solve larger problems quicker.

The algorithms we'll discuss in this book apply directly to specific data structures. For most data structures, we'll need to know how to:

Swift has two fundamental types: value types and reference types. Value types are a type whose value is copied when it is assigned to a variable or constant, or when it is passed to a function. Value types have only one owner. Value types include structures and enumerations. All of Swift's basic types are implemented as structures.

Reference types, unlike value types, are not copied on assignment but are shared. Instead of a copy being made when assigning a variable or passing to a function, a reference to the same existing instance is used. Reference types have multiple owners.

The Swift standard library defines many commonly used native types such as int, double, float, string, character, bool, array, dictionary, and set.

It's important to remember though that the preceding types, unlike in other languages, are not primitive types. They are actually named types, defined and implemented in the Swift standard library as structures. We'll discuss named types in the following section.

In Swift, types are also classified as named types and compound types. A named type is a type that can be user-defined and given a particular name when it's defined. Named types include classes, structures, enumerations, and protocols. In addition to user-defined named types, the Swift standard library also includes named types that represent arrays, dictionaries, sets, and optional values. Named types can also have their behavior extended by using an extension declaration.

Compound types are types without a name, In Swift, the language defines two compound types: function types and type types. A compound type can contain both named types, and other compound types. As an example, the following tuple type contains two elements: the first is the named type Int, and the second is another compound type (Float, Float):

(Int, (Float, Float))

Type aliases define an alternative name for existing types. The typealias keyword is similar to typedef in C-based languages. Type aliases are useful when working with existing types that you want to be more contextually appropriate to the domain you are working in. For example, the following associates the identifier TCPPacket with the type UInt16:

typealias TCPPacket = UInt16

Once you define a type alias you can use the alias anywhere you would use the original type:

1> typealias TCPPacket = UInt16
2> var maxTCPPacketSize = TCPPacket.max
maxTCPPacketSize: UInt16 = 65535

Swift provides three types of collections: arrays, dictionaries, and sets. There is one additional type we'll also discuss, even though it's technically not a collection—tuples, which allow for the grouping of multiple values into a compound value. The values that are ordered can be of any type and do not have to be of the same type as each other. We'll look at these collection classes in depth in the next chapter.

In estimating the running time for the preceding sort algorithms, we don't know what the constants c or k are. We know they are a constant of modest size, but other than that, it is not important. From our asymptotic analysis, we know that the log-linear merge sort is faster than the insertion sort, which is quadratic, even though their constants differ. We might not even be able to measure the constants directly because of CPU instruction sets and programming language differences. These estimates are usually only accurate up to a constant factor; for these reasons, we usually ignore constant factors in comparing asymptotic running times.

In computer science, Big-O is the most commonly used asymptotic notation for comparing functions, which also has a convenient notation for hiding the constant factor of an algorithm. Big-O compares functions expressing the upper bound of an algorithm's running time, often called the order of growth. It's a measure of the longest amount of time it could possibly take for an algorithm to complete. A function of a Big-O notation is determined by how it responds to different inputs. Will it be much slower if we have a list of 5,000 items to work with instead of a list of 500 items?

Let's visualize how insertion sort works before we look at the algorithm implementation.

Given the list in Step 1, we assume the first item is in sorted order. In Step 2, we start at the second item and compare it to the previous item, if it is smaller we move the higher item to the right and insert the second item in first position and stop since we're at the beginning. We continue the same pattern in Step 3. In Step 4, it gets a little more interesting. We compare our current item, 34, to the previous one, 63. Since 34 is less than 63, we move 63 to the right. Next, we compare 34 to 56. Since it is also less, we move 56 to the right. Next, we compare 34 to 17, Since 17 is greater than 34, we insert 34 at the current position. We continue this pattern for the remaining steps.

Now let's consider an insertion sort algorithm:

func insertionSort( alist: inout [Int]){ 
    for i in 1..<alist.count { 
        let tmp = alist[i] 
        var j = i - 1 
        while j >= 0 && alist[j] > tmp { 
            alist[j+1] = alist[j] 
            j = j - 1 
        } 
        alist[j+1] = tmp 
    } 
} 

If we call this function with an array of 500, it should be pretty quick. Recall previously where we said the insertion sort represents a quadratic running time where f(x) = c*n²+q. We can express the complexity of this function with the formula, ƒ(x) ϵ O(x²), which means that the function f grows no faster than the quadratic polynomial x², in the asymptotic sense. Often a Big-O notation is abused by making statements such as the complexity of f(x) is O(x²). What we mean is that the worst case f will take O(x²) steps to run. There is a subtle difference between a function being in O(x²) and being O(x²), but it is important. Saying that ƒ(x) ϵ O(x²) does not preclude the worst-case running time of f from being considerably less than O(x²). When we say f(x) is O(x²), we're implying that x² is both an upper and lower bound on the asymptotic worst-case running time.

Let's visualize how merge sort works before we look at the algorithm implementation:

In Chapter 4, Sorting Algorithms, we will take a detailed look at the merge sort algorithm so we'll just take a high-level view of it for now. The first thing we do is begin to divide our array, roughly in half depending on the number of elements. We continue to do this recursively until we have a list size of 1. Then we begin the combine phase by merging the sublists back into a single sorted list.

Now let's consider a merge sort algorithm:

func mergeSort<T:Comparable>(inout list:[T]) { 
    if list.count <= 1 { 
        return 
    } 
     
    func merge(var left:[T], var right:[T]) -> [T] { 
        var result = [T]() 
         
        while left.count != 0 && right.count != 0 { 
            if left[0] <= right[0] { 
                result.append(left.removeAtIndex(0)) 
            } else { 
                result.append(right.removeAtIndex(0)) 
            } 
        } 
         
        while left.count != 0 { 
            result.append(left.removeAtIndex(0)) 
        } 
         
        while right.count != 0 { 
            result.append(right.removeAtIndex(0)) 
        } 
         
        return result 
    } 
     
    var left = [T]() 
    var right = [T]() 
     
    let mid = list.count / 2 
     
    for i in 0..<mid { 
        left.append(list[i]) 
    } 
     
    for i in mid..<list.count { 
        right.append(list[i]) 
    } 
     
    mergeSort(&left) 
    mergeSort(&right) 
     
    list = merge(left, right: right) 
} 

In Table 1.3, we can see with smaller sized inputs it appears at first glance that the insertion sort offers better performance over the merge sort:

Table 1.3 – Small Input Size: 100-1,000 items / seconds

We can see from the following graph that the insertion sort performs quicker than the merge sort:

We can see in Table 1.4, what happens as our input gets very large using the insertion sort and merge sort we used previously:

Table 1.4 – Very Large Input Size: 2,000-60,000 items / seconds

In this graph, the data clearly shows that the insertion sort algorithm does not scale for larger values of n:

Algorithmic complexity is a very important topic in computer science; this was just a basic introduction to the topic to raise your awareness on the subject. Towards the end of this book, we will cover these topics in greater detail in their own chapter.