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.

Prev

Popular tags

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