Data structures are ways of organizing data used by your code. They provide a way for handling large amounts of data efficiently. They are used to organize information stored in memory. Different structures are used for different types of applications. This week we are talking about arrays.
“Especially with older programming texts that was the way you did things.”
Arrays are a basic data structure that are used to store values and associated keys. You’ll see them across most languages though the names of operations might change or how you implement the arrays. They are related to other data structures such as linked lists.
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.
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. 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.
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
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.
Generally resizing an array requires copying the items to a new array with enough space.
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.
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 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.
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.
Talkies: A new way to chat with kids
“Talkies combines a lovable friend with a built in smartphone for communication.”
This is a cute monster toy that looks like a stuffed animal but has smartphone technology inside. It provides a way for parents to keep in touch with their kids. Parents, grand parents, aunts, or uncles can record a message and send it to the toy. Kids can reply immediately from the toy.
Tricks of the Trade
Use abstractions, but understand the implementation of the layer below your own to understand the performance problems that you might encounter. Abstractions are great time savers, but only if the thing you are abstracting is understood well enough by you that you know what you can ignore and what you cannot.