Data Structures

Every Python program is, at heart, a program that stores data and does something with it. A data structure is the way that data is organized in memory, and the choice decides how fast you can find, add, change and remove items. The same task can take a blink with one structure and minutes with another, even when the code looks almost identical.

This chapter walks through Python's built-in structures one at a time: lists, tuples, sets and dictionaries, then the hashing idea that powers sets and dictionaries, and finally stacks and queues built from a list and from collections.deque. For each one you will see what it is, which methods it offers, how it behaves inside, and what its operations cost in Big-O terms, so you can tell an O(1) step from an O(n) one.

By the end you will be able to pick the right structure for a problem and explain why. You will know when a set beats a list for membership checks, why a list makes a poor queue, why a list can't be a dictionary key, and how to answer the common interview questions that ask about exactly these trade-offs.

A data structure is a way of organizing and storing data in computer memory so that we can access it, modify it and process it efficiently. The same pile of values can be cheap or painful to work with depending on how it is arranged, and the arrangement is exactly what a data structure decides.

Think of a kitchen. You could throw every utensil into one box, but you would dig through it for every spoon. Hang the ladles on hooks and put cutlery in a tray, and each lookup becomes quick. Python's built-in structures are those trays and hooks, each tuned for a different kind of lookup.

• Organized storage: related values live together in a shape you can reason about.
• Efficient operations: adding, finding and removing items cost less work.
• Lower time and space complexity: fewer steps and less memory for the same job.
• Optimized solutions: a well-chosen structure often turns a slow solution into a fast one without changing the idea behind it.

Here are the four built-in structures this handbook covers, each holding a small piece of data that suits it. Notice how the shape of each literal already hints at its job.

cart = ['pen', 'book', 'pen']
point = (4, 7)
usernames = {'abhi', 'sam', 'abhi'}
user = {1: 'Abhi', 2: 'Sam'}

print(cart)
print(point[0])
print(len(usernames))
print(user[2])

One value of each built-in structure

The cart kept its duplicate 'pen', the tuple was read by position, the set quietly dropped the repeated username so only two remain, and the dictionary answered a question by key rather than by position.

Each structure answers four questions: does it keep order, can you change it, does it allow repeats, and can you reach an item by index? The table puts the answers next to each other so the differences stand out.

Two footnotes explain the starred cells. Note 1: a set is unordered, so it has no concept of an index and nothing like s[0] exists. Note 2: a dictionary preserves insertion order since Python 3.7+, so it iterates in the order you added the keys.

The code below checks both footnotes. The dictionary lists its keys in the order they were inserted, not alphabetically, while two sets with the same members compare equal no matter how you wrote them.

d = {'b': 1, 'a': 2}
print(list(d))
print({1, 2, 3} == {3, 2, 1})

Insertion order for dicts, no order for sets

If the table is too much to hold in your head, boil each structure down to three words. These one-liners are worth memorizing for interviews.

Python values fall into two camps. A mutable object can be changed in place after it is created, while an immutable object can never change, so any edit produces a new object instead. This single split explains why tuples are safe to share and why only some objects can serve as set items or dictionary keys later in the handbook.

The example shows both camps in action. The list, set and dictionary all accept edits, but trying to assign into a tuple raises a TypeError, and a string method such as upper() hands back a new string while the original stays as it was.

cart.append('lamp')
print(cart)
usernames.add('lee')
print(len(usernames))
user[3] = 'Lee'
print(user)

try:
    point[0] = 9
except TypeError as e:
    print(type(e).__name__)

word = 'abc'
word.upper()
print(word)

Uses cart, point, usernames and user from the first page

Knowing the properties is only half the job; the skill is matching them to the problem. Start from what you need to do with the data, then pick the structure that makes those operations natural and cheap.

When you are unsure, walk through these questions in order. The first question that gets a yes decides the structure, and the list is the default when nothing special is required.

A list is Python's everyday container: an ordered collection that you write between square brackets. Order means every item has a fixed position, so you can ask for "the second item" and always get the same one. Items can be of any data type, the list is mutable (you can change it after creating it), and duplicates are allowed.

The list below mixes an integer, a string, a float and a boolean. The code reads one item, measures the list with len(), overwrites the first item to show that lists are mutable, and prints a list made of the same value three times.

Every item has a positive index that counts from the front, starting at 0, and a negative index that counts from the back, starting at -1. The negative form is handy because -1 is always the last item, no matter how long the list is.

my_list = [10, 20, 30, 40, 50]
print(my_list[0])
print(my_list[2])
print(my_list[-1])

First item, middle item, last item

Slicing copies a stretch of a list into a new list. The syntax is list[start : stop : step]. You begin at start, walk toward stop and take every step-th item. The stop index is excluded, so [1:4] gives positions 1, 2 and 3. Leave a part out and Python fills in a default: start at the beginning, stop at the end, step of 1. A negative step walks backward, which is why [::-1] reverses a list.

Because lists are mutable, they come with methods that change them in place. Start with the ones that add items. append(x) puts one item at the end, extend(iterable) adds every item of another collection at the end, and insert(i, x) places x at index i and shifts the later items to the right.

Each row above starts from a fresh [10, 20, 30]. The program below walks through adding and then removing on one list, so you can see each step change it. Note that pop() is the only one here that gives you something back: the removed value. del my_list[0] removes by position and returns nothing.

There are several ways to take things out, and the right one depends on what you know about the item and whether you need it back.

index(x) tells you where the first x sits, count(x) tells you how many times it appears, sort() puts the items in ascending order and reverse() flips their order. Both sort() and reverse() work in place: they change the list itself and return None. clear() empties the list completely.

Knowing the methods is half the job; the other half is knowing what each one costs as the list grows. A list keeps its items side by side, so jumping to an index is a direct calculation, while anything that has to look at or move many items grows with the list length n.

The pattern behind the O(n) rows is shifting. Putting a value at the front forces every existing item to move, as the steps below show.

Here is a small program that combines several ideas: it appends, sorts in place, prints the whole list, then slices out the middle.

A Python list looks like a row of values, but underneath it is a dynamic array. The list does not hold your objects directly. It holds references (addresses) that point to the objects, and those references sit side by side in one contiguous block of memory. That is why jumping to my_list[3] is instant: Python takes the start of the block, moves over three slots and follows the reference it finds there.

The block is not fixed. The array can grow and shrink as you add and remove items. When the list outgrows its block, Python creates a new, larger array and copies the references across. Because of this, the list usually owns more slots than it uses. Its capacity is greater than or equal to its size.

Take my_list = [10, 20, 30, 40]. Four slots hold references to the four numbers. The block has room for eight, so the other four slots are empty and waiting (the picture shows them as None).

When a list runs out of space, Python allocates a new array with more capacity, copies every reference into it and releases the old block. Here is a list that starts full, with capacity 4 and size 4, and keeps receiving items.

Note that the trace above is the idea, not the exact numbers. Textbooks say the capacity roughly doubles. Real CPython grows by about 1.125x plus a small constant, so the jumps are gentler. The shape of the argument is the same either way: each resize buys a run of cheap appends.

Now the cost. Most of the time append just drops the item into a free slot, which is O(1). Occasionally the array is full and a resize copies every element, which is O(n). Those expensive appends are rare, and the gaps between them get longer as the list grows. Over a large number of appends, the average cost per append is O(1).

This is amortized analysis: spread the rare big cost over all the appends. If n appends cost O(n) in total, then the amortized cost per append is O(1). The program below counts the work for 1000 appends, using a simple doubling rule starting at capacity 4.

capacity, size = 4, 0
copies, resizes = 0, 0

for _ in range(1000):
    if size == capacity:
        copies += size
        resizes += 1
        capacity *= 2
    size += 1

total = 1000 + copies
print('appends:', 1000)
print('resizes:', resizes)
print('items copied:', copies)
print('total work:', total)
print('work per append:', total / 1000)

Counting the cost of 1000 appends with doubling

Only 8 resizes happened, and the copying added up to about one extra unit of work per append. Each append costs roughly 2 units on average, no matter how long the list gets. That flat average is what O(1) amortized means.

The array design decides what is cheap and what is not. Anything that goes straight to a slot, or works at the end, is quick. Anything that has to slide the other items along, or look at each one, grows with the length of the list.

You can watch the spare room appear. sys.getsizeof reports the bytes the list object uses, and that figure includes the whole reference array, not just the used part. So it stays flat while appends fill free slots and jumps when a resize happens.

import sys

lst = []
print(0, sys.getsizeof(lst))
for i in range(1, 21):
    lst.append(i)
    print(len(lst), sys.getsizeof(lst))

Sizes shown are for 64-bit CPython 3.11

The empty list is 56 bytes. The first append jumps to 88, which means room for 4 references (each takes 8 bytes). The size then stays put until the 5th item, and so on. The jumps are 88, 120, 184 and 248 bytes, so capacity went 4, 8, 16 and 24. Early on it doubles, then the steps get smaller in proportion, which is the 1.125x growth showing up.

A tuple is an ordered collection of items that cannot be changed after it is created. Like a list, it keeps its items in a fixed order and allows duplicates, so (1, 2, 2) is perfectly valid. Unlike a list, it is a fixed-size sequence: nothing can be added, removed or replaced once it exists.

Because Python never has to leave spare room for growth, a tuple is also more memory efficient than a list holding the same items. Think of a tuple as a sealed envelope: you can read what is inside as often as you like, but you cannot swap the contents.

There are several ways to create a tuple. The usual form uses parentheses, but the parentheses are optional because the commas are what actually build the tuple. You can also convert any list with tuple(), write () for an empty tuple, and add a trailing comma to make a single-element tuple.

That last case is the classic trap. (10) is not a tuple: the parentheses are just grouping, so Python sees the integer 10. Only (10,), with the trailing comma, is a one-element tuple. The example below builds all five forms and then checks the types.

Tuples are indexed exactly like lists. Positions count from 0 at the left, and negative positions count from the right starting at -1. For t = (10, 20, 30, 40, 50) the indices run 0 to 4, or equivalently -5 to -1.

Slicing uses start:stop:step, and the stop index is excluded. A step of -1 walks backwards, which gives you a reversed copy. Reading and slicing never modify the original, and a slice of a tuple is itself a new tuple.

Immutability means that once the tuple exists you cannot change, add or remove elements. Every operation that tries to modify it raises an error. The exact error depends on the operation: assigning to or deleting an index is a TypeError, while calling a list method that tuples simply do not have is an AttributeError.

Packing means putting several values into one tuple just by separating them with commas. Unpacking is the reverse: you assign the tuple's items to separate variables in one statement, matched by position. The number of names on the left must match the number of items.

Unpacking also gives Python its tidy swap. In x, y = y, x, the right side is evaluated first and packed into a temporary tuple, and only then are the items assigned to the names on the left. No third temporary variable is needed.

Since a tuple cannot change, it has only two methods. count(x) tells you how many times a value appears, and index(x) returns the position of its first occurrence. There is no append, remove, sort or anything else that would modify the contents.

Tuples and lists look alike, so the choice comes down to whether the data should change. The table below sets them side by side. The tuple trades flexibility for safety, a smaller footprint and a little extra speed.

Reach for a tuple in four situations: the data should never change, you need a dictionary key, a function must return several values, or you want better performance than a list gives you. Dictionary keys must be hashable, and a list is not, because its contents can change. A tuple of hashable items can be a key, which makes it ideal for things like coordinates.

The example uses a coordinate pair as a dictionary key, shows that a list is rejected in the same position, and then returns two values from one function. Returning min(nums), max(nums) actually packs a tuple, and the caller unpacks it.

A set is an unordered collection of unique items. If you add the same value twice, the set keeps one copy and says nothing. A set has no positions, so you cannot ask for the item at index 0. What you can ask is whether a value is in the set, and that check is very fast.

Two more facts shape everything else on this page. A set is mutable, so you can add and remove items after you create it. But every item inside it must be hashable, which in practice means immutable.

Curly braces create a set. Here the literal repeats 20 and 30, and the duplicates disappear on their own. The final line prints the set directly. On CPython this particular set happens to come out as {40, 10, 20, 30}, but treat that order as an accident.

s = {10, 20, 20, 30, 30, 40}
print(type(s))
print(len(s))
print(sorted(s))
print(s)

Duplicates vanish as the set is built

Numbers, strings, tuples and frozensets are immutable, so they can live in a set. Lists, dicts and other sets can change after the fact, so Python refuses them and raises a TypeError.

A set is mutable, so it comes with methods that change it in place. Use add for one item and update for several at once. To take items out you have three choices that differ in how they treat a missing value, plus clear to empty the whole set.

The walkthrough below applies the calls in order. Printing sorted(s) keeps the output stable, because the set itself has no order to show. pop hands back an arbitrary element, so the code checks only that the returned value is gone.

Sets follow the maths you may remember from school. Four operators combine two sets into a new one without changing either. The examples use A = {1, 2, 3} and B = {3, 4, 5}, which share exactly one element, 3.

Difference is the only one of the four where the order of the operands matters. A - B and B - A give different answers, while union, intersection and symmetric difference give the same result either way round.

The in and not in operators ask whether a value is present and return a bool. This is the job sets do best.

The speed comes from hashing. A set does not scan its items one by one. It turns the value into a number with a hash function, uses that number to pick a slot in an internal table, and looks only there.

Because a set has no order, two sets are equal when they hold the same elements, however you wrote them. Equality never looks at position.

The single-item operations are O(1) on average, because hashing finds the slot directly. The combining operations must look at the elements of the sets involved, so they grow with the size of the data, which is O(n). The word average matters here. If many items collide on the same slot, a set can degrade towards O(n), though that is rare.

• You need unique items, for example distinct usernames.
• You need fast membership checks on a lot of data.
• Order does not matter to you.
• You want union, intersection, difference or symmetric difference.

A dictionary stores data as key-value pairs. You don't ask for item number 3. You ask for the value filed under a key such as 'age', and Python hands it back. Under the hood a dict is a hash table, which is why that lookup is so quick.

Values in one dict don't have to share a type. Here one record holds a string, an int, a list and a boolean, and you read each one through its key.

d = {'name': 'Abhi', 'age': 23, 'skills': ['Python', 'SQL', 'Git'], 'is_employed': True}
print(d['name'])
print(d['skills'][1])
print(len(d))

Mixed value types in one dictionary

The key rules show up when you break them. Two keys may point at the same value, but a list can't be a key because it is mutable and therefore unhashable.

scores = {'a': 1, 'b': 1}
print(scores)
try:
    bad = {[1, 2]: 'x'}
except TypeError as e:
    print(e)

Duplicate values are fine, mutable keys are not

A dict is often described as unordered, and that starred word needs care. A dict has no index positions, so you can't ask for the third item. Since Python 3.7 it does remember the order in which keys were inserted, and loops and printing follow that order. Older versions made no such promise.

order = {}
order['z'] = 1
order['a'] = 2
order['m'] = 3
print(list(order))

Insertion order is kept, not alphabetical order

A dict doesn't search through its pairs one by one. It passes the key to a hash function, which returns an integer. That integer is reduced to an index in the table, and the key-value pair is stored in that slot. To look the key up later, Python repeats the same steps and goes straight to the slot.

Here is that walkthrough for a table with 8 slots. The hash value 5721 is illustrative. Real string hashes change from one run of Python to the next, but the steps are always the same.

Because each step is a single calculation, lookup, insert and delete take O(1) on average. The cost doesn't grow with the number of pairs in the dict.

A table with a limited number of slots can't give every key its own. Two different keys can land on the same index, which is called a collision. Python resolves collisions with open addressing: if the slot is taken, it probes other slots in the same table by a fixed pattern until it finds a free one. The toy hash below, which sums character codes, shows how easily collisions happen.

def slot(key, size=8):
    return sum(ord(c) for c in key) % size

for k in ['age', 'name', 'ega']:
    print(k, slot(k))

A toy hash, not Python's real one

'age' and 'ega' are different keys that both map to slot 5. A real dict would keep both and probe onward for the second one.

Start with the basic operations. Square brackets add, read and update a key, del removes it, in tests membership, and a plain for loop walks the keys.

d = {'a': 1, 'b': 2}
d['c'] = 3          # add
print(d['a'])       # access
d['b'] = 20         # update
del d['a']          # delete
print('c' in d)     # membership
print(len(d))       # number of pairs
for k in d:
    print(k, d[k])

The basic operations on one small dict

Methods cover the cases where brackets are awkward. First, the ones that read data. get is the safe way to look up a key that may be missing, because it returns a default instead of raising KeyError.

Next, the methods that change the dict. update merges another dict in, and setdefault inserts a key only when it is missing.

p = {'name': 'Abhi', 'age': 23}
print(p.get('age'))
print(p.get('city', 'NA'))
print(list(p.keys()))
print(list(p.values()))
print(list(p.items()))
p.update({'age': 24})
print(p)
print(p.setdefault('city', 'Pune'))
print(p.setdefault('city', 'Delhi'))
print(len(p))

Reading, merging and setdefault

The second setdefault call didn't replace 'Pune' with 'Delhi'. The key already existed, so its current value came back unchanged. Now the removal methods.

q = {'a': 1, 'b': 2, 'c': 3}
print(q.pop('a'))
print(q.pop('zz', 'none'))
print(q.popitem())
backup = q.copy()
q.clear()
print(q, backup)

Removing items and taking a copy

orig = {'skills': ['Python']}
dup = orig.copy()
dup['skills'].append('SQL')
print(orig)

The inner list is shared

A dictionary comprehension builds a dict from a loop in one expression. The part before the colon is the key and the part after it is the value.

squares = {x: x * x for x in range(1, 6)}
print(squares)

Each number becomes a key, its square the value

Every core operation goes through the hash table, so each one costs the same however large the dict grows.

Every dict and set rests on one trick, which is hashing. A hash function turns a key into an integer, and that integer tells Python where in memory to look for the value. Python does not scan the collection comparing keys one by one. It computes a number and jumps close to the answer. That is why lookup, insertion and deletion are fast, O(1) on average for both dicts and sets.

A hash function takes an input, the key, and produces an integer, the hash value. Two properties matter. The output is always an integer, and the same input always gives the same hash value within one run of the program. Python exposes this through the built-in hash(). Integers hash to themselves, so hash(123) is 123 and hash(42) is 42. Strings, floats and tuples are mixed into much larger integers.

print(hash(123))
print(hash(42))
print(hash(123) == hash(123))
print(hash('Abhi') == hash('Abhi'))
print(hash((1, 2, 3)) == hash((1, 2, 3)))
print(type(hash('hello')).__name__)

Same input, same hash, and the result is always an int

You will see numbers such as hash('Abhi') giving 274836809, hash((1,2,3)) giving 529344067 and hash(3.14) giving 322818021 in notes like these. Treat them as illustrations of the kind of number you get, not values to memorise. On a 64-bit Python the real ones are much longer. String hashes are also deliberately randomised for each new interpreter run, so hash('hello') will differ between runs. Only the property that matters is guaranteed: inside one run, equal keys hash equally.

An object is hashable if it has a hash value that stays the same for its whole lifetime. Only hashable objects can be dict keys or set elements. Asking an unhashable object for its hash raises a TypeError.

try:
    hash([1, 2, 3])
except TypeError as e:
    print(e)

try:
    d = {[1, 2]: 'value'}
except TypeError as e:
    print(e)

print(hash((1, 2, 3)) == hash((1, 2, 3)))

try:
    hash((1, [2, 3]))
except TypeError as e:
    print(e)

Lists fail as keys; a tuple is hashable only if everything inside it is

The reason lists are refused is mutability. A dict files each entry under the slot its key's hash points to. Suppose a list could be a key and you later appended to it. Its contents, and therefore its hash, would change, and Python would look in a different slot and never find the entry it stored. That would break the contract between the key and the table. Python removes the whole problem by refusing unhashable keys up front with a TypeError, instead of letting the table be corrupted quietly.

Dicts and sets share the same machinery, and both are built on a hash table. A set hashes each element to an index and stores the element there. A dict does the same with each key, and stores the value alongside it. This is why the rules for set elements and dict keys are identical.

Two different keys can still end up wanting the same place. This is a collision. It happens when two keys have the same hash, or when different hashes are reduced to the same table index. In the illustration below, 'abc' and 'cab' both hash to 12345, and both therefore map to index 5. The numbers are made up for the picture. Real collisions between strings are rare.

Python handles collisions inside the table, and you never write code for it. CPython uses open addressing with probing. When a slot is taken by a different key, it follows a fixed sequence to the next candidate slot and tries that. On lookup it follows the same sequence, comparing hashes and then keys with ==, until it finds the key or reaches an empty slot. The other classic technique, chaining, keeps a small list of entries at each slot. Both ways of dealing with collisions stay cheap as long as collisions are rare.

class Clash:
    def __init__(self, name):
        self.name = name
    def __hash__(self):
        return 5
    def __eq__(self, other):
        return self.name == other.name

a, b = Clash('abc'), Clash('cab')
print(hash(a) == hash(b), a == b)
d = {a: 1, b: 2}
print(len(d), d[a], d[b])

A deliberate collision: every key hashes to 5, yet both entries survive

The two keys have the same hash but are not equal, so Python keeps both and tells them apart with ==. That is the rule behind everything here: equal objects must have equal hashes, but equal hashes do not imply equal objects. The cost is speed. If many keys collide, probing grows long and the average O(1) drifts toward O(n).

Now for classes you write yourself. By default Python hashes a custom object by its identity, so two objects that look the same are still different keys. The behaviour changes the moment you define __eq__ without __hash__. Python then sets __hash__ to None and the class becomes unhashable, because you changed what equality means and it will not guess a matching hash.

class Plain:
    def __init__(self, x):
        self.x = x

print(Plain(1) == Plain(1))
print(len({Plain(1), Plain(1)}))

class OnlyEq:
    def __eq__(self, other):
        return True

try:
    hash(OnlyEq())
except TypeError as e:
    print(e)

Default identity hashing, then what happens when only __eq__ is defined

To make a class behave as a value, define both methods. __eq__ decides when two objects are the same. __hash__ must agree with it, so the simplest approach is to hash a tuple of exactly the fields that __eq__ compares.

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y
    def __hash__(self):
        return hash((self.x, self.y))
    def __eq__(self, other):
        return self.x == other.x and self.y == other.y

p1 = Point(1, 2)
p2 = Point(1, 2)
print(p1 == p2, hash(p1) == hash(p2))
visited = {p1}
print(p2 in visited)
print(len({p1, p2, Point(3, 4)}))

Equal points now collapse to one set member

A stack follows the rule Last In, First Out (LIFO): the item you added most recently is the first one to come back out. All the action happens at a single end called the TOP. You add at the top and you remove from the top, and nothing in the middle is touched.

You meet stacks all the time without noticing. The undo command in an editor reverses your latest change first. The browser back button returns you to the page you visited most recently. The function call stack runs the function that was called last and finishes it before returning to its caller.

Python has no separate stack type, because a plain list already does the job. The end of a list is its cheap end, so append() is your push and pop() with no argument is your pop. Reading stack[-1] shows the top without removing it, which is called a peek.

stack = []
stack.append(10)   # push
stack.append(20)
stack.append(30)
print(stack)
print(stack.pop())  # pop removes the top
print(stack[-1])    # peek at the new top
print(len(stack))   # size
stack.clear()       # empty the stack
print(stack, len(stack) == 0)

A list used as a stack

Every one of these operations works on the end of the list. Nothing has to move, so each one costs the same no matter how many items the stack holds.

A queue follows First In, First Out (FIFO): whoever arrived first is served first. New items join at the REAR and leave from the FRONT. Think of the line at a ticket counter. Print jobs are handled in the order they were submitted. Breadth first search (BFS) visits nodes in the order it discovered them.

For queues Python gives you collections.deque, short for double-ended queue. It is built so that adding or removing at either end is cheap. You enqueue with append(), which adds at the rear, and you dequeue with popleft(), which removes and returns the front item. Looking at q[0] shows the front without removing it.

from collections import deque

q = deque()
q.append(10)   # enqueue at the rear
q.append(20)
q.append(30)
print(q)
print(q.popleft())  # dequeue from the front
print(q[0])         # peek at the new front
print(len(q))       # size
q.clear()
print(q, len(q) == 0)

A deque used as a queue

The queue operations you will use most often fit in one small table.

A list can be used as a queue, but it is not recommended. Enqueueing is fine, because append() adds at the end. The trouble is dequeueing, because the front of a list is the expensive end. You do it with pop(0), and that is O(n).

q = []
q.append(10)    # enqueue
q.append(20)
q.append(30)
print(q.pop(0))  # dequeue, costs O(n)
print(q)

A queue built on a list: it works, but slowly

The reason is how a list is laid out. Its items sit side by side in one block of memory, and the slot numbered 0 must always hold the first item. When pop(0) removes the front, a hole appears at position 0. To close it, every remaining element is shifted one position to the left. With 3 items that is trivial. With a million queued items, every single dequeue moves a million references.

A deque avoids this because it does not insist that the first item live in slot 0 of a single block, so popleft() removes the front without moving the rest. That is why both ends cost O(1).

Stacks and queues are really use cases, not separate data types. Both are built from a list or a deque, and what makes them what they are is the order in which items come out. Choose by asking which item you need next: the newest or the oldest.

Python gives you several containers that look similar from a distance. Each one makes some operations cheap and others expensive. Choosing well means knowing which operations your program performs most, then picking the container that makes them fast. The table below compares the five structures you have met so far.

The asterisk on the dict row matters: dictionaries remember insertion order since Python 3.7, but that order is not a sorted order. The word avg on the set and dict rows means the O(1) comes from hashing. A pile of collisions can push the worst case towards O(n).

Read the table in two passes. First look at the Mutable and Duplicates columns, which tell you what the data is allowed to look like. Then look at the Access and Search columns, which tell you how quickly you can get things back out.

When you are unsure, walk through five questions in order. The first question that gets a yes decides the structure. If every answer is no, the plain list is your default.

The flowchart is a starting point, not a law. A real problem sometimes needs two structures at once, such as a dict for lookups plus a list for ordering. The questions still help, because each one asks about an operation your code must perform.

Here are the common scenarios, each with the structure that fits and the reason. The reasoning matters more than the answer, because it carries over to problems you have not seen yet.

The cart and the point show the line between list and tuple. A cart changes as the user shops, and the same item may appear twice. A point is a single fixed pair, so unpacking it into two names is natural and nobody can overwrite it by accident.

Removing duplicates and checking for an existing email are both jobs for a set. Converting a list to a set drops repeats, and the in test hashes straight to the right slot instead of walking through every item. A set does not keep order, so if you need unique items in their original order, use list(dict.fromkeys(items)) instead.

User records and task queues call for a dict and a deque. A dict gives you the record by id without scanning, and a second dict keyed by email gives you the reverse lookup. A deque removes work from the front in constant time, which is what a first-in, first-out queue needs.

Undo and redo behave like two stacks, and a plain list is a good stack because append() and pop() both work at the end in O(1). Counting words is the classic dict job: the word is the key and the running count is the value.

Most wrong choices come from using a familiar structure out of habit. These are the mistakes that show up most often, along with the fix for each.

Every built-in structure answers two questions: does order matter, and can the contents change? A list is ordered, mutable and allows duplicates. A tuple is also ordered and allows duplicates, but it is immutable, so it is fixed once built. A set drops order and duplicates: it is unordered, mutable and stores only unique items. A dict stores key-value pairs. It keeps insertion order, is mutable, and every key is unique.

Stacks and queues are not separate types. They are usage patterns. A stack is LIFO (last in, first out) and a plain list does it well with append() and pop(). A queue is FIFO (first in, first out) and collections.deque does it best, because popleft() is O(1) while list.pop(0) shifts every remaining item. Picking the right structure improves both time and space efficiency.

Start from the operations you need, then choose the structure that makes them cheap. The table lists the situation each one is built for, and the diagram below turns it into a decision path.

This table puts the four core operations side by side for all five structures. A dash means the operation does not apply: a set has no index to access, and a tuple cannot be inserted into or deleted from because it is immutable.

Delete follows the same pattern as insert. A list is cheap at its end because there is no shifting, and costly anywhere else because every item behind the position moves. A deque is O(1) for inserts and deletes because it works at its two ends. Reaching an item in the middle of a deque is slower, so its O(1) access really means the ends.

Speed is half the story. Memory differs too, and the figures here are rough guidance rather than exact numbers.

Comprehensions build a list, dict or set in one readable line. The list version squares the numbers 1 to 5. The dict version maps each number to its square. The set version keeps only the distinct remainders of dividing by 2, so ten numbers collapse into two values.

A deque is imported from collections. It adds to the left as cheaply as to the right, which a list cannot do. Here appendleft(0) puts a new front item in place, and pop() takes the last one off the right.

Given numbers and a target, find the two positions whose values add up to it. Scanning every pair costs O(n squared). Instead, keep a dict seen that maps each value to its index. For each new number, one O(1) lookup asks whether its partner target - x has already been seen, so the whole job takes a single pass.

Imagine a strip of values and a window of three that slides along it. A deque with maxlen=3 does the sliding for you: appending a fourth item pushes the oldest one out of the left end automatically, in O(1).

Counting how often each item appears is a dict job. freq.get(ch, 0) returns the current count, or 0 for a character not yet seen, so no special first-time case is needed.

The patterns above come down to a short list of habits. Each one swaps a slow default for a structure that fits the job.

• Understand the time complexity of an operation before you choose a structure for it.
• Write clean, readable, pythonic code: a comprehension, enumerate or dict.get often says in one line what a loop needs five for.
• Remember the memory side: tuples are the lightest, while sets and dicts pay for their hash tables.
• Say the cost out loud when you compare two choices, such as list against deque.

Work out each answer before you open it. These questions ask you to predict output or find the bug, because that is what interviews do.

• Lists are ordered, mutable and allow duplicates; tuples are the same but immutable, so they can be dict keys.
• Sets keep unique, hashable items with no order, and dicts map unique keys to values in insertion order.
• List append is amortized O(1) thanks to spare capacity; inserting or deleting anywhere else is O(n).
• Sets and dicts use hashing, so lookup, insert and delete are O(1) on average, and only hashable objects can be keys.
• Use a list as a stack (LIFO) and a deque as a queue (FIFO), because list.pop(0) is O(n).
• Pick the structure by the operations you need most, and state its complexity when you explain your choice.