ENGR110: Containers and Data Structures

Review: Environment, Shadow, Scope

  • Environment: Memory storing variables and their values (including functions).

  • Scope: Program part where a variable is valid and usable.

  • Shadowing: When two variables have the same name; local variables hide global ones with the same name. Changes to local variables don't affect globals. Local variables are removed when their scope ends.

Basic Data Types

  • Integer (int\text{int}): Whole numbers.

  • Float (float\text{float}): Decimal numbers.

  • String (str\text{str}): Text, enclosed in quotes.

  • Boolean (bool\text{bool}): True or False.

  • These are considered "simple" types.

Types and Relationships

  • A type includes syntax for representation, functions/relations, and typecasting.

  • Relationships connect separate parts into a meaningful whole (e.g., book components, phone number parts).

Container Types

  • A container groups values as a single unit; values are "members."

  • Allow representing data relationships.

  • Support operations: Add, remove, modify members.

  • Can hold basic data types or other containers (e.g., lists of lists).

Main Python Container Types

  • List ([][]): Ordered, mutable sequence of items (e.g., my_list = [1, 2, 3]).

  • Tuple (()()): Ordered, immutable sequence of items (e.g., my_tuple = (1, 2, 3)). Immutability depends on its members.

  • Dictionary ({}): Key-value pairs. Keys must be unique and immutable (e.g., strings, numbers, immutable tuples); values can be any type and are mutable (e.g., my_dict = {"id": 123, "name": "Ahmad"}).

Why Containers are Useful

  • Store multiple values together.

  • Provide built-in operations (add, remove, modify, search).

  • Support looping.

  • Organize information (data structures).

  • Can nest (containers within containers).

Sequences

  • An ordered collection of items, each mapped to a position (index).

  • Python uses zero-based indexing (first item at position 00).

  • Lists and Tuples are sequences.

  • Example: numbers = [10, 20, 30], numbers[0] is 1010, numbers[2] is 3030.

  • Behind the scenes: stored as position-value pairs (e.g., (0,"car")),(1,"apple")).</p></li></ul><h4id="101d07b7−d387−481a−9c0e−db545a97b988"data−toc−id="101d07b7−d387−481a−9c0e−db545a97b988"collapsed="false"seolevelmigrated="true">List,Tuplevs.DictionaryDistinctions</h4><ul><li><p>ListsandTuplesstoreordered,non−uniquemembers.</p></li><li><p>Dictionariesuse<code>key:value</code>pairs;keysmustbeimmutable.</p></li></ul><h4id="1199b431−2e68−4e11−a170−96c80f11ba48"data−toc−id="1199b431−2e68−4e11−a170−96c80f11ba48"collapsed="false"seolevelmigrated="true">Mutability</h4><ul><li><p><strong>Immutable</strong>:Objectcannotbechangedaftercreation(e.g.,<code>int</code>,<code>float</code>,<code>bool</code>,<code>str</code>,<code>tuple</code>∗−ifitsmembersareimmutable).Changinganimmutableobjectcreatesanewobjectinmemory(addresschanges).</p></li><li><p><strong>Mutable</strong>:Objectcanbechangedaftercreation(e.g.,<code>list</code>,<code>set</code>,<code>dict</code>).Changeshappeninplace(addressremainsunchanged).</p></li><li><p>The<code>id()</code>functionreturnsthememoryaddressofanobject,demonstratingmutability/immutability.</p></li></ul><h4id="1e39b8e7−94f1−4a9a−936b−4f41f147fae5"data−toc−id="1e39b8e7−94f1−4a9a−936b−4f41f147fae5"collapsed="false"seolevelmigrated="true">ContainerElementsandSyntax</h4><ul><li><p>Listsandtuplescanhold:integers,floats,booleans,strings,lists,tuples,dictionaries.</p></li><li><p>Dictionarykeys(x)mustbeimmutable;values(y)canbeanytype.</p></li><li><p>Symbols:<code>[]</code>forlist,<code>()</code>fortuple,<code></code>fordictionary.</p></li><li><p>Elementsareseparatedbycommas.</p></li><li><p>Containerscanbeempty.</p></li><li><p>Indexingstartsat(0, "car")), (1, "apple")).</p></li></ul><h4 id="101d07b7-d387-481a-9c0e-db545a97b988" data-toc-id="101d07b7-d387-481a-9c0e-db545a97b988" collapsed="false" seolevelmigrated="true">List, Tuple vs. Dictionary Distinctions</h4><ul><li><p>Lists and Tuples store ordered, non-unique members.</p></li><li><p>Dictionaries use <code>key: value</code> pairs; keys must be immutable.</p></li></ul><h4 id="1199b431-2e68-4e11-a170-96c80f11ba48" data-toc-id="1199b431-2e68-4e11-a170-96c80f11ba48" collapsed="false" seolevelmigrated="true">Mutability</h4><ul><li><p><strong>Immutable</strong>: Object cannot be changed after creation (e.g., <code>int</code>, <code>float</code>, <code>bool</code>, <code>str</code>, <code>tuple</code>* - if its members are immutable). Changing an immutable object creates a new object in memory (address changes).</p></li><li><p><strong>Mutable</strong>: Object can be changed after creation (e.g., <code>list</code>, <code>set</code>, <code>dict</code>). Changes happen in place (address remains unchanged).</p></li><li><p>The <code>id()</code> function returns the memory address of an object, demonstrating mutability/immutability.</p></li></ul><h4 id="1e39b8e7-94f1-4a9a-936b-4f41f147fae5" data-toc-id="1e39b8e7-94f1-4a9a-936b-4f41f147fae5" collapsed="false" seolevelmigrated="true">Container Elements and Syntax</h4><ul><li><p>Lists and tuples can hold: integers, floats, booleans, strings, lists, tuples, dictionaries.</p></li><li><p>Dictionary keys (x) must be immutable; values (y) can be any type.</p></li><li><p>Symbols: <code>[]</code> for list, <code>()</code> for tuple, <code>{}</code> for dictionary.</p></li><li><p>Elements are separated by commas.</p></li><li><p>Containers can be empty.</p></li><li><p>Indexing starts at0.</p></li></ul><h4id="99bde67a−b341−4cb1−9baa−2e0019079293"data−toc−id="99bde67a−b341−4cb1−9baa−2e0019079293"collapsed="false"seolevelmigrated="true">ChoosingaContainer</h4><ul><li><p><strong>List</strong>:Mostflexible,easytouse,forgeneralcollections.</p></li><li><p><strong>Tuple</strong>:Immutable,goodforfixedcollectionsorwhenimmutabilityisrequired(e.g.,dictionarykeys).</p></li><li><p><strong>Dictionary</strong>:Key−valuepairs,forfastlookupsbykey.</p></li></ul><h4id="b4525949−2e65−4eb7−b02f−f942ed36f38d"data−toc−id="b4525949−2e65−4eb7−b02f−f942ed36f38d"collapsed="false"seolevelmigrated="true">ContainerOperations</h4><ul><li><p><code>len()</code>:Returnsthenumberofelementsinacontainerorcharactersinastring(non−negativeinteger).</p></li><li><p><strong>Concatenation(</strong><code>+</code><strong>)</strong>:Joinstwocontainersofthesametype(e.g.,<code>[1,2]+[3]</code>resultsin<code>[1,2,3]</code>).Fornon−tuplesingle−elementexpressions(e.g.,<code>(1)+(2)</code>),itperformsarithmeticaddition.</p></li><li><p><strong>Repetition(</strong><code>∗</code><strong>)</strong>:Repeatsacontainerorstringbyanintegerfactor(e.g.,<code>[1,2]∗2</code>resultsin<code>[1,2,1,2]</code>).</p></li><li><p><strong>Subscripting(</strong><code>[]</code><strong>)</strong>:Accesseselementsbyindexforsequences(lists,tuples,strings)orbykeyfordictionaries.</p></li></ul><h4id="f7efb2c2−e055−4535−92d3−65c8209e252f"data−toc−id="f7efb2c2−e055−4535−92d3−65c8209e252f"collapsed="false"seolevelmigrated="true">EmptyContainersandBooleans</h4><ul><li><p>Emptycontainers(.</p></li></ul><h4 id="99bde67a-b341-4cb1-9baa-2e0019079293" data-toc-id="99bde67a-b341-4cb1-9baa-2e0019079293" collapsed="false" seolevelmigrated="true">Choosing a Container</h4><ul><li><p><strong>List</strong>: Most flexible, easy to use, for general collections.</p></li><li><p><strong>Tuple</strong>: Immutable, good for fixed collections or when immutability is required (e.g., dictionary keys).</p></li><li><p><strong>Dictionary</strong>: Key-value pairs, for fast lookups by key.</p></li></ul><h4 id="b4525949-2e65-4eb7-b02f-f942ed36f38d" data-toc-id="b4525949-2e65-4eb7-b02f-f942ed36f38d" collapsed="false" seolevelmigrated="true">Container Operations</h4><ul><li><p><code>len()</code>: Returns the number of elements in a container or characters in a string (non-negative integer).</p></li><li><p><strong>Concatenation (</strong><code>+</code><strong>)</strong>: Joins two containers of the same type (e.g., <code>[1, 2] + [3]</code> results in <code>[1, 2, 3]</code>). For non-tuple single-element expressions (e.g., <code>(1) + (2)</code>), it performs arithmetic addition.</p></li><li><p><strong>Repetition (</strong><code>*</code><strong>)</strong>: Repeats a container or string by an integer factor (e.g., <code>[1, 2] * 2</code> results in <code>[1, 2, 1, 2]</code>).</p></li><li><p><strong>Subscripting (</strong><code>[]</code><strong>)</strong>: Accesses elements by index for sequences (lists, tuples, strings) or by key for dictionaries.</p></li></ul><h4 id="f7efb2c2-e055-4535-92d3-65c8209e252f" data-toc-id="f7efb2c2-e055-4535-92d3-65c8209e252f" collapsed="false" seolevelmigrated="true">Empty Containers and Booleans</h4><ul><li><p>Empty containers ([], (), {})evaluateto<code>False</code>inabooleancontext.</p></li></ul><h4id="fb781f64−4a28−4086−9ab1−61cad5e34744"data−toc−id="fb781f64−4a28−4086−9ab1−61cad5e34744"collapsed="false"seolevelmigrated="true">AccessingElementswithSubscripts</h4><ul><li><p>Uses<code>[n]</code>(postfixfunction)toreturntheelementatposition<code>n</code>(zero−basedindex).</p></li><li><p><code>IndexError</code>occursifanindexisoutofrange(e.g.,accessingbeyond<code>len(container)−1</code>).</p></li><li><p>Appliestolists,tuples,andstrings.Example:<code>xlist=[45,′H′,[],6]</code>,<code>xlist[1]</code>is<code>′H′</code>.</p></li><li><p><strong>NestedSubscripting</strong>:Repeatedlyapply<code>[]</code>toaccesselementsinnestedcontainers(e.g.,<code>x[2][2][1]</code>).</p></li></ul><h4id="03cc9119−d679−434b−96f4−f304f0406c3a"data−toc−id="03cc9119−d679−434b−96f4−f304f0406c3a"collapsed="false"seolevelmigrated="true">HashableObjects</h4><ul><li><p>Anobjectis<strong>hashable</strong>ifithasahashvaluethatneverchangesduringitslifetime.</p></li><li><p>Hashableobjectscanbeusedas<strong>keysindictionaries</strong>or<strong>elementsinsets</strong>.</p></li><li><p><strong>Immutabletypes</strong>(numbers,strings,tuplesofimmutableitems)aregenerallyhashable.</p></li><li><p><strong>Mutabletypes</strong>(lists,dictionaries,sets)are<strong>nothashable</strong>becausetheircontentcanchange,whichwouldbreakhash−basedlookups.</p></li></ul><h4id="a7660c6a−8e3e−4c0d−8c2d−b7f1f09096bb"data−toc−id="a7660c6a−8e3e−4c0d−8c2d−b7f1f09096bb"collapsed="false"seolevelmigrated="true">Listsvs.Tuples(Revisited)</h4><ul><li><p><strong>Lists</strong>:Mutable,nothashable.</p></li><li><p><strong>Tuples</strong>:Immutable,canbehashable<em>ifalltheirelementsarethemselvesimmutable</em>.</p><ul><li><p>Atuplecontainingamutablemember(e.g.,alist)isconsidered"mutable"inbehaviorevenifthetuplestructureitselfcannotbechanged,thusmakingitnothashable.</p></li></ul></li></ul><h4id="bf6a3199−335c−4061−9f88−1fded26d1350"data−toc−id="bf6a3199−335c−4061−9f88−1fded26d1350"collapsed="false"seolevelmigrated="true">DictionarySubscripting</h4><ul><li><p>Usesthe<strong>key</strong>toaccessitscorrespondingvalue(e.g.,<code>mydict["id"]</code>).</p></li><li><p>Dictionariesdonothaveaninherentorder(nofirst,secondelementbyindex).</p></li></ul><h4id="b0127cff−3b7d−4da4−9e9d−94ab0e2b347d"data−toc−id="b0127cff−3b7d−4da4−9e9d−94ab0e2b347d"collapsed="false"seolevelmigrated="true">TypicalListOperations</h4><ul><li><p><code>+</code>(concatenation),<code>∗</code>(repetition),<code>[]</code>(subscripting).</p></li><li><p>Typeerrorsoccurifoperationscombineincompatibletypes(e.g.,<code>[1]+2</code>).</p></li></ul><h4id="82a0cf2c−8779−417a−849b−aa2f31cc28a2"data−toc−id="82a0cf2c−8779−417a−849b−aa2f31cc28a2"collapsed="false"seolevelmigrated="true">BuildingDictionaries:Merging</h4><ul><li><p><code>update()</code><strong>method</strong>:Mergesonedictionaryintoanother(e.g.,<code>menua.update(menub)</code>).</p></li><li><p><strong>Unionoperator(</strong><code>∣</code><strong>)</strong>:Mergestwodictionaries(Python3.9+)</p></li><li><p><strong>Unpacking(</strong><code>∗∗</code><strong>)</strong>:Mergesdictionariesintoanewone(e.g.,<code>combinedmenu=∗∗d1,∗∗d2</code>).</p></li></ul><h4id="131e567a−dea5−4c29−bf5f−4683d9fceda9"data−toc−id="131e567a−dea5−4c29−bf5f−4683d9fceda9"collapsed="false"seolevelmigrated="true">AssignmentwithContainersandStrings</h4><ul><li><p><strong>Multipleassignment</strong>:Pythonallowsassigningmultiplevariablesfromasequenceorstringinoneline(e.g.,<code>x,y,z=[1,2,3]</code>or<code>x,y,z="123"</code>).Evaluationisright−to−left.</p></li><li><p><code>∗</code><strong>forexpansion</strong>:Inmultipleassignment,<code>∗</code>canunpackaniterable(list,tuple,string)intomultiplevariables(e.g.,<code>a,b,c=1,∗(2,3)</code>).A<code>ValueError</code>occursiftherearetoomany/fewvaluestounpack.</p></li></ul><h4id="283a0a88−5f60−461e−bb6a−9b163be1070d"data−toc−id="283a0a88−5f60−461e−bb6a−9b163be1070d"collapsed="false"seolevelmigrated="true">TupleasPython′sDefaultContainer</h4><ul><li><p>Whenafunctionreturnsmultipleitems(separatedbycommas),Pythonautomaticallypackagesthemintoatuple(e.g.,<code>returnx+1,x−1</code>returns<code>(x+1,x−1)</code>).</p></li></ul><h4id="89564bb0−c9e3−42c6−9b3b−cc452ece0c8f"data−toc−id="89564bb0−c9e3−42c6−9b3b−cc452ece0c8f"collapsed="false"seolevelmigrated="true">QuadraticEquationExample</h4><ul><li><p>Demonstratesunpackingatupleofcoefficients) evaluate to <code>False</code> in a boolean context.</p></li></ul><h4 id="fb781f64-4a28-4086-9ab1-61cad5e34744" data-toc-id="fb781f64-4a28-4086-9ab1-61cad5e34744" collapsed="false" seolevelmigrated="true">Accessing Elements with Subscripts</h4><ul><li><p>Uses <code>[n]</code> (postfix function) to return the element at position <code>n</code> (zero-based index).</p></li><li><p><code>IndexError</code> occurs if an index is out of range (e.g., accessing beyond <code>len(container) - 1</code>).</p></li><li><p>Applies to lists, tuples, and strings. Example: <code>xlist = [45, 'H', [], 6]</code>, <code>xlist[1]</code> is <code>'H'</code>.</p></li><li><p><strong>Nested Subscripting</strong>: Repeatedly apply <code>[]</code> to access elements in nested containers (e.g., <code>x[2][2][1]</code>).</p></li></ul><h4 id="03cc9119-d679-434b-96f4-f304f0406c3a" data-toc-id="03cc9119-d679-434b-96f4-f304f0406c3a" collapsed="false" seolevelmigrated="true">Hashable Objects</h4><ul><li><p>An object is <strong>hashable</strong> if it has a hash value that never changes during its lifetime.</p></li><li><p>Hashable objects can be used as <strong>keys in dictionaries</strong> or <strong>elements in sets</strong>.</p></li><li><p><strong>Immutable types</strong> (numbers, strings, tuples of immutable items) are generally hashable.</p></li><li><p><strong>Mutable types</strong> (lists, dictionaries, sets) are <strong>not hashable</strong> because their content can change, which would break hash-based lookups.</p></li></ul><h4 id="a7660c6a-8e3e-4c0d-8c2d-b7f1f09096bb" data-toc-id="a7660c6a-8e3e-4c0d-8c2d-b7f1f09096bb" collapsed="false" seolevelmigrated="true">Lists vs. Tuples (Revisited)</h4><ul><li><p><strong>Lists</strong>: Mutable, not hashable.</p></li><li><p><strong>Tuples</strong>: Immutable, can be hashable <em>if all their elements are themselves immutable</em>.</p><ul><li><p>A tuple containing a mutable member (e.g., a list) is considered "mutable" in behavior even if the tuple structure itself cannot be changed, thus making it not hashable.</p></li></ul></li></ul><h4 id="bf6a3199-335c-4061-9f88-1fded26d1350" data-toc-id="bf6a3199-335c-4061-9f88-1fded26d1350" collapsed="false" seolevelmigrated="true">Dictionary Subscripting</h4><ul><li><p>Uses the <strong>key</strong> to access its corresponding value (e.g., <code>my_dict["id"]</code>).</p></li><li><p>Dictionaries do not have an inherent order (no first, second element by index).</p></li></ul><h4 id="b0127cff-3b7d-4da4-9e9d-94ab0e2b347d" data-toc-id="b0127cff-3b7d-4da4-9e9d-94ab0e2b347d" collapsed="false" seolevelmigrated="true">Typical List Operations</h4><ul><li><p><code>+</code> (concatenation), <code>*</code> (repetition), <code>[]</code> (subscripting).</p></li><li><p>Type errors occur if operations combine incompatible types (e.g., <code>[1] + 2</code>).</p></li></ul><h4 id="82a0cf2c-8779-417a-849b-aa2f31cc28a2" data-toc-id="82a0cf2c-8779-417a-849b-aa2f31cc28a2" collapsed="false" seolevelmigrated="true">Building Dictionaries: Merging</h4><ul><li><p><code>update()</code><strong> method</strong>: Merges one dictionary into another (e.g., <code>menu_a.update(menu_b)</code>).</p></li><li><p><strong>Union operator (</strong><code>|</code><strong>)</strong>: Merges two dictionaries (Python 3.9+)</p></li><li><p><strong>Unpacking (</strong><code>**</code><strong>)</strong>: Merges dictionaries into a new one (e.g., <code>combined_menu = {**d1, **d2}</code>).</p></li></ul><h4 id="131e567a-dea5-4c29-bf5f-4683d9fceda9" data-toc-id="131e567a-dea5-4c29-bf5f-4683d9fceda9" collapsed="false" seolevelmigrated="true">Assignment with Containers and Strings</h4><ul><li><p><strong>Multiple assignment</strong>: Python allows assigning multiple variables from a sequence or string in one line (e.g., <code>x, y, z = [1, 2, 3]</code> or <code>x, y, z = "123"</code>). Evaluation is right-to-left.</p></li><li><p><code>*</code><strong> for expansion</strong>: In multiple assignment, <code>*</code> can unpack an iterable (list, tuple, string) into multiple variables (e.g., <code>a, b, c = 1, *(2,3)</code>). A <code>ValueError</code> occurs if there are too many/few values to unpack.</p></li></ul><h4 id="283a0a88-5f60-461e-bb6a-9b163be1070d" data-toc-id="283a0a88-5f60-461e-bb6a-9b163be1070d" collapsed="false" seolevelmigrated="true">Tuple as Python's Default Container</h4><ul><li><p>When a function returns multiple items (separated by commas), Python automatically packages them into a tuple (e.g., <code>return x+1, x-1</code> returns <code>(x+1, x-1)</code>).</p></li></ul><h4 id="89564bb0-c9e3-42c6-9b3b-cc452ece0c8f" data-toc-id="89564bb0-c9e3-42c6-9b3b-cc452ece0c8f" collapsed="false" seolevelmigrated="true">Quadratic Equation Example</h4><ul><li><p>Demonstrates unpacking a tuple of coefficients(a, b, c)andreturningatupleofrootsand returning a tuple of roots(r1, r2) = ((-b - \sqrt{b^2 - 4ac}) / 2a, (-b + \sqrt{b^2 - 4ac}) / 2a)$$ using math.sqrt().

Order in Containers (Important Observation)

  • Order matters for lists and tuples in comparisons (e.g., (1, 2) == (2, 1) is False).

  • However, type conversion can allow equality (e.g., (1, 2) == (1.0, 2.0) is True).

  • For problems where order matters, specific instructions will be given (e.g., "return the smaller root first").