CSE 212: Programming with Data Structures

Learning Activity: Dynamic Arrays

Overview

In this learning activity you will learn about the first data structure of this course, the Dynamic Array. It is similar to a fixed array, but can grow in size to accommodate any number of items.

Fixed Arrays

A fixed array is a collection of data put in memory with the following properties:

• The fixed array cannot grow or shrink after it is created.
• Each item in the fixed array is the same size
• Each item in the fixed array is contiguous (i.e. right next to each other) in memory

It is very easy for the programming language to access any position in the array. We use the term index when referring to a position in the array. The index starts at 0. In the example array below, we will assume that index 0 begins at memory location 100. We will also assume that the size of each element in the array is 4 bytes. Using this information, we can determine the memory location for each index. Generically, we can say that memory(index) = startingAddress + (index * itemSize)

To create a fixed array in C#, you allocate the array with a size and type, and then add items by index:

var numbers = new int[3];

numbers[0] = 1;
numbers[1] = 2;
numbers[2] = 3;

Another syntax that is a few less characters is to use a collection initializer:

var numbers = new[] { 1, 2, 3 };

Dynamic Arrays

The difference between a dynamic array and a fixed array is that the dynamic array can grow (and also shrink). This means that we can always add another item to a dynamic array. One of the common operations performed on a dynamic array is to append a new item to the end of the list. Consider the dynamic array below.

In the dynamic array, the size of the array is 7 and the capacity is 8. If we append another number to the array, we can use the formula described earlier to get the memory location of the next available index. We will then store the new number into the memory location just calculated.

In this updated array, both the size and the capacity are now 8. If we want to append another number, we cannot just add it to the end. A dynamic array is really just a fixed size array (in this case a fixed array of size of 8) that we will discard in favor of building a bigger fixed array. If we tried to add another one, then we would be overwriting memory that likely belongs to another variable. This dangerous condition is called buffer overflow.

To properly grow the array, we have to complete the following steps:

• Create a new array twice as big as the original array. Usually a dynamic array starts with capacity 0 and then increases in the following pattern: 0, 1, 2, 4, 8, 16, 32, 64, 128, etc.
• Copy all the values from the original smaller array into the new larger array.
• Delete the original smaller array.
• Add the new item to the larger array.

Inserting in the Dynamic Array

If we wanted to insert an item somewhere besides the end of the dynamic array, we would need to be careful to maintain the order of the items in the array. In the array below, if we insert a value at the beginning of the array, all other items will need to move to the next index (i.e. move to the right).

Deleting from the Dynamic Array

If we wanted to delete an item from the array, we would need to move all items after the item removed to the previous index (i.e. move to the left). As a special case, if we wanted to remove the last item in the array, we would not need to move any other items. The typical effect of removing the last item is to just decrease the size variable by 1 while leaving the capacity the same. This means that the data is not really "deleted." If we append a new item, then the previously "deleted" item will be overwritten.

Lists in C#

In C#, a dynamic array is created by using a List object. There are several ways to create lists in C#. Here's the most basic way to create a list of integers and add 1, 2, & 3:

var numbers = new List<int>();

numbers.Add(1);
numbers.Add(2);
numbers.Add(3);

Another syntax that is a little less characters is to use a collection initializer:

var numbers = new List<int> { 1, 2, 3 };

The following table shows the most common operations in a dynamic array and the equivalent C# List code:

Looping Through Lists or Arrays

To access, display, or do something with every item in a list, the foreach loop is used. The following code will display all values in a list one at a time:

foreach(var item in myList)
{
  Console.WriteLine(item);
}

This type of for loop is called an iterator because it will visit all items in the collection without the programmer needing to think about the index. We can change the for loop so that it loops through all the index values for the list instead.

// This is for a list
for (var index = 0; index < myList.Count; ++index)
{
  Console.WriteLine(myList[index]);
}

// This is for an array
for (var index = 0; index < myArray.Length; ++index)
{
  Console.WriteLine(myArray[index]);
}

Lists vs Arrays

Dynamic arrays seem like they are so much more useful, so is there ever a reason to use a fixed array? Of course!

Advantages of Dynamic Arrays

• Expandable

Advantages of Fixed Arrays

• Faster memory allocation if you know how much to store
  • Dynamic arrays need to expand and copy the contents once they experience overflow
• Consumes slightly less memory as there is less metadata in an array

Activity Instructions

Complete each of the following:

1. With a pencil and paper, draw a dynamic array with an initial capacity of 4.
2. Manually insert (by writing the letters in your boxes) the following: A, B, C, D, E. Observe what you need to do when adding the E.
3. Remove the letter B and add it to the end of the dynamic array. Observe the impact of adjusting something early in the list versus later in the list.

Key Terms

capacity

The number of items that can fit in the fixed array or the number of items that can currently fit in the dynamic array. The capacity of a dynamic array can be increased. This should not be confused with the size of the array.

collection

Data that can be put in a data structure including a dynamic array.

condition

In programming, this is a boolean expression that results in True or False. A condition is usually used with an if, while, or list comprehension in Python.

dynamic array

An array that can grow. A dynamic array is a fixed array that is replaced with a new fixed array if more space is needed.

expression

In programming, this is a statement that evaluates to a result. Common expressions include mathematical operators (for example, +, -, *, /) and variables.

index

In an array, the index represents the location of data. The first index in the array is 0. The index also refers to offset in memory from the starting address.

list

In many programming languages, a dynamic array is called a list.

overflow

Occurs when something goes outside of the specified bounds. This occurs with arrays when access occurs outside of the size of the array.

size

The number of items that are currently in a fixed or dynamic array. If the array is empty, then the size is 0. The size cannot exceed the capacity.

Submission

When you have finished all of the learning activities for the week, return to I-Learn and submit the associated quiz there.

Other Links:

• Return to: Week Overview | Course Home