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 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.
  • 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.

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


Popular tags

2d arrays abstract data type alignment and animation arc array arrays bezier curve built-in function callable object circle classes close closure cmyk colour comparison operator comprehension context context manager conversion creational pattern data types design pattern device space dictionary drawing duck typing efficiency else encryption enumerate fill filter font font style for loop function function composition function plot functools game development generativepy tutorial generator geometry gif gradient greyscale higher order function hsl html image image processing imagesurface immutable object index inner function input installing iter iterable iterator itertools l system lambda function len line linspace list list comprehension logical operator lru_cache magic method mandelbrot mandelbrot set map monad mutability named parameter numeric python numpy object open operator optional parameter or partial application path polygon positional parameter print pure function pycairo radial gradient range recipes rectangle recursion reduce rgb rotation scaling sector segment sequence singleton slice slicing sound spirograph sprite square str stream string stroke subpath symmetric encryption template text text metrics tinkerbell fractal transform translation transparency tuple turtle unpacking user space vectorisation webserver website while loop zip