Data Structures: Beginner

A list stores items in numbered slots starting at 0. The first value you append lands in slot 0, the next in slot 1, and nothing moves unless you remove something. A tuple works the same way, built once with its items already seated. Both answer steps[0] with the item that went in first, every time the program runs, on every computer.

Appending report put it in slot 3, the next free position, and the earlier 3 items stayed where they were. The tuple answered slot 2 with 48 because that is where 48 sat when the tuple was written.

Line 7 changed the value under load and the key stayed in front. Deleting it and adding it back moved it to the end, since the second add is a new insertion with no memory of the old one.

A set keeps no slots at all. It stores each item at a spot computed from the item's own value, which is what lets 30 in tags answer without scanning, and it means the order you added items plays no part in the order Python prints them. Small integers often come out in numeric order on the standard interpreter, so {3, 1, 2} prints as {1, 2, 3}, which looks like sorting but is a side effect of where those numbers land. Strings come out in an order that can change between one run and the next, so code that depends on set order can pass on one run and fail on the next.

Step through it and watch in_order grow at the end while no_order places each value where its number sends it. The 2 collections hold the same 3 integers and answer different questions: the list knows what came first, the set knows what is present.

Both membership checks answered at once, because answering them is what a set is built for. Add a line print(tags[0]) and the program stops there with TypeError: 'set' object is not subscriptable. There is no slot 0 to read, and the error names the operation the set refused: subscripting, the word Python uses for square brackets written after a value.

The drill below depends on how each collection starts and grows. An empty list is [] and grows with append, which puts the item in the next free slot. An empty set is set(), since {} builds an empty dict, and it grows with add, which files the item by its value. A set has no append and a list has no add, so pairing a collection with the other one's method stops the program with an AttributeError.

Editing in place means the operation changes the existing object rather than building a new one. scores.append(90) returns nothing useful and leaves scores longer by 1 item. The same holds for metrics["errors"] = 5 on a dict and seen.add(42) on a set. In the animation below, one dict gains a key, has a value replaced and then loses a key, and the name metrics points at that same dict the whole time.

Because the object itself changes, every name bound to it sees the edit. A function that receives a list as a parameter receives the caller's list, so an append inside the function shows up outside it without any return.

pending has 3 items after the call even though record returned nothing. The function edited the one list that both names refer to.

A tuple has neither append nor remove, and it does not allow assignment into a slot. Calling a method it lacks raises an AttributeError, because the tuple has no attribute by that name. Assigning into a slot raises a TypeError, because the tuple refuses item assignment. What you can do is point the name at a different tuple, which leaves the old tuple exactly as it was and is a separate action from editing it.

Python accepted the tuple as a key, and reading it back with the same tuple returned the stored value. If the same coordinates are written as the list locations[[40.7, -74.0]] = "New York", the program stops with TypeError: unhashable type: 'list'. Unhashable is the name Python gives to values that can change and therefore cannot be filed by their contents.

An AttributeError raised on a method call usually traces back to the line that built the collection. Parentheses there make a tuple, and square brackets around the same items make a list in the same order, so changing the brackets on that one line is enough for every later append to succeed. Keep the parentheses only when the items are meant to stay fixed.

Each collection type doubles as a function. list(x) takes any collection and builds a new one of the named type holding the same items, and tuple(x) and set(x) work the same way. The source is untouched. What differs is which guarantees the new collection makes, and that is where values keep or lose something on the way across.

All 5 readings went in. The tuple reports 5 with the order intact. The set reports 3 and prints {9, 2, 4}, which is the slot order inside the set and has no relation to the order the readings arrived. The last line shows readings still holds all 5.

Watch back_to_list appear: it is a real list with a slot 0, and back_to_list[0] would work. What it cannot give back is the original arrival order or the 2 lost duplicates, because the set never had them.

Handing a dict to list() or set() gives you the keys only, in insertion order for the list. The values stay behind in the dict. This is the usual way to get a dict's keys into something you can index.

dict() runs the other direction. Give it a list of 2-item tuples and each tuple's first item becomes a key, with its second item as that key's value.

Conversion never edits the source, so to drop duplicates and keep working with a list, assign the result back: readings = list(set(readings)). After that line the order is the set's order, and the duplicate count is gone for good.

Both exercises hinge on what set() throws away and what list() can and can't restore.

Converting a dict to a set never shrinks it, because its keys were unique to begin with, so len(set(inventory)) always equals len(inventory). Converting it to a list is what makes reading by position possible: square brackets on the dict look up a key, while square brackets on the list read a slot.

The list took 4 items and len reported 4. remove deleted the first home only, so 2 copies remain. Each copy is a real item in its own slot. min counts them all, as do max and sum: sum([5, 5, 5]) is 15, and a tuple behaves the same way.

Of the 4 values added, 2 survive. add on a value already present does nothing and raises nothing, which is what makes a set the right place to record whether something has been seen rather than how often.

Write a dict literal with the same key twice and Python builds it left to right, so the second value replaces the first. The key keeps the position where it first appeared. The same rule governs dict() given a list of pairs, and plain assignment to a key that already exists.

Python raises nothing, and len reports 2. A config literal with a repeated key silently discards the earlier value, and the mistake only surfaces when the program behaves as if retries were 5. The pairs example keeps a in front with the value 10 from the later pair.

Because keys are unique, a dict is the natural place to count how often each item of a list appears: the item becomes the key and its count the value. in checks whether the key exists before deciding whether to start at 1 or add 1 to the count already there.

The list reports 5 because it kept every click. The dict reports 2 because home and cart are the only keys that ever existed, no matter how many times each was seen.

Trace the counting loop on 3 clicks and the 2 branches separate cleanly. A page's first visit finds no key, so the count starts at 1, and the key takes its position in the dict at that moment. Every later visit finds the key and adds 1 to the value under it, leaving the position alone. Flip the test to not in and the branches swap jobs with it: the first branch starts the count and the else adds 1.

Real tasks mix types, and the mix follows the same questions. The animation walks a list of click events, uses a set to remember which users have already appeared, and builds a list of each user's first event. The list preserves arrival order, the set answers not in without scanning, and the dict inside each event holds that event's fields by name.

The third capstone builds 2 collections from the same list of readings, and each answers a different count. len of a set counts distinct values, while len of a tuple counts every reading, repeats included. max returns the same highest value from either one, because dropping repeats never removes the largest value, only extra copies of it.

The last capstone depends on what square brackets mean on a dict built from pairs. dict() makes the first item of each pair a key, so a dict built from (name, quantity) pairs is read with a name. A position number between the brackets asks for a key that is that number, and when no such key exists the lookup stops with a KeyError naming the missing key.