Lecture Preview: Arrays and ArrayList

(Suggested book reading: Programming Abstractions in C++, 11.2 - 11.3, 12.1, 12.3, 14.1, 14.4)

We have used several collections so far from the Stanford libraries, such as Vector, Stack, Queue, Set, Map, and so on. Today we will explore how collection classes are implemented. We will implement a simple version of Vector, which we will call ArrayList.

Inside a Vector is an array storing the elements you have added. Typically the array is larger than the data added so far, so that it has some extra slots in which to put new elements later. We call this an unfilled array.

If you execute the following code: 

Vector<int> v;
v.add(42);
v.add(-5);
v.add(17);

The state inside the vector looks like this:

index 0 1 2 3 4 5 6 7 8 9
value 42 -5 17 0 0 0 0 0 0 0
size 3 capacity 10

To write our own implementation of a vector, we must learn about how to use arrays in C++. C++ arrays are a bit cumbersome to use and require unusual syntax, which is why we have avoided them thus far. Here is a brief example of constructing an array and storing data in some of its elements: 

int* a = new int[10];
a[0] = 42;
a[1] = 17;
a[9] = 90210;

The unusual use of a * character above is related to how C++ manages memory using a feature called pointers. We will learn about this feature in detail this week.

This document and its content are copyright © Marty Stepp, 2018. All rights reserved. Any redistribution, reproduction, transmission, or storage of part or all of the contents in any form is prohibited without the authors' expressed written permission.