{"nbformat":4,"nbformat_minor":0,"metadata":{"colab":{"provenance":[],"toc_visible":true,"authorship_tag":"ABX9TyNLoETExfHXRIUoH4tHOp06"},"kernelspec":{"name":"python3","display_name":"Python 3"},"language_info":{"name":"python"}},"cells":[{"cell_type":"markdown","source":["# Data Structures\n","\n","

\n","\n","In addition to what are called \"primitive\" data types in Python (`integer`, `float`, `string`, and `Boolean`), most programming languages also include or support more complex data structures or more complex ways of storing and accessing information. In Python, those one-dimensional (or linear) data structures include `strings`, `lists`, `tuples`, `sets`, and `dictionaries`.\n","\n","\n"," \n"," \n"," \n"," \n"," \n","
NameSyntaxExampleDescription
Stringstr(), \"\"\"Hello world!\"Sequence of characters
Listlist(), [][\"apple\", \"banana\", \"pear\"], [1, 3, 5, 7]Sequence of objects/values
Dictionarydict(), {}{'first_name': 'Knute', 'last_name':'Rockne', 'class':'1918'}Key-value pairs
Setset(), {}{\"apple\", \"banana\", \"pear\"}, {1, 3, 5, 7}Unordered group of unique values
Tupletuple(), ()(\"apple\", \"banana\", \"pear\"), (1, 3, 5, 7)Ordered group of values that can include duplicates
"],"metadata":{"id":"LyBuOuvvzAbd"}},{"cell_type":"markdown","source":["## Lists\n","\n","

\n","\n","\"In computer science, 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...The simplest type of data structure is a linear array, also called one-dimensional array\" ([Wikipedia, \"Array (data structure)](https://en.wikipedia.org/wiki/Array_(data_structure))\")\n","\n","We can think of arrays as one-dimensional, linear data structures made up of a collection of items. As the definitions note, we can access specific elements in the array by using an index or key value.\n","\n","\"In Python, the built-in array data structure is a list\" (Busbee and Braunschweig, \"[Arrays and Lists](https://press.rebus.community/programmingfundamentals/chapter/arrays-and-lists/)\"). Python also includes a few other built-in array-like data structures, including `sets` and `tuples`. We'll come back to these later in this lab. We can also think of string objects, which are a sequence of characters, as a type of one-dimiensional, linear array.\n","\n","These **one-dimensional or linear array structures** have a few key properties that differentiate the structures and shape how we can interact with or manipulate them in a programming environment.\n","\n","Those properties include:\n","- Mutable: Can values in the structure be changed once it has been created or assigned to a variable?\n","- Order: Does the order of values in the structure have meaning/significance, or is order not significant?\n","- Indexing/Slicing: Can values in the structure be accessed using their position or index? Can we isolate values in the structure using their position?\n","- Duplicates: Does the structure allow duplicate values?\n","\n","How these properties show up for Python's built-in data structures:\n","\n","

\n","\n","Each structure has its own specific vocabulary and syntax, but some common operations we can use with these structures:\n","- Getting number of values in the structure (using the `len()` function)\n","- For structures that are mutable, adding, modifying, and removing values\n","- Sorting values in the structure\n","- Testing for membership, if specific value(s) are present in the structure (using the `in` and `not in` operators)\n","- For structures that are ordered or indexed, accessing elements using their position\n","\n","An example that uses a list of strings:"],"metadata":{"id":"6CTXXjvr6sJc"}},{"cell_type":"code","source":["# list of string objects\n","fruits = [\"apple\", \"banana\", \"blueberry\", \"cherry\"]\n","\n","# check data type\n","print(type(fruits))"],"metadata":{"id":"XFlK0bD46wqt"},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":["We can determine the number of elements in the list using the `len()` function.\n"],"metadata":{"id":"fA0n0VoK6xpJ"}},{"cell_type":"code","source":["print(len(fruits))"],"metadata":{"id":"jBiO9s8b6ybw"},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":["Remember Python starts at `0` and counts left-to-right. We can access specific values using their position.\n"],"metadata":{"id":"2vDhClNK66US"}},{"cell_type":"code","source":["# access first value\n","print(fruits[0])\n","\n","# access second value\n","print(fruits[1])\n","\n","# access third value\n","print(fruits[2])"],"metadata":{"id":"cO2jtKed65Yw"},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":["\n","Python lists also support negative indexing- we can use negative index values to count right-to-left.\n","- NOTE: Negative indexing starts counting at `-1`"],"metadata":{"id":"0h6ek0A36-Yp"}},{"cell_type":"code","source":["# access last value\n","print(fruits[-1])\n","\n","# access next to last value\n","print(fruits[-2])"],"metadata":{"id":"mSUMqgbJ6_aP"},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":["## Dictionaries\n","\n","

\n","\n","The other primary type of array we can encounter is an **associative array**, \"an abstract data type that stores a collection of (key, value) pairs, such that each possible key appears at most once in the collection\" ([Wikpedia, Associative Array](https://en.wikipedia.org/wiki/Associative_array))\n","\n","Python stores associate arrays using the **dictionary** data structure. Python dictionaries consist of key-value pairs, where the key is working as an identifier or index.\n","\n","A preliminary example in Python:"],"metadata":{"id":"iFWBFlo77Ajw"}},{"cell_type":"code","source":["# create dictionary\n","english_to_french = {\n"," 'one': 'un',\n"," 'two': 'deux',\n"," 'three': 'trois',\n"," 'four': 'quatre',\n"," 'five': 'cinq'\n","}\n","\n","# check data type\n","print(type(english_to_french))"],"metadata":{"id":"qgZxEtH17DFP"},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":["We can use the index operator (`[]`) and key values to select specific values in the dictionary.\n"],"metadata":{"id":"_lsH9O7q7D7M"}},{"cell_type":"code","source":["# access value for one key\n","print(english_to_french['one'])\n","\n","# access value for five key\n","print(english_to_french['five'])\n","\n","# access value for asdf key\n","print(english_to_french['asdf'])"],"metadata":{"id":"wPf4_0uu7HsU"},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":["The last line will return a `KeyError` because `asdf` is not a key in this dictionary."],"metadata":{"id":"cRto1Fu37JDE"}},{"cell_type":"markdown","source":["## Application\n","\n","Q2: Create your own list of numbers or strings, using the examples in the lab as a starting point. What is the number position for each of the items in your list? How would you return the value of the first item? How would you return the value of the last item?"],"metadata":{"id":"BOP2tzC_z8pg"}},{"cell_type":"markdown","source":["## Additional Resources\n","\n","For more background on arrays and data structures in Python:\n","- [Elements of Computing I \"Data Structures in Python\" lab](https://github.com/kwaldenphd/python-data-structures)"],"metadata":{"id":"RKVypOny0Abb"}}]}