3.4 Vectors

A vector is an indexed ordered sequence container that can grow in size as new items are added or shrink as items are removed. While similar to an array in structure, the vector is an abstract data type that includes a large number of useful operations for accessing and managing the indexed sequence. As you learned earlier in the chapter, the array consists of only three operations: array creation, getting an element, and setting an element. This makes the vector far more useful in the implementation of a wide range of abstract data types.

Some languages refer to a vector as an array list or as in the case of Python, simply as a list. In computer science, the term list is commonly used to refer to any container with a linear ordering. The ordering is such that every element in the container, except the first one, has a unique predecessor and every element, except the last one, has a unique successor. By this definition, an indexed sequence is a list, but a list is not necessarily an indexed sequence since there is no requirement that a list provide access to the elements by position. Python, unfortunately, uses the same name for its built-in mutable sequence type. To avoid confusion, we will use the term list to refer to the data type provided by Python and use the terms general list or list structure when referring to the more general list structure as defined earlier.

The Vector ADT

The definition of the vector abstract data type is provided below. Note that the list of operations, other than the constructor, mirror those of the Python list. Although, only a subset of the operations provided by the Python list are included in our vector ADT definition.

The Vector ADT

A vector is a container that stores a collection of elements in linear order in which the elements can be accessed by position. The container can grow and shrink as items are added and removed. The first element is located at position or index 0, the second at index 1, and so on.

Vector()

Creates a new empty vector that, equivalent to v = [] in Python.
Vector(*initElements)

Creates a vector that contains the initial elements provided as a sequence of arguments, v = Vector(2, 15, 7, 25). This is equivalent to v = [2, 15, 7, 25] in Python.
length()

Returns the number of elements in the list.
contains(element)

Returns a Boolean indicating whether the given element is contained in the vector.
getitem(position)

Returns the element stored at the given position within the indexed sequence. The value of position must be within the valid range, which starts at 0 and ends one less than the length of the vector.
setitem(position, element)

Changes the contents of the element at the given position to the new element. The value of position must be within the valid range, which starts at 0 and ends at the first position after the last element.
append(element)

Appends the given element to the end of the list.
insert(position, element)

Inserts the element at the given position. All elements at and following the given position are moved down to make room for the new item. The value of position must be within the valid range.
pop(position)

Removes and returns the element from the given position. All elements follwoing the given position are moved up one place to close the gap created by removing the element. The value of position must be within the valid range.
popLast()

The same as the pop operation, but the last element in the list is removed and returned. The vector can not be empty.
index(element)

Returns the position of the given element in the vector. The element must be in the vector.
extend(otherVector)

Extends the vector by appending the entire contents of the other vector to this vector.
slice(from, to)

Creates and returns a new vector that contains a subsequence of the elements in the vector between and including those indicated by the given from and to positions. The values of both from and to must be within the valid range.
iterator()

Creates and returns an iterator that can be used to traverse the elements of the vector.

Over the next several sections we examine the implementation of Python's list by way of implementing the vector ADT. This can be very beneficial not only for learning more about abstract data types and their implementations but also to illustrate the major differences between an array and Python's list structure. We explore some of the more common list operations and describe how they are implemented using an array structure.

3.3 Why Study Arrays

Chapter 3. Arrays and Vectors

3.5 Designing an Expandable Container