# Data Structures the Fun Way  ## Metadata - Author: [[Jeremy Kubica]] - Full Title: Data Structures the Fun Way - Category: #data-structures-and-algorithms ## Highlights - Understanding how data structures function is critical to using them effectively. ([Location 619](https://readwise.io/to_kindle?action=open&asin=B09WJYH4KL&location=619)) - Individual pieces of data are often stored in variables, which are essentially names representing the location (or address) of a piece of data in the computer’s memory. ([Location 713](https://readwise.io/to_kindle?action=open&asin=B09WJYH4KL&location=713)) - Without variables, a programmer can’t track, evaluate, or update the program’s internal state. ([Location 718](https://readwise.io/to_kindle?action=open&asin=B09WJYH4KL&location=718)) - Many programming languages provide the ability to create composite data structures, such as a struct or an object, which gather multiple individual variables into a single group. ([Location 754](https://readwise.io/to_kindle?action=open&asin=B09WJYH4KL&location=754)) - Business cards provide a real-world example of composite data structures. ([Location 766](https://readwise.io/to_kindle?action=open&asin=B09WJYH4KL&location=766)) - In many programming languages, including Java and Python, data composites can take the form of objects, which contain both the data and functions for operating on their own data. ([Location 769](https://readwise.io/to_kindle?action=open&asin=B09WJYH4KL&location=769)) - An array is generally used to store multiple related values. ([Location 781](https://readwise.io/to_kindle?action=open&asin=B09WJYH4KL&location=781)) - Arrays provide a simple mechanism for storing multiple values in adjacent and indexable bins. An array is effectively a row of variables—a contiguous block of equal-sized bins in the computer’s memory, ([Location 785](https://readwise.io/to_kindle?action=open&asin=B09WJYH4KL&location=785)) - The structure of an array allows you to access any value, also known as an element, within the array by specifying its location, or index. ([Location 795](https://readwise.io/to_kindle?action=open&asin=B09WJYH4KL&location=795)) - Most programming languages use zero-indexed arrays, which means the first value of the array resides at index 0, the second at index 1, and so forth, ([Location 801](https://readwise.io/to_kindle?action=open&asin=B09WJYH4KL&location=801)) - The location of the ith item in the array can be computed by: Location(item i) = Location(start of array) + Size of each element × i ([Location 813](https://readwise.io/to_kindle?action=open&asin=B09WJYH4KL&location=813)) - Although we often visualize and discuss arrays as the whole data structure, it is important to remember that each bin behaves like an individual variable. ([Location 834](https://readwise.io/to_kindle?action=open&asin=B09WJYH4KL&location=834)) - Insertion sort is an algorithm to sort the values in an array. ([Location 853](https://readwise.io/to_kindle?action=open&asin=B09WJYH4KL&location=853)) - Insertion sort works by sorting a subset of the array and expanding this sorted range until the entire array is in order. ([Location 855](https://readwise.io/to_kindle?action=open&asin=B09WJYH4KL&location=855)) - Insertion sort isn’t particularly efficient. When inserting elements into the array, we could end up shifting around significant portions of the array. In the worst case, the cost of the algorithm scales proportionally with the square of the number of items—for every item in the list, we shift all the items in front of it. If we double the size of the array, we increase the worst-case cost by a factor of four. ([Location 893](https://readwise.io/to_kindle?action=open&asin=B09WJYH4KL&location=893)) - Strings are ordered lists of characters that can often be thought of as a special kind of arrays. ([Location 901](https://readwise.io/to_kindle?action=open&asin=B09WJYH4KL&location=901)) - The worst-case computational cost of string comparison grows proportionally with the length of the strings. ([Location 931](https://readwise.io/to_kindle?action=open&asin=B09WJYH4KL&location=931)) - Binary search is an algorithm for efficiently searching a sorted list. ([Location 946](https://readwise.io/to_kindle?action=open&asin=B09WJYH4KL&location=946)) - Linear scan searches for a target value by testing each value in our list, one after the other, against the target value, until the target is found or we reach the end of our list. ([Location 972](https://readwise.io/to_kindle?action=open&asin=B09WJYH4KL&location=972)) - Linear scan isn’t fancy or clever. It’s a brute-force test guaranteed to find the item of interest (if the item is in the data) because it checks every possible item until it finds a match or confirms the item is missing. ([Location 991](https://readwise.io/to_kindle?action=open&asin=B09WJYH4KL&location=991)) - Binary search is an algorithm to find a target value v in a sorted list and only works on sorted data. ([Location 1005](https://readwise.io/to_kindle?action=open&asin=B09WJYH4KL&location=1005)) - The key to efficient algorithms is using information or structure within the data. ([Location 1015](https://readwise.io/to_kindle?action=open&asin=B09WJYH4KL&location=1015)) - Binary search tracks the current search space with two bounds: the upper bound IndexHigh marks the highest index of the array that is part of the active search space, and the lower bound IndexLow marks the lowest. ([Location 1022](https://readwise.io/to_kindle?action=open&asin=B09WJYH4KL&location=1022))