Working with Arrays Flashcards
Collections and Data Structures
Each type of collection uses an underlying data structure to contain its items
One common data structure is the array
For example, Python’s list type uses an array as the container of its items
What is an array?
An array contains a fixed number of items that can be accessed by position (from 0 to the size of the array minus 1)
The type of access is random
The memory for an array is a single block of adjacent cells
RAM is actually a big array of memory cells
Base address plus index
What is random access?
The amount of access time does not vary with the position
Array vs. List
The size of an array is fixed when it is created
Items can be accessed or replaced, but not inserted or removed
The only operations are str, len, the for loop, and the subscript [ ]
Basic Array Operations
Module: from arrays import Array
Constructor: a = Array(size = 10, fillValue = None)
Length: len(a)
Access: a[index]
Replacement: a[index] = newItem
Iteration: for item in a
Note: size is required, fillValue is optional (None by default); Items can be of any type; index must be >= 0 and < len(a)
What are potential complications of arrays?
When arrays are used to implement other collections, such as lists, the arrays are not always full, and sometimes they run out of room
Any other types of operations, such as insertions and removals, require more programmer and computer effort
Physical size
Number of cells in array
Logical size
Number of data values currently stored and used by the program
Physical size vs. Logical size
When created, arrays have a permanent capacity (number of physical cells)
The number of data values (the logical size of an array-based list) may not equal the capacity
Replace, Insert, and Delete
A replacement requires no shifting of data
A deletion requires shifting data to the left, to close a hole
An insertion requires shifting data to the right, to open a hole
Array complexity analysis
Replacement, like access, is O(1)
Insertion requires shifting n - i items to the right, O(n) in time on the average, and O(1) in space
Deletion requires shifting n - i items to the left, O(n) in times on the average, and O(1) in space
Resizing, when it occurs, is O(n) in time and space
Can python arrays be resized?
No
How can we get more or less space?
Create a new array that’s larger or smaller, transfer data from the original array to the new array, and reset the original array variable to the new array
Adding one cell complexity
Memory and running time complexities are O(n)
What is the advantage of doubling the length of an array when more space is needed?
Resizings will not occur very often
