Lists, Stacks, and Queues

Add items to a list

A list grows in three different ways, and picking the wrong one is a classic first-week bug: the value does arrive, but in the wrong shape or the wrong place. Decide first what you are adding — one value, the whole contents of another collection, or a value that must land at a known position.

The difference between the first two is how the argument is read. append() treats it as a single object; extend() walks through it and adds each item it yields.

plan = ['wash']
plan.append(['dry', 'fold'])   # ['wash', ['dry', 'fold']] -> one nested item
plan = ['wash']
plan.extend(['dry', 'fold'])   # ['wash', 'dry', 'fold']   -> two separate items
plan.insert(0, 'sort')         # ['sort', 'wash', 'dry', 'fold']

insert() is defined by the element it pushes aside: the new value goes before the element that currently sits at the index you name. So insert(0, value) puts the value at the front of the list, and inserting at the length of the list is the long way of writing append(value).

Remove items by value or by position

Removal splits along the same line as addition: do you know the value you want gone, or its position?

Two details decide most real choices. remove(value) deletes the first equal item and leaves later matches in place, and pop(index) removes and returns the item at the given position — it is the only call here that hands the removed value back.

names = ['ana', 'bruno', 'ana']
names.remove('ana')   # ['bruno', 'ana'] -> only the first match went
last = names.pop()    # last == 'ana', names == ['bruno']
names.pop(7)          # IndexError: the index is outside the range
names.clear()         # []

Without an index, pop() removes and returns the last item; that default is what makes it feel like "take the newest one off". Both remove() and pop() fail loudly rather than quietly: a missing value raises ValueError, and an empty list or an out-of-range index raises IndexError.

Ask the list a question, then reorder it

Before changing a list it often pays to ask it something. Two methods answer without touching the contents.

The limited search is the subtle one: narrowing the window changes where Python looks, not how it counts. A match found in a later window still reports its position in the whole list.

Three more methods change or duplicate the list itself. sort() orders a list in place, while reverse() reverses it in place, and copy() returns a shallow copy of the list.

Their return value is the trap. List methods that only mutate the list, such as insert(), remove() and sort(), return None.

names = ['zoe', 'ana']
result = names.sort()   # names == ['ana', 'zoe'], result is None

So result = names.sort() sorts names in place and leaves result as None. Read the list itself after sorting it; when a separate sorted list is what you need, keep the original untouched and build a new one instead.

Last-in, first-out work

Some jobs must reach the newest item first. An undo history is the everyday case: the action you want to reverse is the one you just performed. That behavior has a name — a stack retrieves the last element added before earlier elements.

A plain list is enough, as long as both operations stay at the same end:

• Use append() to add an item to the top of a list-backed stack.
• Use pop() without an index to retrieve the top item.

history = []
history.append('type')     # ['type']
history.append('delete')   # ['type', 'delete']
history.pop()              # 'delete' -> the newest action comes back first

Keeping insertion and removal at the same end is the whole trick, and it is also why the pairing is fast: nothing else in the list has to move. Mixing ends breaks the order — adding at the front and popping from the back would return the oldest action first, which is the opposite of an undo.

First-in, first-out work

Now flip the requirement. A ticket line, a print spooler and an arrivals log all need the opposite rule: a queue retrieves the first element added before later elements.

A list can imitate a queue, but it is the wrong shape for the job. Appending to or popping from the end of a list is fast, but inserting or popping at its beginning is slow, because all the remaining elements have to shift one position.

For a queue, collections.deque provides fast appends and pops at both ends. A deque queue adds arrivals with append() and retrieves the earliest arrival with popleft().

from collections import deque
line = deque(['ana', 'bruno'])
line.append('carla')   # deque(['ana', 'bruno', 'carla'])
line.popleft()         # 'ana' -> the earliest arrival leaves first

Same two verbs as the stack at one end, a different verb at the other — and that is the entire difference between serving the newest item and serving the oldest.

Delete without retrieving

Sometimes the removed value is of no interest at all — a row is wrong, a range of records is obsolete, a name is finished with. That is the del statement, and it works differently from every method above.

• The del statement removes a list item by index rather than by value.
• Unlike pop(), del does not return the removed value.
• del can remove a slice of the list, or clear the whole list through a full slice.
• del can also delete a variable name, and referring to that name is then an error until another value is assigned to it.

records = [0, 1, 2, 3, 4, 5, 6]
del records[2]      # [0, 1, 3, 4, 5, 6]      -> by index, nothing returned
del records[2:5]    # [0, 1, 6]               -> a whole slice at once
del records[:]      # []                      -> the name still exists
del records         # the name itself is gone
records             # NameError until `records` is assigned again

The distinctions are worth stating precisely, because three of them look alike. del values[2] removes a position and produces nothing; values.pop(2) removes the same position but returns the item; values.remove(2) ignores positions and hunts for the value 2. And a slice target such as del records[2:5] clears positions 2, 3 and 4 in one statement while the name records stays usable.

Key takeaways

• One item or many: append() adds a single item to the end, while extend() appends every item from an iterable.
• Value or position: remove() deletes the first equal item, pop(index) removes and returns the item at a position, and index-free pop() takes the last one.
• In-place methods return None: sort() and reverse() reorder the list itself, so read the list rather than the result.
• Same end for a stack: append() plus index-free pop() gives last-in, first-out behavior.
• Both ends for a queue: collections.deque with append() and popleft() gives first-in, first-out behavior without shifting elements.
• del when the value is not needed: it removes by index or slice, returns nothing, and applied to a bare name it removes the name itself.