List methods - Python

List objects provide several methods, as shown in Table 4-3. Nonmutating methods return a result without altering the object to which they apply, while mutating methods may alter the object to which they apply. Many of the mutating methods behave like assignments to appropriate slices of the list. In Table 4-3, L  indicates any list object, i any valid index in L , s  any iterable, and x  any object.

Table 4-3. List object methods

All mutating methods of list objects, except pop , return None .

Sorting a list

A list's method sort causes the list to be sorted in-place (its items are reordered to place them in increasing order) in a way that is guaranteed to be stable (elements that compare equal are not exchanged). In practice, sort is extremely fast, often preternaturally fast, as it can exploit any order or reverse order that may be present in any sublist (the advanced algorithm sort uses, known as timsort to honor its developer, Tim Peters, is technically a "non-recursive adaptive stable natural mergesort/binary insertion sort hybrid").

In Python 2.3, a lists sort method takes one optional argument. If present, the argument must be a function that, when called with any two list items as
arguments, returns -1, 0, or 1, depending on whether the first item is to be considered less than, equal to, or greater than the second item for sorting purposes. Passing the argument slows down the sort, although it makes it easy to sort small lists in flexible ways. The decorate-sort-undecorate idiom, covered in "Searching and sorting" on page 485 is faster, at least as flexible, and often less error-prone than passing an argument to sort.

In Python 2.4, the sort method takes three optional arguments, which may be passed with either positional or named-argument syntax. Argument cmp  plays just the same role as the only (unnamed) optional argument in Python 2.3. Argument key , if not None, must be a function that can be called with any list item as its only argument. In this case, to compare any two items x  and y , Python uses cmp(key(x),key(y)) rather than cmp(x,y) (in practice, this is implemented in the same way as the decorate-sort-undecorate idiom presented in "Searching and sorting" on page 485, and can be even faster). Argument reverse , if True, causes the result of each comparison to be reversed; this is not the same thing as reversing L  after sorting because the sort is stable (elements that compare equal are never exchanged) whether argument reverse  is true or false.

Python 2.4 also provides a new built-in function sorted (covered in sorted on page 167) to produce a sorted list from any input iterable. sorted accepts the same input arguments as a lists method sort. Moreover, Python 2.4 adds to module operator (covered in "The operator Module" on page 368) two new higher-order functions, attrgetter and itemgetter, which produce functions particularly suitable for the key= optional argument of lists' method sort and the new built-in function sorted. In Python 2.5, an identical key=  optional argument has also been added to built-in functions min and max, and to functions nsmallest and nlargest in standard library module heapq, covered in "The heapq Module" on page 177.