Lists

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:

• Array lists
• Linked lists

See also

• Abstract data types
• Arrays
• Array lists
• Linked lists
• Static vs dynamic data structures
• Queues
• List based queues
• Circular queues