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.


Tag cloud

2d arrays abstract data type alignment and array arrays bezier curve built-in function close closure colour comparison operator comprehension context conversion data types design pattern device space dictionary duck typing efficiency encryption enumerate filter font font style for loop function function plot functools generator gif gradient html image processing imagesurface immutable object index input installing iter iterator itertools lambda function len linspace list list comprehension logical operator lru_cache mandelbrot map monad mutability named parameter numeric python numpy object open operator optional parameter or path positional parameter print pure function radial gradient range recursion reduce rotation scaling sequence slice slicing sound spirograph str stream string subpath symmetric encryption template text text metrics transform translation transparency tuple unpacking user space vectorisation webserver website while loop zip

Copyright (c) Axlesoft Ltd 2020