Lists (data structures)
Martin McBride, 2020-03-13
Tags list stream mutability abstract data type
Categories data structures
You will no doubt be familiar with Python lists. In this section we will look at the abstract data type list, of which the Python list is an example. In the course of doing that, we will learn a few of the properties of Python lists that you might not be aware of.
What is a list
If you have used Python lists, then you most likely already have an idea of what a list is.
A more formal definition of a list is an abstract data type that holds a countable number of values, in a defined order, and where the same value may occur more than once.
This essentially means:
- A list must have a finite number of elements (you can't create an infinitely long list in Python, although you can create infinite lazy streams.
- Each element in the list has an index from 0 to
n - 1, where
nis the length of the list.
- You can have more than one element with the same value. This makes it different from, say, a dictionary where each key must be unique.
Lists can be mutable or immutable:
- A Python
listis a mutable list type.
- A Python
tupleis an immutable list type.
There are two main ways to implement a list:
- As a dynamic array.
- As a linked list.
The standard Python implementation, CPython, uses the first method, dynamic arrays. Other implementations are very likely to use the same method. Linked lists have advantages in certain circumstances, but for general usage dynamic arrays are likely to give better average performance.