Lists & Tuples

Basic Operations#

Initialising a list: myList = [0] * 6

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

Operation Name	Operator	Explanation
indexing	[ ]	Access an element of a sequence
concatenation	+	Combine sequences together
repetition	*	Concatenate a repeated number of times
membership	in	Ask whether an item is in a sequence
length	len	Ask 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 Name	Operator	Explanation
`append`	`alist.append(item)`	Adds a new item to the end of a list
`insert`	`alist.insert(i,item)`	Inserts an item at the ith position in a list
`pop`	`alist.pop()`	Removes and returns the last item in a list
`pop`	`alist.pop(i)`	Removes and returns the ith item in a list
`sort`	`alist.sort()`	Modifies a list to be sorted
`reverse`	`alist.reverse()`	Modifies a list to be in reverse order
`del`	`del alist[i]`	Deletes the item in the ith position
`index`	`alist.index(item)`	Returns the index of the first occurrence of `item`
`count`	`alist.count(item)`	Returns the number of occurrences of `item`
`remove`	`alist.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#

Operation	Big-O Efficiency
index []	`O(1)`
index assignment	`O(1)`
append	`O(1)`
pop()	`O(1)`
pop(i)	`O(n)`
insert(i,item)	`O(n)`
del operator	`O(n)`
iteration	`O(n)`
contains (in)	`O(n)`
get slice [x:y]	`O(k)`
del slice	`O(n)`
set slice	`O(n+k)`
reverse	`O(n)`
concatenate	`O(k)`
sort	`O(n log n)`
multiply	`O(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.