List Built-in Type (Python)

One of Python's most useful built-in types is the List. Ironically, it does not provide the functionality of the list (ADT). Instead it provides array (ADT), stack, and queue functionality along with a few other helpful methods. Internally, it is implemented as a dynamic array^[1].

Array Functionality

Create an array of fixed size:

1
2
3

>>>foo = [None,] * 5 # creates a list of length 5 whose elements are all initialized to None
>>>print(foo)
[None, None, None, None, None]

Set a value at an index:

1
2
3

>>>foo[2] = 'bar'
>>>print(foo)
[None, None, 'bar', None, None]

Get a value at an index:
1
2
>>>print(foo[2])
bar

Stack Functionality

The left-most item in a List is the bottom of the stack. The right-most item in a List is the top of the stack.

Push items:

>>>animals = [] # creates an empty list
>>>print(animals)
[]
>>>animals.append('elephant') # use append as push
>>>animals.append('giraffe')
>>>animals.append('lion')
>>>print(animals)
['elephant', 'giraffe', 'lion']

Pop items:

>>>animal = animals.pop() # pop the most recently added animal
>>>print(animal)
lion
>>>print(animals)
['elephant', 'giraffe']

Queue Functionality

Note: although this functionality is provided by List, popping index 0 is an O(n) operation. This is because the implementation is a dynamic array, so removing the first item in the array means all the remaining items must be moved back one index. Python's collections module provides a deque type that is more efficient for this.

The left-most item in the List is the front of the queue. The right-most item in the List is the back of the queue.

Enqueue items:

>>>animals = [] # creates an empty list
>>>print(animals)
[]
>>>animals.append('elephant')
>>>animals.append('giraffe')
>>>animals.append('lion')
>>>print(animals)
['elephant', 'giraffe', 'lion']

Dequeue items:

>>>animal = animals.pop(0) # get the animal at the front of the queue
>>>print(animal)
elephant
>>>print(animals)
['giraffe', 'lion']

References

Python Software Foundation, . listobject.c. Retrieved September 8, 2016, from https://hg.python.org/cpython/file/tip/Objects/listobject.c

Contents