Array Flashcards
Everything from the wikipedia page
What is an array?
In computer science, an array data structure, or simply an array, is a data structure consisting of a collection of elements (values or variables), each identified by at least one array index or key.
What is the memory address of the first address called?
The memory address of the first element of an array is called first address or foundation address.
How does an array effectively exploit addressing logic of computers?
In most modern computers and many external storage devices, the memory is a one-dimensional array of words, whose indices are their addresses.
How are arrays useful.?
element indices can be computed at run time which allows a single iterative statement to process arbitrarily many elements of an array.
Requirements?
the elements of an array data structure are required to have the same size and should use the same data representation.
History?
The first digital computers used machine-language programming to set up and access array structures for data tables, vector and matrix computations, and for many other purposes.
Applications?
Arrays are used to implement other data structures, such as lists, heaps, hash tables, deques, queues, stacks, strings, and VLists.
How else can Arrays be used?
Arrays can be used to determine partial or complete control flow in programs, as a compact alternative to (otherwise repetitive) multiple IF statements.
Accessing elements?
When data objects are stored in an array, individual objects are selected by an index that is usually a non-negative scalar integer.
What are the 3 ways in which an element can be indexed?
0 (zero-based indexing): The first element of the array is indexed by subscript of 0.[8]
1 (one-based indexing): The first element of the array is indexed by subscript of 1.[9]
n (n-based indexing): The base index of an array can be freely chosen. Usually programming languages allowing n-based indexing also allow negative index values and other scalar data types like enumerations, or characters may be used as an array index
What is the dimension?
The number of indices needed to specify an element is called the dimension, dimensionality, or rank of the array.
How to find the element index of a linear vector in a one-dimensional array?
For a vector with linear addressing, the element with index i is located at the address B + c × i, where B is a fixed base address and c a fixed constant, sometimes called the address increment or stride.
How about multidimensional arrays?
For a multidimensional array, the element with indices i,j would have address B + c · i + d · j, where the coefficients c and d are the row and column address increments, respectively.
What is a dope vector?
The addressing formula is completely defined by the dimension d, the base address B, and the increments c1, c2, …, ck. It is often useful to pack these parameters into a record called the array’s descriptor or stride vector or dope vector.[2][3]
What kinds of operations can be handled by the dope vector?
Many useful array slicing operations (such as selecting a sub-array, swapping indices, or reversing the direction of the indices) can be performed very efficiently by manipulating the dope vector.[2]
Static arrays?
Static arrays have a size that is fixed when they are created and consequently do not allow elements to be inserted or removed.
Dynamic arrays?
by allocating a new array and copying the contents of the old array to it, it is possible to effectively implement a dynamic version of an array
Worst case O(1)?
Both store and select take (deterministic worst case) constant time.
Locality of Reference?
This is roughly a factor of B/k better than the number of cache misses needed to access n elements at random memory locations. As a consequence, sequential iteration over an array is noticeably faster in practice than iteration over many other data structures, a property called locality of reference
Memory-wise?
Memory-wise, arrays are compact data structures with no per-element overhead.
Packed arrays?
It can also happen that elements stored in an array require less memory than the same elements stored in individual variables, because several array elements can be stored in a single word; such arrays are often called packed arrays.
Efficiency?
Indexing = O(1)
Wasted space = 0
What are dynamic arrays?
growable arrays are similar to arrays but add the ability to insert and delete elements; adding and deleting at the end is particularly efficient. However, they reserve linear (Θ(n)) additional storage, whereas arrays do not reserve additional storage.
Efficiency for Dynamic arrays?
Indexing = O(1) Insertion/Deletion at beginning = O(n) Insertion/Deletion at end = O(1) amortized Insertion/Deletion at middle = O(n) Wasted Space = O(n)
What are Associative Arrays?
provide a mechanism for array-like functionality without huge storage overheads when the index values are sparse. For example, an array that contains values only at indexes 1 and 2 billion may benefit from using such a structure.
What is 32-bit unsigned integer?
2,147,483,647…the largest integer from 2**32
What is the item size for 32bits?
4 bytes, so an array holding n items has a total size of 4 * n bytes.
How is the memory address of the first index of an array assigned?
Arbitrarily…
How are preceding memory address of indices computed?
Start with the memory address of the first index i.e. 0xBA03 and add the number of bytes it will hold multiplied by the index it will occupy: 0xB3A0 + 4 * 3 = 0xB3A3
How do arrays work in higher level languages?
To store heterogeneously sized items in an array in C, pointers to those items, instead of the items themselves, would have to be explicitly stored.
Why are arrays among the fastest data structures?
among the fastest data structures since the index lookup process is simply an integer multiplication operation followed by an integer addition operation
What is a jagged array?
This can be avoided by using a one-dimensional array which stores references to other one-dimensional arrays of heterogeneous length.
What are the types of ways to manipulate data?
Adding Searching Sorting Deleting Rearranging Traversing
