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 deque for 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#

Ascending Order#

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

Descending Order#

# This will print 5,4,3,2. Note that 1 is excluded.
# The last parameter, -1, is the step value which decrements i by -1 in each loop.
for i in range(5, 1, -1):
print(i)

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]

Sorting Lists#

We can use both sort and sorted in Python to sort lists. The only difference is that sorted(list_a) will return a new list that is sorted, while list_a.sort() will modify the original list in-place and will not return anything.

For example, to check if 2 lists have the same elements, we can do something like:

def are_lists_equal(list_a, list_b):
return sorted(list_a) == sorted(list_b)

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.