Lists & Tuples

Basic Operations#

Initialising a list: myList = [0] * 6

Accessing last element in a list: myList[-1]

Operation NameOperatorExplanation
indexing[ ]Access an element of a sequence
concatenation+Combine sequences together
repetition*Concatenate a repeated number of times
membershipinAsk whether an item is in a sequence
lengthlenAsk the number of items in the sequence
slicing[ : ]Extract a part of a sequence

Other Operations Useful for Data Structures#

Note: Some of the methods mutate the original list, whereas other return a modified new list

Operation NameOperatorExplanation
appendalist.append(item)Adds a new item to the end of a list
insertalist.insert(i,item)Inserts an item at the ith position in a list
popalist.pop()Removes and returns the last item in a list
popalist.pop(i)Removes and returns the ith item in a list
sortalist.sort()Modifies a list to be sorted
reversealist.reverse()Modifies a list to be in reverse order
deldel alist[i]Deletes the item in the ith position
indexalist.index(item)Returns the index of the first occurrence of item
countalist.count(item)Returns the number of occurrences of item
removealist.remove(item)Removes the first occurrence of item

Sorting Lists#

# in-place, stable sort
list.sort(key=None, reverse=False)

key is the function that serves as the key for sorting.

>>> class Student:
def __init__(self, name, grade, age):
self.name = name
self.grade = grade
self.age = age
def __repr__(self):
return repr((self.name, self.grade, self.age))
def weighted_grade(self):
return 'CBA'.index(self.grade) / float(self.age)
>>> student_objects = [
Student('john', 'A', 15),
Student('jane', 'B', 12),
Student('dave', 'B', 10),
]
>>> sorted(student_objects, key=lambda student: student.age) # sort by age, returns new list
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]
>>> student_objects.sort(key=lambda student: student.age) # in-place sort on original list

Source: https://wiki.python.org/moin/HowTo/Sorting

When set to True, reverse sorts the list in a descending manner.

We can also use sorted which performs stable sort.

# Note: This is stable
# returns a new list
sorted_list = sorted(alist)

Time complexity of the sort() or sorted() methods is O(nlog(n)).

Using Lists as Stacks (LIFO)#

To add an item to the top of the stack, use append(). To retrieve an item from the top of the stack, use pop()without an explicit index.

- Python 3 Documentation

Using Lists as Queues (FIFO)#

We can use collections.deque to have fast appends, and pops from both ends.

>>> from collections import deque
>>> queue = deque(["Eric", "John", "Michael"])
>>> queue.append("Terry") # Terry arrives
>>> queue.append("Graham") # Graham arrives
>>> queue.popleft() # The first to arrive now leaves
'Eric'
>>> queue.popleft() # The second to arrive now leaves
'John'
>>> queue # Remaining queue in order of arrival
deque(['Michael', 'Terry', 'Graham'])

Iterating Lists#

for i in range(0, len(arr)):
arr[i] = arr[i] * 2

Reversing a List#

a = [1,2,3]
print(a[::-1]) # prints [3,2,1]
print(reversed(a)) # returns an iterable
print(list(reversed(a))) # prints [3,2,1]

Time Complexity of Operations#

OperationBig-O Efficiency
index []O(1)
index assignmentO(1)
appendO(1)
pop()O(1)
pop(i)O(n)
insert(i,item)O(n)
del operatorO(n)
iterationO(n)
contains (in)O(n)
get slice [x:y]O(k)
del sliceO(n)
set sliceO(n+k)
reverseO(n)
concatenateO(k)
sortO(n log n)
multiplyO(nk)

List Comprehension#

List comprehension allows us to create lists/sets/tuples/vectors easily.

Example:

a_list = [x for x in range(10)]
list_2 = [x * x for x in a_list if x % 2 == 0]
# Nesting
statement = 'Hello world! How are you?'.split()
list_3 = [[word.upper(), word.lower(), len(word)] for word in statement]
print(list_3)
'''
Output:
[['HELLO', 'hello', 5], ['WORLD!', 'world!', 6], ['HOW', 'how', 3], ['ARE', 'are', 3], ['YOU?', 'you?', 4]]
'''

Reference: http://www.secnetix.de/olli/Python/list_comprehensions.hawk

Creating a 2D Array#

# to create [[0, 0], [0, 0], [0, 0]]
arr = [[0 for x in range(2)] for x in range(3)]

Tuples#

Tuples are similar to lists, but tuples are immutable.

Example declaration: myTuple = (4.5, True).

Other operations are similar to lists.