Fundamental data structures

As we discussed previously, you need to have a firm understanding of the strengths and weaknesses of the different data structures. In this section, we'll provide an overview of some of the main data structures that are the building blocks for more advanced structures that we'll cover in this book.

There are two fundamental types of data structures, which are classified based on arrays and pointers, respectively as:

• Contiguous data structures, as their name imply, it means storing data in contiguous or adjoining sectors of memory. These are a few examples: arrays, heaps, matrices, and hash tables.
• Linked data structures are composed of distinct sectors of memory that are bound together by pointers. Examples include lists, trees, and graphs.

You can even combine these two types together to create advanced data structures.

Contiguous data structures

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

Declaring an array

There are three forms of syntax in Swift for declaring an array: the full method that uses the Array<Type> form, the shorthand method that uses the square bracket [Type] form, and type inference. The first two are similar to how you would declare variables and constants. For the remainder of this book, we'll use the shorthand syntax.

To declare an array using the full method, use the following code:

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

To declare an array using the shorthand array syntax, use the following code:

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

To declare an array using the type inference syntax, use the following code:

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

Tip

Type inference is a feature that allows the compiler to determine the type at compile time based on the value you provide. Type inference will save you some typing if you declare a variable with an initial type.

If you do not want to define any values at the time of declaration, use the following code:

var myIntArray: [Int] = [] 

To declare a multidimensional array use nesting pairs of square brackets. The name of the base type of the element is contained in the innermost pair of square brackets:

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

You can create beyond two dimensions by continuing to nest the type in square brackets. We'll leave that as an exercise for you to explore.

Retrieving elements

There are multiple ways to retrieve values from an array. If you know the elements index, you can address it directly. Sometimes you may want to loop through, or iterate through the collection of elements in an array. We'll use the for...in syntax for that. There are other times when you may want to work with a subsequence of elements in an array; in this case we'll pass a range instead of an index to get the subsequence.

Directly retrieve an element using its index:

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

Iterating through the elements in an array:

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

Tip

Notice in the preceding examples that when we typed the for loop, after we hit Enter, on the new line instead of a > symbol we have a . and our text is indented. This is the REPL telling you that this code will only be evaluated inside of this code block.

Retrieving a subsequence of an array:

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
}

Directly retrieve an element from a two-dimensional array using its index:

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

Adding elements

You can add elements to an array using several different methods, depending on whether you want to add an element to the end of an array or insert an element anywhere between the beginning and the end of the array.

Adding an element to the end of an existing array:

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]

Inserting an element at a specific index in an existing array:

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]

Removing elements

Similarly, you can remove elements from an array using several different methods, depending on whether you want to remove an element at the end of an array or remove an element anywhere between the beginning and end of the array.

Removing an element at the end of an existing array:

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

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

To remove an element at a specific index in an existing array:

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]

Arrays are used to implement many other data structures, such as stacks, queues, heaps, hash tables, and strings, just to name a few.

Linked data structures

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.

Singly linked list

The linked list data structure is comprised of the four properties we defined previously, as shown in the following declaration:

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

We won't get into the full implementation of this class since we will cover a complete implementation in Chapter 3, Standing on the Shoulders of Giants.