file-text2 file-play home

Intro to Data Structures

“Data structures” tend to conjure intimidation, but they are very easy to begin to understand. Understanding data structures helps us to know when we are/aren’t using the right tool for our task.

Array

contiguous chunk of indexable memory

// allocating memory for an array of 8 elements in C
int * array = malloc(8 * sizeof(int));

The guarantee that elements will reside adjacently allows us to make assumptions about arrays

  1. indexing a particular position will be very fast
  2. iterating over the array in order will be very fast since computers fetch memory in chunks at a time

List

an ordered collection

ArrayList

an ordered collection backed by a contiguous chunk of indexable memory

LinkedList

an ordered collection containing exactly 1 or 0 values and a reference to exactly 1 or 0 other linked lists

Hash function

a function used to map an object to a set of possible keys, typically ints

The resulting int is called a hashcode or hash value.

HashMap

2-dimensional collection of keys and values, where each value is mapped to its corresponding and unique key based on the key’s hashcode

Since HashMaps are array-based, they are as fast as an ArrayList for lookup and addition. Since they do not guarantee consecutive elements, they have fast removal, unlike an ArrayList

HashMaps are not optimized for value-based operations. If you find yourself operating on values in a HashMap, consider swapping your key/value association or using an alternative data structure.

Set

an unordered collection of unique elements

HashSet

an unordered collection of elements that uses the elements hashcode to guarantee fast lookup and addition

Sets are great for collecting unique elements then checking membership. More robust sets also provide interfaces for various set operations.

Tree

a one-dimensional collection, which is either empty, or a node containing one value and references to two branches, each of which are trees

Binary Search Tree

a tree, whose value is greater than the value of its left branch and less than the value of its right branch, each of with are binary search trees

A Recursive Board

either empty or a node containing an index, marker, and reference to its previous state, which is also a board

Mar 23, 2016