Lists

By Martin McBride, 2018-05-04
Tags: list abstract data type
Categories: data structures

A list is an abstract data type consisting of an ordered collection of items, called elements. The elements of a list might be numbers, strings or other data types. The elements of a list do not have to be unique (the same element can appear more than once in a list).

The elements in a list can be accessed by their index. In most languages the first element has an index of 0, the second element has an index 1, the third element has an index 2, and so on.

A list will typically have functions that allow you to add and remove elements from the list, count the number of elements, and search for particular values. It may have additional functions for joining two lists, sorting the elements, and other functions, depending on the programming language you are using

Lists vs arrays

Lists are similar to arrays. They both contain an ordered collection of elements. The main differences between lists and arrays are:

  • The size of an array is normally fixed when it is created. A list can change size as you add or remove elements.
  • Lists often have efficient functions for certain operations such as inserting elements or joining two lists into one.
  • The elements of an array are usually all the same type. In some languages, lists can contain a mix of different types of elements.

Different programming languages use lists in slightly different ways. This section gives an overview of the sort of things that are possible with lists in many popular languages.

Creating lists

You can create a list from a set of items, in a similar way to an array. In pseudocode:

LIST k = [2, 4, 6, 8]

You can also create an empty list. This is useful because you can add elements later.

LIST e = []

Accessing elements

You can read, modify and loop through elements in a list, in the same way as for an [[arrays|array]].

Adding and removing elements

You can insert elements into a list, eg this will insert value 10 at position 2:

k.INSERT(10, 2)

k now holds [2, 4, 10, 6, 8]. It has automatically increased in length from 4 to 5, and the elements are shifted up to make room for the new value.

You can remove elements into a list, eg this will remove the value at position 3:

k.DELETE(3)

k now holds [2, 4, 10, 8]. It has automatically increased in length from 5 to 4.

You can join two lists, for example:

k = k + [100, 200, 300]

k now holds [2, 4, 10, 8, 100, 200, 300], as the extra value have been added to the end of the existing list.

For a real example of lists, see the section on Python lists.

How lists work

How do lists work? Lists can be implemented in several ways, two common ones are:

See also

Sign up to the Creative Coding Newletter

Join my newsletter to receive occasional emails when new content is added, using the form below:

Popular tags

555 timer abstract data type abstraction addition algorithm and gate array ascii ascii85 base32 base64 battery binary binary encoding binary search bit block cipher block padding byte canvas colour coming soon computer music condition cryptographic attacks cryptography decomposition decryption deduplication dictionary attack encryption file server flash memory hard drive hashing hexadecimal hmac html image insertion sort ip address key derivation lamp linear search list mac mac address mesh network message authentication code music nand gate network storage none nor gate not gate op-amp or gate pixel private key python quantisation queue raid ram relational operator resources rgb rom search sort sound synthesis ssd star network supercollider svg switch symmetric encryption truth table turtle graphics yenc