# Lists (data structures)

By 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 n is 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 list is a mutable list type.
• A Python tuple is an immutable list type.

## List implementation

There are two main ways to implement a list:

• As a dynamic array.

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.

If you found this article useful, you might be interested in the book NumPy Recipes or other books by the same author.