# 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:
self.name = name
self.age = age
def __repr__(self):
>>> 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.