# Lists & Tuples

## Basic Operations#

Initialising a list: `myList =  * 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
`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:
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 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.