Lecture Preview: Vector and LinkedList

(Suggested book reading: Programming Abstractions in C++, section 5.1 - 5.2)

In this lecture, we move from our introduction of C++ into the first main unit of the course, which is Abstract Data Types (ADTs). ADTs are containers for data. When you have many, many pieces of data to keep track of, you don't want to make a named variable for each. The first ADT containers we'll look at are Vector, LinkedList, and Grid. We discussed Grid already in the previous lecture.

A Vector is a one-dimensional list of items, each of which is associated with a 0-based integer index. This is essentially the same thing as an ArrayList in Java. Both serve the same purpose: To provide a collection with similar structure to an array, but that can dynamically resize itself to fit its contents, as well as providing many other useful operations.

stack

Here is a short piece of code that uses a Vector: 

Vector<int> vec;
for (int i = 1; i <= 5; i++) {
    vec.add(2 * i);
}
cout << vec << endl;      // {2, 4, 6, 8, 10}

A LinkedList is similar to a Vector and provides the same set of methods, but it is implement using a different internal structure. This means that some of its operations are more or less efficient than the same operations on a Vector; each is useful in different situations.

The idea of different collections that provide the same operations is related to the notion of an abstract data type (ADT). An ADT is a specification of a collection of data and the operations that can be performed on it. An ADT describes what the collection can do, not how it does it. Vectors and linked lists both represent implementations of the same ADT, which we might choose to call "list".

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.