03 Prove : Homework - Data Structures
Dynamic Arrays
Outcomes
At the end of this study, successful students will be able to:
Articulate the strengths and weaknesses of Dynamic Arrays.
Use Dynamic Arrays in Python to solve problems.
Preparation Material
Please read the following:
Please be aware that lists in Python, vectors in C++, ArrayLists in Java and Lists in C# are all dynamic arrays, so you will often see these terms floating around as well.
Supplementary Discussion
On of the biggest benefits of traditional arrays (such as those in C++) is that you can directly access an element by its index, such as words[17]. The place in memory to find can be calculated, so you can jump right to it, and not have to iterate through the preceding items to find it. A major downside to a traditional arrays is that once defined, their size cannot be changed. It might seem simple to just say "use the next spot in memory," but that memory may be used for something else.
Dynamic arrays add the ability to resize the array. To accomplish this, when an attempt is made to add an item to an array that is at capacity, a new, larger array is allocated, then every item is copied over from the original array. Finally, the original array is deleted. This process takes O(n) time (which is bad) because it has to copy over every element in the list.
To avoid this expensive operation every time something is added to the list, when we do resize the list, we make it larger than is currently needed, so that the next addition doesn't require this work. When choosing a new size for the array, we can double the size (or something similar, as long as it has exponential growth), so that the times when this is necessary occur less and less frequently as it grows. Because of this exponential back-off, even though in some cases the cost of adding to the list is O(n), the effective amortized cost for addition is only O(1). See the reading material for a more detailed explanation of this calculation.
In addition to the auto-resizing capability, Dynamic Arrays maintain other properties of traditional Arrays:
O(1) Data access by index - You can jump right to the spot you want, based on its index.
O(n) Insertion to the beginning of the list - Everything in the list most be shuffled down to make room for the new item.
O(n) Removal from the beginning of the list - Everything must be shuffled up to fill the empty spot.
O(1) (amortized) Insertion at the end of the list - See discussion above.
O(1) Remove at the end of the list - Nothing needs to be shuffled.
Using Dynamic Arrays in Python
As mentioned, in Pythons, the built-in list data structure is actually dynamic array! This means that using them in Python is very natural and easy.
Lists can be created with either the list() or [] syntax:
cars = []
trucks = list()
Items can be added to the list via the .append() method (and also the .insert() method), which takes care of all of the resizing work automatically for us!
cars = []
cars.append("Ford")
cars.append("Mazda")
cars.append("Dodge")
# Add one to the beginning, this is O(n) because everything has to be
# shuffled down to make room.
cars.insert(0, "Toyota")
Items in a list can be access by their index:
print(cars[2])
A list can be iterated using either the built-in for loop, or via the index.
for car in cars:
print(car)
# or, this more cumbersome way (don't do this unless you have a specific reason)
for i in range(len(cars)):
print(car[i])
Homework Assignment
Make a list for odd numbers and one for even numbers. Ask the user for numbers and put them in the appropriate list. When they are done, the user can type 0, then the program displays all the even numbers followed by all the odd numbers.
Instructions
Use the following steps to guide your development.
Create two different lists, one for odd numbers and one for even numbers.
Create a loop that prompts the user for a number (0 to quit).
After each number is entered, put it in the correct list.
After a 0 is entered, loop through each number in the even list and display it, then loop through each number in the odd list and display it.
Test your program with different amounts of even and odd numbers, including cases where you don't include any of one type or the other.
Sample output
Enter a number (0 to quit): 6
Enter a number (0 to quit): 15
Enter a number (0 to quit): 8
Enter a number (0 to quit): 82
Enter a number (0 to quit): 3
Enter a number (0 to quit): 124
Enter a number (0 to quit): 0
Even numbers:
6
8
82
124
Odd numbers:
15
3
Testing your program
To help keep your focus squarely on the data structure involved, and not on matching a particular testBed output, an automated grading script is not provided. Instead, test your own code, ensuring that everything works as you would expect. Don't forget to test boundary conditions such as not entering any numbers, or entering all of one type and ensure that the program behaves as expected.
Submission
When you have a good understanding of this data structure and have completed the programming project, take the accompanying I-Learn Quiz. It has questions about how the data structure works, and also, has places for your to report on the parts of the programming assignment that you completed.