Arrays

07:18 Indexes

Arrays are a collection of values with an index or key for each. Data is stored sequentially in memory so that the value can be found quickly from the index.

Indexes are generally positive integers. The index generally starts at 0 and goes to one less than the total number of values in the array n – 1. This is called zero-based indexing. One-based indexing starts with the first value indexed as 1. N-based indexing allows for the base or first index/key to be chosen. Some languages even allow for negative indexes.

“Talking with a Javascript developer when he says array he’s really meaning a linked-list”

The foundation address is the memory address at index of 0, or the first item. Can be one based in some languages such as classic visual basic or some collections in delphi. They are typically allocated ahead of time in anticipation of use, rather than as-needed because allocation is expensive.

16:30 One Dimensional Arrays

“A string is a character array”

These are also known as a linear array. Values can be found by a single subscript array[0]. Your start index is the start of the records. Usually there is a chunk of memory reserved at the beginning for the length.

18:10 Multi-Dimensional Arrays

“A two dimensional array is like a cartesian plane”

Multi-dimensional arrays are similar to matrixes in math. Simplest is a two-dimensional array where the first subscript is the row and the second is the column. Can go as high as your language will allow.

23:55 Sparse Arrays

“In a sparse array not all the books are the same size on the bookshelf.”

Multidimensional array is an array of arrays, effectively. In sparse arrays though, the arrays at each position may not all be of the same size.

28:50 Iteration

Iteration is a direct jump to an index => start of array + (record size * index). Zero based in one dimension of the array. You have to have additional for-loops for further dimensions. They can also return an iterator, which knows where the start position is, how long the array is, and how to get the next item. This tends to be the object type that is used in things like foreach loops.

“So obviously if you have multi-dimensional arrays and you’re iterating you have nested loops.”

34:15 Array Operations

Remove

All items after the current must be moved back, or a null object pattern must be used on the item to be deleted. In order to be dynamic this is very expensive computationally.

Resize

Generally resizing an array requires copying the items to a new array with enough space.

Add Items

Adding an item often requires a resize to accommodate the array size. The new item will need to go in the last available space, not necessarily at the end of the array.

Copy

Copying an array requires a new pointer for a starting location and memory allocated to hold the whole thing. It then must iterate through the array and copy each of the items to the new location.

Slice

Slice creates a subarray from the original parent array. It returns a range of items withing the parent array. The subarray is usually a fixed number of items from a starting point.

Concatenate

Concatenation is the combining of two arrays into one. This usually requires allocating space equal to the sum of the sizes of the first two arrays and then copying them.