Python lists and deque

Why it matters

Real programs almost never know in advance how many items they will handle. A shop has a different number of orders each day. A game has a different number of enemies on screen each second. A program that needs to grow a fixed-size row of values has to build a bigger row and copy everything across by hand.

Python's built-in list is the container you will reach for most often. It grows, shrinks and searches for you. collections.deque (read "deck") is the built-in alternative for work at both ends of a line. This lesson teaches both, and it teaches what each operation costs. Interviewers ask about costs as often as they ask about syntax, so you need both.

Start from the problem: a row of slots

Picture a row of numbered slots in memory, all the same size and numbered from 0. Programmers call this an array. A fixed-size array has a length that you choose once. If you need one more slot, you must make a new row of six and copy the five old values into it.

Arrays are fast for reading and writing a slot you already know the number of. The computer finds slot i by multiplying the index by the size of one slot and adding the start address. That takes the same time whatever the row length is. What a fixed array cannot do is grow.

A Python list is a row of slots that grows by itself. You never copy items by hand. The price is that some operations are slower than others, and the price differs from one container to another. That difference is the main theme of this module.

Five words you need first

Several terms appear on every page of this module. Here they are in plain words.

An object is a piece of data in memory that has a type, such as a number, a text string or a list. Everything in Python is an object.

A method is a function that belongs to an object. names.append("Asha") calls the append method of the list names. Methods are written with a dot after the object.

A reference is a stored address that says where an object lives. In Python, a variable name does not hold a box with the value inside it. It holds a reference to the object. Two names can refer to the same list, and then a change through one name shows up through the other.

An index is a position in a sequence, counted from 0. In names[1], the index is 1, and it picks the second item.

Big-O describes how the time an operation takes grows as the number of items grows. We write the number of items as n. O(1) means the time does not depend on n. O(n) means the time grows in step with n: twice as many items means about twice the time. You do not need exact timings. You need to know which operations touch one item and which operations may touch every item.

Python also does not ask you to name the item type of a list. A list can hold a number, then a text string, then another list. The optional type hint list[str] only records what you intend. Python does not stop you from breaking it when the program runs. The example in the common mistakes section shows this.

An analogy: a bookshelf and a treasure hunt

Picture two ways to store a line of books.

The first is a bookshelf. Every book sits in a numbered slot, and the slots are next to each other. If someone asks for the book in slot 7, you walk straight to slot 7 and take it. That is what a list does. But suppose you want to put a new book into slot 2. Every book from slot 2 onward must slide one slot to the right to make room. The more books on the shelf, the more sliding.

The second is a treasure hunt. Each clue sits in its own box, and each box names the box after it and the box before it. If someone asks for the seventh clue, you must start at the first clue and follow the names six times. That is what a linked list does. Python has no built-in linked list, but deque is built so that adding and removing at both ends is cheap. Suppose you want to add a clue at the front. You make the new box name the old first box, and you tell the start of the hunt that the new box is first. Nothing else moves.

Neither picture is better in general. The right question is which operations your program does most often. The rest of this lesson makes that question precise.

Your first list

Here is a complete program. Read it one line at a time, then run it to check the output.

The output is:

['Asha', 'Meera', 'Ravi']
Asha
['Asha', 'Meera', 'Dev']
['Meera', 'Dev']
2
True
1
0

The line names = [] creates an empty list. The square brackets make a list, the same way quotes make a text string. The first two append calls add Asha and then Ravi at the end, so the list is ['Asha', 'Ravi']. The call insert(1, "Meera") puts Meera at index 1, which pushes Ravi to index 2. The first print shows ['Asha', 'Meera', 'Ravi'].

Indexes start at 0. So names[0] is the first item, Asha. The line names[2] = "Dev" replaces the item at index 2 and does not change the length. The statement del names[0] deletes the item at index 0, which leaves ['Meera', 'Dev']. The function len returns the number of items, which is 2. The in test checks whether any item equals Dev, and it gives True. The method index returns the position of the first match, which is 1. The method count returns how many items match, which is 0 for Zed. The index method, unlike count, raises an error when nothing matches. You will see that in the next section.

Notice what the program never does. It never makes a fixed-size row, never copies items by hand and never says how big the list should be. That work happens inside the object, and the next section explains it.

What happens inside a list

A Python list stores a row of references. Each slot holds a reference to an object, and the object itself sits somewhere else in memory. This is why one list can hold numbers, text and other lists together.

Hidden inside the object are two numbers. The capacity is the number of slots the row owns. The length is how many of those slots hold real items. Capacity is always at least as large as length.

When you add an item and the length already equals the capacity, the list must grow. It creates a bigger row, copies every reference across, and then stores the new item. CPython, the standard Python interpreter, grows the row by a little more than the current size each time, so the number of copies stays small. The exact growth rule is an implementation detail and it changes between versions. You can see the capacity grow by watching sys.getsizeof, which reports how many bytes the list object takes:

The output on Python 3.14 is:

length 1 bytes 88
length 5 bytes 120
length 9 bytes 184
length 17 bytes 248
length 25 bytes 312
length 33 bytes 376

The jumps happen at lengths 1, 5, 9, 17, 25 and 33. Between jumps, append only writes into the next free slot. Each jump copies every reference, which costs O(n) on that one call. Most appends cost one step. If you average the cost over a long run of appends, the expensive copies are rare enough that each append costs about one step. Programmers call this amortized O(1), which means "constant time on average over many operations." When someone says that appending to a list is O(1), this is the reason. The numbers printed above can differ on another Python version or machine.

Reading is simple. To answer names[i], the list checks that i is a valid index and then reads slot i directly. The same arithmetic works for any index, so the time does not depend on the list length. That is O(1).

Inserting in the middle is the slow case. To insert at index i, the list moves every reference from i to the end one slot to the right, then writes the new item into the gap. If the list has a million items and you insert at the front, all million references move. That is O(n).

What happens inside a deque

A deque does not use one row of slots. It stores items in small blocks, and each block knows about the block before it and the block after it. You can think of it as a row of short rows, linked at the ends. Because of that layout, adding or removing at either end only touches the end block, and the cost does not depend on how many items the deque holds. That is O(1).

To see the linked idea directly, here is a tiny linked list built by hand. Each node is a small object with a value and a reference to the next node. The None value means "no next node."

The output is:

Ana
Bo
Ana -> Bo -> None

Adding a node at the front only changes one reference. The new node points to the old head, and head now points to the new node. The other nodes do not move. Reaching the third node, however, means following the references from the head, one node at a time. That walk is O(n). Python's deque avoids this walk for the two ends, but when you ask for an item in the middle, it also has to walk, so d[i] in the middle of a deque costs O(n).

In a real program, each node is a separate object placed somewhere in memory, so following the links jumps from place to place. A list's references sit next to each other, so the processor reads them quickly. This is one reason list is usually faster in practice, even for operations where the two containers have the same Big-O cost.

The cost table

Here is how the two containers compare for the operations you will use most. Each entry is a cost in terms of the number of items, n.

Look at the row for deleting in the middle. Both containers are O(n) there. A deque must walk to the position before it can unlink the item, and walking is the expensive part. People who choose a deque because "inserting is O(1)" often forget this. The O(1) claim is true only when you already hold a reference to the place where the change happens, which a plain index does not give you.

In practice, list is the right default. It is faster than deque for almost everything because its references sit side by side in memory. Use deque mainly when you need cheap changes at both ends. Even then, a deque is the usual choice, so you never need to write your own linked list for ordinary work.

The remove trap

Here is the trap that catches almost every beginner. Python has two ways to delete from a list, and they look alike. del lst[i] and lst.pop(i) delete by position. lst.remove(x) deletes the first item equal to x. The number you write decides the meaning only through the method you choose, so read the method name carefully.

Run this program and check the output against the comments.

The output is:

[10, 30]
[30]
[1, 2]

The line nums.remove(20) looks for the value 20 and deletes it. The list becomes [10, 30]. The line nums.remove(10) looks for the value 10, so it deletes the first item equal to 10 and does not care about positions.

The mistake looks like this. A beginner who wants the item at position 10 writes nums.remove(10), which means "delete the value 10." If the value is not in the list, Python raises an error instead of silently doing something else:

The output is:

caught: list.remove(x): x not in list
caught: pop index out of range

A helpful way to remember it: remove takes a value, and pop or del takes a position. If you want to delete by position, write del nums[i] or nums.pop(i).

The third part of the first program shows the clean way to delete by condition. The list comprehension [n for n in more if n != 3] builds a new list that keeps only the items that pass the test. The name more then refers to the new list. The old list is freed if nothing else refers to it. If you need to change the same list object in place, write more[:] = [n for n in more if n != 3]. The slice assignment replaces every slot of the existing list.

Reading the whole list

There are three common ways to visit every item. Choose by what you need.

for name in names:
    print(name)
 
for i, name in enumerate(names):
    print(i, name)
 
for i in range(len(names)):
    print(i, names[i])

The first form is the for loop over items. It is the clearest when you only need each value. The second form uses enumerate, which gives you the index and the item together. It is the right choice when you need the position. The third form uses range(len(names)) and is the older style. You need it only when you must change a list by position and the other forms do not suit the job.

Notice that Python uses len(names), not names.length or names.size(). Those attributes do not exist on a list, and the error is one of the most common ones for people who come from other languages. The common mistakes section shows the message.

A worked example: removing every match from input

Now a program that reads input from the keyboard. Save it as a file, then run it in a terminal and type the three lines of input below. The first line is how many numbers follow. The second line holds those numbers, separated by spaces. The third line is the value to remove everywhere in the list.

6
4 7 4 9 4 2
4

n = int(input())
nums = [int(part) for part in input().split()]
x = int(input())
 
nums = [v for v in nums if v != x]
print(nums)
print(len(nums))

The output is:

[7, 9, 2]
3

Here is what happens step by step. The function input() reads one line of text. The call int(...) turns text into a whole number, because input() always returns text. The first line gives n, which is 6. The program does not need n to split the second line, since split() already counts the parts. The list comprehension reads each piece of the second line, converts it to a number, and builds the list [4, 7, 4, 9, 4, 2]. The third line gives x, which is 4. The comprehension then keeps every value that is not equal to x, which leaves [7, 9, 2]. The last line prints the length.

The value n is read but not used. This is on purpose. The first line still has to be read, so that the next input() call gets the second line.

Two details matter for the timing of this program. The comprehension walks the list once, so it costs O(n). A loop that calls remove for each match would cost O(n) per deletion, and the total could reach O(n squared). That difference matters when n grows to a hundred thousand.

A deque as a line of people

A deque works well as a line where people join and leave at both ends. Its methods are named for that job: append and appendleft add at the end and the front, and pop and popleft remove from the end and the front.

The output is:

deque(['VIP', 'Ana', 'Bo'])
VIP Bo
VIP
Bo
deque(['Ana'])
Ana

The method appendleft put VIP ahead of Ana. The method popleft removed VIP from the front and returned it. The method pop removed Bo from the end and returned it. Each of those four calls changes only the end of the deque, so each one is O(1).

The first line of output shows deque([...]) instead of a plain list. This is only how the deque prints itself. The name deque is also the name of the class, which is why the import line comes first.

Notice line[0]. It works, but on a long deque, asking for an item in the middle this way is slow. If you find yourself indexing a deque inside a loop, switch to a list.

There is a second reason to be careful. A small deque uses more memory than a small list, because it keeps block bookkeeping. On Python 3.14, one item takes 760 bytes in a deque and 64 in a list. At a million items the two are about the same size. Measure before you choose a container for memory reasons.

Copying, converting and tuples

Lists often need to become other containers, and other containers often need to become lists. Python gives you short tools for this.

The function list(...) builds a new list from any sequence or iterable:

The output is:

[3, 1, 2]
[3, 1, 2, 9]
[0, 1, 2, 3]
['a', 'b', 'c']

The call list("abc") splits the text into one-character strings. The copy list(nums) makes a new list object, so appending to copy does not change nums. The slice nums[:] makes the same kind of copy.

If you want a list that cannot change after it is made, use a tuple. A tuple is written with round brackets, such as (3, 1, 2). The function tuple(nums) converts a list to a tuple. A tuple has no append or remove methods, so a function that returns data callers should not change can return a tuple. The next section shows what happens when you try to change one.

Fixed containers and their errors

A tuple cannot be changed after it is made. The program below shows what the failures look like, including what happens when you ask for an index that does not exist.

The output is:

caught: list index out of range
caught: 'tuple' object has no attribute 'append'
caught: StopIteration
[1, 2, 3]

The first message is short. It says list index out of range and does not name the index or the length. Index 3 does not exist in a list of length 3, because the valid indexes are 0, 1 and 2. When you see this message, look at the line that makes the index, and print len(items) just before it. The value in the index and the length tells you the cause.

The second message names the type of the object, tuple, and the missing method. That tells you the object is not a list. The third message is the same kind of thing for an empty iterator. The next function asks an iterator for its next item, and an empty iterator has none, so it raises StopIteration. Loops handle that error for you, which is why you rarely see it. The last lines show the fix: wrap the tuple in list(...) and append works.

What happens when you pass the wrong type

Python does not check the types of list items when the program runs. The type hint list[int] is a note, not a rule. The program below adds text to a list that a hint says holds integers. It runs without any error.

The output is:

[1, 2, 'three']

A type checker such as mypy reads the hints and reports the mismatch before the program runs. Python itself does not. The mistake shows up later, when code adds or compares values of the wrong type. For example, sum(nums) raises TypeError: unsupported operand type(s) for +: 'int' and 'str' as soon as it meets the text.

A subtler case is comparing values with is. The operator is asks whether two names refer to the same object. The operator == asks whether two values are equal. CPython keeps shared objects for small integers from -5 to 256, so is can look right by accident for small numbers. Use == to compare values.

The output is:

True False

The two numbers are equal, but they are two different objects. Use is only for checks such as x is None.

Equality, copies and sizing

Three details about lists trip people up once they start passing them between functions. They concern equality, copying and the initial size.

Equality compares order and content. Two lists are equal when they hold the same items in the same order. The expression [1, 2] == [1, 2] is True. The lists [1, 2] and [2, 1] are not equal, because the order differs. A list and a tuple are never equal, so [1, 2] == (1, 2) is False. Sets behave differently, because they ignore order: {1, 2} == {2, 1} is True. When you compare two containers in a test or an interview answer, say which kind of equality you mean.

Copying a list copies the slots, not the items. The call list(original) or the slice original[:] makes a new list that holds the same items. If you append to the copy, the original does not change. If you change an object inside the list, both lists see the change, because both point to the same object. Picture a photocopy of a list of index cards. The new sheet has the same words, but the cards you hand around are still the originals. A copy protects the structure of the list, not the objects inside it.

The output is:

[[1, 99], [2]]
[[1, 99], [2], [3]]

The list original gained the 99, because shallow and original share the inner lists. The new item [3] appears only in shallow. To copy the inner lists as well, use copy.deepcopy(original) from the standard copy module.

Capacity is not length. Python has no argument for the initial capacity. To make a list with 10000 slots that are already filled, write [0] * 10000. That list has a length of 10000 and every item is 0. The list comprehension [0 for _ in range(10000)] gives the same result and is slower, but it is useful when each slot needs its own value. Presizing helps when you know roughly how many items you will add and each slot will be overwritten. Without it, the list grows many times, and each growth copies every reference. For ordinary code, leave the growth to Python. Use presizing only when a timing test shows the list is slow.

Searching a list: linear and binary

Finding a value in a list costs O(n) when you know nothing about the order. The in test and the index method check each item from the start until they find a match or reach the end. On average they look at half the list, and in the worst case they look at all of it. That is the price of not knowing where a value sits.

If the list is sorted, you can do much better. Binary search looks at the middle item. If the middle is the value you want, it stops. If the wanted value is smaller, it repeats on the left half. If the value is larger, it repeats on the right half. Each step throws away half of what is left, so a sorted list of a million items needs about twenty comparisons instead of a million. The standard bisect module does this for you. The function bisect.bisect_left(items, x) returns the position where x belongs, and the function bisect.insort(items, x) inserts x at that position.

The output is:

2
3
[1, 3, 4, 5, 7, 9]

The position returned for a value that is in the list is the position of its first copy. The position returned for a value that is missing is the place where it would go. To check whether a value is present, look at that position and confirm that the item there is equal to the value.

The price of binary search is that the list must stay sorted. Sorting costs O(n log n) once. If you search many times after that, the sort pays for itself quickly. If you insert new items in between searches, insort keeps the list sorted after each insert, at O(n) per insert because the items after the position move. The practice exercises include inserting into a sorted list by hand.

Common mistakes

Here are the mistakes that appear most often in the first weeks of Python lists, with the message you will see and how to fix each one.

Using .length or .size() on a list. A list has no such attribute. Python reports 'list' object has no attribute 'length' or 'list' object has no attribute 'size'. Replace it with len(names).

Calling add on a list. Lists use append, not add. Python reports 'list' object has no attribute 'add'. Use append(x) to add at the end, or insert(i, x) to add at a position.

Removing the wrong thing. remove(2) looks for the value 2. del lst[2] and lst.pop(2) remove the item at position 2. If you want the position, use del or pop.

Expecting a number to mean a position in remove. When a list holds numbers, remove(9) still means "the value 9." If the value is missing, you get list.remove(x): x not in list.

Reading past the end. items[len(items)] raises IndexError: list index out of range. A loop written as range(len(items) + 1) instead of range(len(items)) causes exactly this error on its last pass. The debugging walkthrough below shows this case.

Changing a list while looping over it. Python does not raise an error here, which makes the mistake harder to see. Removing items inside a for loop moves the items after each removal, so the loop skips some of them. The next example shows the skip.

The output is:

[1, 3, 2]

Three items equal to 3 were in the list, but one of them survived. When the first 3 was removed, the item after it moved into its slot, and the loop then moved past that slot. Build a new list with a comprehension instead, as the worked example did.

Using a deque when you need the middle. A deque is fast at both ends. If you index it in a loop, the cost is O(n) per index in the middle. Use a list for that work.

Adding to a tuple. Tuples have no append. Python reports 'tuple' object has no attribute 'append'. Convert with list(...) first, or build the list from the start.

A debugging walkthrough

Here is a bug that beginners write all the time. The program is meant to print every item in a list. It crashes with this message:

Traceback (most recent call last):
  File "main.py", line 3, in <module>
    print(items[i])
          ~~~~~^^^
IndexError: list index out of range

Read the message in two steps. The last line, IndexError, names the kind of problem. The text after it says the index was out of range. The traceback also points at the line and the expression that failed, which is items[i]. The message does not tell you the bad index or the length, so you must find those yourself.

Now find the line that caused it. Suppose the loop looks like this:

items = ["a", "b", "c"]
for i in range(len(items) + 1):
    print(items[i])

Trace the loop by hand. len(items) + 1 is 4, so range(4) produces 0, 1, 2 and 3. When i is 0, the loop prints a. When i is 1, it prints b. When i is 2, it prints c. When i is 3, the loop calls items[3], which does not exist. Running the code confirms the trace:

a
b
c
Traceback (most recent call last):
  File "b.py", line 3, in <module>
    print(items[i])
          ~~~~~^^^
IndexError: list index out of range

The fix is to remove the + 1, so the range stops at len(items) - 1. The valid indexes are 0 through len(items) - 1. Writing for item in items: avoids the index entirely.

This pattern teaches a general habit. When an index error appears, write down the valid range, then check the first and last values of the loop variable. Most off-by-one bugs show up at one of those two ends.

Variations and edge cases

An empty list is the first edge case to test. items[0] on an empty list raises IndexError with the same message. Check if items: before you read the first or last item.

Negative indexes count from the end. In Python, items[-1] is the last item and items[-2] is the one before it. This is different from many other languages, where a negative index is an error. The rule is that items[-k] for k from 1 up to the length works. An index below minus the length raises an error.

Slices with a zero. The slice items[-k:] returns the last k items. When k is 0, items[-0:] is the same as items[0:], so it returns the whole list. The practice exercise on the last k items handles this case.

Duplicates are allowed in lists. in answers true when at least one copy exists. remove deletes only the first copy it finds. To remove every copy, use a comprehension, as shown earlier.

Sorting can be done two ways. sorted(items) returns a new sorted list and leaves items as it was. items.sort() changes items in place and returns None. Assigning the result of items.sort() is a common mistake, because the variable then holds None.

Lists of lists are common in real programs. A list of lists can hold rows of a grid, one row per inner list. Reading grid[r][c] walks two lists, so the cost is the cost of the two index operations added together.

Interview-style and real-world uses

Interview questions about lists usually test one of three ideas. The first is choosing the right structure. If an interviewer says "the list is read far more often than it changes," the answer is list, because reads are O(1). If they say "items join and leave at the front constantly," the answer is a deque, not a list with insert(0, ...) in a loop.

The second idea is in-place editing. A question might ask you to remove all occurrences of a value without making a new list. A slice assignment such as items[:] = [...] does this in one pass. A hand-written version walks the list backwards with an index, so that removing an item does not shift an item you have not checked yet. You will write the backwards loop in the practice exercises.

The third idea is cost. Interviewers ask "what is the cost of inserting at the front?" and expect "O(n) for a list, O(1) for a deque, but finding the spot first costs O(n) in both." Your answer should always name both the operation and the position it happens at.

In real programs, list is everywhere: the list of messages in a chat window, the rows returned by a database query, the items in a shopping cart. It is the default because most real work reads and appends more than it inserts in the middle. When you need to know the cost, count how many times the program reads by index and how many times it inserts in the middle. Those two counts usually decide the answer.

Practice

1. Write a program that adds the numbers 1 to 10 to a list with a for loop and prints the list. Then print its length.
2. Read five integers from the keyboard, put them into a list, and print their sum. Type the five numbers on one line, separated by spaces.
3. The list holds [7, 8, 9]. What does del nums[2] do? What does nums.remove(2) do? Which one is the safe way to say "remove the value 2" when the value might be missing?
4. Remove every occurrence of 3 from [3, 1, 3, 3, 2] using a backwards index loop, without using a comprehension. Explain why a forwards loop would skip items.
5. Write a function that inserts a value into an already sorted list so that the list stays sorted. Find the position with a loop, then call insert(index, value).
6. Reverse a list in place in two ways: once with reverse() and once with a loop that swaps the item at i with the item at len(items) - 1 - i. Print the list after each.
7. Write a function that returns a new list with duplicate values removed, keeping the first copy of each value in its original order. Use in on the new list.
8. A program removes items from the front of a list of 100000 items in a loop with pop(0). Explain why this is slow and show how you would rewrite the loop with a deque.
9. Write a function last_k(items, k) that returns the last k items in their original order, without changing items. Handle k larger than the list length, and handle k equal to 0.
10. Write a program that builds a list of 100000 integers by inserting at the front each time, and a deque of 100000 integers built with appendleft. Time each part with time.perf_counter() and print which one is faster. Explain the result in terms of Big-O. Your times will differ from the times on another machine.

Exercise 1. Show the answer: nums = [], then for i in range(1, 11): nums.append(i), then print(nums) and print(len(nums)).

Exercise 2. Show the answer: nums = [int(part) for part in input().split()] followed by print(sum(nums)). The function sum adds the numbers.

Exercise 3. Show the answer: del nums[2] removes the item at position 2, which is the value 9, so the list becomes [7, 8]. nums.remove(2) looks for the value 2. The list has no 2, so Python raises ValueError: list.remove(x): x not in list. To remove the value safely, check first with if 2 in nums: and then call remove(2).

Exercise 4. Show the answer:

nums = [3, 1, 3, 3, 2]
for i in range(len(nums) - 1, -1, -1):
    if nums[i] == 3:
        del nums[i]
print(nums)

The output is [1, 2]. Going backwards means that when you delete index i, every item you have not checked yet is still before i, so it does not move. A forwards loop would move the next item into index i, and then the loop would step past it without checking it.

Exercise 5. Show the answer:

def insert_sorted(sorted_items, value):
    i = 0
    while i < len(sorted_items) and sorted_items[i] < value:
        i += 1
    sorted_items.insert(i, value)

Exercise 6. Show the answer:

a = [1, 2, 3, 4]
a.reverse()
print(a)
 
b = [1, 2, 3, 4]
for i in range(len(b) // 2):
    j = len(b) - 1 - i
    b[i], b[j] = b[j], b[i]
print(b)

Both print [4, 3, 2, 1]. The line b[i], b[j] = b[j], b[i] swaps two items in one statement.

Exercise 7. Show the answer:

def unique(items):
    out = []
    for value in items:
        if value not in out:
            out.append(value)
    return out

This is O(n squared) in the worst case, because in scans the output. A set brings it to O(n), which the fourth lesson of this module covers.

Exercise 8. Show the answer: pop(0) on a list moves every remaining reference one slot to the left, so each call costs O(n), and a loop of n calls costs O(n squared). A deque removes the first item in O(1). Write queue = deque(items) once, then call queue.popleft() in the loop.

Exercise 9. Show the answer:

def last_k(items, k):
    start = max(0, len(items) - k)
    return items[start:]

The function max handles a k larger than the list. The slice items[start:] makes a new list, so the caller gets a list that does not change when items changes. When k is 0, start equals the length, and the slice is empty, which is the correct answer. Writing items[-k:] instead would return the whole list for k equal to 0.

Exercise 10. Show the answer: the list version is much slower. Each insert(0, x) on a list shifts every item, so the total is O(n squared) for 100000 items. The deque version adds one item at its front each time, so its total is O(n). Students who measure should expect the deque to finish first for this pattern. The real times depend on the machine, so print the two times rather than guessing.

What you now know

• A list is an ordered collection with indexes that start at 0. Create it with square brackets, and read items with lst[i].
• A list keeps references in a row of slots. Reads are O(1). Inserts and deletes in the middle are O(n). Appends are O(1) on average.
• A deque from collections adds and removes at both ends in O(1), but reading an item in the middle costs O(n).
• In practice, list is the right default, and deque covers the cases where you would otherwise insert at the front of a list.
• remove(x) deletes by value, and del lst[i] or pop(i) deletes by position.
• A list comprehension builds a new list that keeps only the items that pass a test.
• Python's IndexError message does not name the index or length, so print len(...) next to the index to find the cause.