Python: Data Structure - 卖萌的弱渣

Functions on `list`

append(x) Add an item to the end of the list. a[len(a)] = x
extend(L) Extend a list by appending all the items of given list L a[len(a):] = L
insert(index, x) Insert x before a[index]

a.insert(0,x)         # Insert at the begining
a.insert(len(a),x)    # Insert at the end

remove(x) Remove all values x from the list. If there is no value x, there will be an error
pop(index)

Remove the item at the given position index in the list and return it. But you can use pop() to return and remove the last item in the list

clear() Remove all items from the list
index(x) Return the index of value x in the list. There will be an error if no such item.
count(x) Return the nuber of times value x appears in the list
sort() Sort the items of the list in place
reverse() Reverse the items of list in place
copy() Return a copy of the list

>>> a = [66.25, 333, 333, 1, 1234.5]
>>> print(a.count(333), a.count('x'))
2 0

>>> a.insert(2, -1)        # add -1 before a[2]
>>> a.append(333)         # andd 333 in the end
[66.25,333,-1,333,1,1234.5,333]

>>> a.index(333)         # only search once
1
>>> a.remove(333)        # delete once from left
[66.25, -1, 333, 1, 1234.5, 333]

>>> a.reverse()
[333, 1234.5, 1, 333, -1, 66.25]

>>> a.sort()
[-1,1,66.25, 333, 333, 1234.5]

>>> a.pop()              # return and remove the last item
1234.5
>>> a
[-1,1,66.25,333,333]

Every method has return value. insert,remove and sort will return None

Using Lists as Stacks

Use append() and pop() to implement First in first out.

>>> stack = [3,4,5]
>>> stack.append(6)
>>> stack.append(7)
>>> stack
[3,4,5,6,7]
>>> stack.pop()
7
>>> stack
[3,4,5,6]
>>> stack.pop()
6
>>> stack.pop()
5
>>> stack
[3,4]

Using Lists as Queues

To implement First in Last out, use collections.deque

>>> from collections import deque
>>> queue = deque(['Eric", "John", "Michael"])
>>> queue.append("Terry")        # Terry arrives 
>>> queue.append("Graham")       # Graham arrives
>>> queue.popleft()              # Eric left
'Eric'
>>> queue.popleft()              # John left
'John'
>>> queue
deque(['Michael', 'Terry', 'Graham'])

List Comprehensions

You can do

>>> squares = []
>>> for x in range(10):
        squares.append(x**2)

>>> squares
[0,1,4,9,16,25,36,49,64,81]

>>> squares = [x**2 for x in range(10)]

Another Example:

>>> [(x,y) for x in [1,2,3] for y in [3,1,4] if x!=y]
[(1,3, (1,4), (2,3), (2,1), (2,4,) (3,1),(3,4)]

equivalent to

>>> combos = []
>>> for x in [1,2,3]:
        for(y in [3,1,4]:
            if x!=y:
                combs.append((x,y))
>>> combs
[(1,3),(1,4),(2,3),(2,1),(2,4),(3,1),(3,4)]

More Examples:

>>> vec = [-4,-2,0,2,4]
>>> # create a new list with values doubled
>>> [x*2 for x in vec]
[-8,-4,0,4,8]
>>> # filter the list to exclude negative nums
>>> [x for x in vec if x>=0]
[0,2,4]
>>> # call a method on each element
>>> freshfruit =['banana', 'loganberry','passion fruit']
>>> [weapon.strip() for weapon in freshfruit]
['banana','loganberry',passion fruit']
>>> create a 2-tuple, you must have `()`
>>> [(x, x**2) for x in range(6)]
[(0,0),(1,1),(2,4),(3,9),(4,16),(5,25)]
>>> # two 'for'
>>> vec = [[1,2,3],[4,5,6],[7,8,9]]
>>> [num for elem in vec for num in elem]
[1,2,3,4,5,6,7,8,9]

Nested List Comprehension

Implement a 3x4 matrix

>>> matrix = [
        [1,2,3,4],
        [5,6,7,8],
        [9,10,11,12],
    ]

The following will switch the row and column.

>>> [[row[i] for row in matrix] for i in range(4)]
[[1,5,9],[2,6,10],[3,7,11],[4,8,12]]

This code is also equal to

>>> new_matrix = [];
>>> for i in range(4);
        new_matrix.append([row[i] for row in matrix])

>>> new_matrix
[[1,5,9],[2,6,10],[3,7,11],[4,8,12]]

The built-in function zip() can provide the same functionality.

>>> list(zip(*matrix))
[(1,5,9),(2,6,10),(3,7,11),(4,8,12)]

The del statement

Remove an item from a given list by a index.

>>> a = [-1, 1, 66.25, 333, 333, 1234.5]
>>> del a[0]
>>> a
[1, 65.25, 333, 333, 1234.5]      # delete a[2] and a[3]
>>> del a[2:4]
>>> a
[1,66.25, 1234.5]

Delete an entire list

del a
or
del a[:]

Tuples and Sequences

The tuples is always enclosed in parentheses. Nested tuple is correct. The elements in Tuples can not be changed.

>>> t = 12345, 54321, 'hello!'
t
(12345, 54321, 'hello!')

>>> u = t, (1,2,3,4,5)         # nested tuple
>>> u
((12345, 54321, 'hello!'), (1,2,3,4,5))
>>> t[0] = 888         # Wrong !
>>> v = ([1,2,3],[3,2,1])

You can build empty tuple and comma is not considered when you calculate the length of tuple

>>> empty = ()
>>> singlenton = 'hello',
>>> len(empty)
0
>>> len(singleton)
1
>>>

Sets

No duplicate elements
Elements are unordered

To create an empty set, you have to use set(). If you do {}, you will create an empty dictionary.

>>> basket = {'apple', 'orange', 'apple', 'pear', 'banana'}   # {} can be used to create un empty dictionary
>>> print(basket)
{'orange','banana','pear','apple'}

Set support fast membership testing

>>> 'orange' in basket
True
>>> 'haha" in basket
False

Set support -, |, &, ^ operations

>>> a = set('abracadabra')
>>> b = set('alacazam')
>>> a
{'a','r','b','c','d'}
>>> a-b                       # letters in a but not in b
{'r','d','b'}
>>> a | b                     # letters in either a or b
{'a','c','r','d','b','m','z','l'}
>>> a & b                     # letters in both a and b
{'a','c'}
>>> a ^ b                     # letters in a or b but not both
{'r','d','b','m','z','l'}

Dictionaries

Indexed by unique Keys. Key must be immutable type. List cannot be used as key.
Check if a key is in the dictionary by using the in keyword
List all keys by list(d.keys()) or sorted(d.keys())
Each element in dictionary is key:value separated by comma

>>> tel = {'jack':4098, 'sape:4139}
>>> tel['guido'] = 4127                # add a new one element
>>> tel
{'sape':4139, 'guido':4127, 'jack':4098}
>>> tel['jack']
4098
>>> del tel['sape']                    # delete an element
>>> tel['irv'] = 4127
>>> tel
{'guido':4127, 'irv':4127, 'jack':4098}
>>> list(tel.keys())
['irv','guido','jack']
>>> 'guido' in tel
True

dict() can build dictionaries from sequences of key-value pairs:

>>> dict([('sape',4139),('guido',4127),('jack',4098)])
{'sape':4139, 'jack':4098, 'guido':4127}

You can create dictionaries with expressions

>>> {x: x**2 for x in (2,4,6)}
{2:4, 4:16, 6:36}

If your keys are string, you can also do this

>>> dict(sape=4139, guido=4127, jack=4098)
{'sape':4139, 'jack':4098, 'guido':4127}

Looping

For dictionaries, Retrieve the key and value at the same time by using items()

>>> knights = {'gallahad': 'the pure', 'robin': 'the brave'}
>>> for k, v in knights.items();
    print(k,v)
gallahad the pure
robin the brave

For a sequence, the position index and corresponding value can be retrieved at the same time using enumerate() function

>>> for i,v in enumerate(['tic', 'tac', 'toe'])
    print(i,v)
0 tic
1 tac
2 toe

To loop over two or more sequences at the same time, entries can be paired with the zip() function.

>>> questions = ['name', 'quest', 'favorite color']
>>> answers = ['lancelot', 'the holy grail','blue']
>>> for q, a in zip(questions, answers):
        print('What is your {0}? It is {1}.'.format(q,a))
What is your name? It is lancelot.
What is your quest? It is holy grail.
What is your favorite color? It is blue.

To loop over a sequence in reverse, call reversed() function

>>> for i in reversed(range(1,10,2)):
        print(i)
9
7
5
3
1

Sorted() function can loop over a sequence in sorted order and return a new sorted list while leaving source unaltered.

>>> basket = ['apple', 'orange', 'apple', 'pear', 'orange', 'banana']
>>> for f in sorted(set(basket)):
        print(f)
apple
banana
orange
pear

Conditinos

is and is not compare whether two objects are the same.
in and not in check whether a value occur in a sequence.
Comparision can be chained

a < b == c         # a<b && b<c

If you compare two sequence object with same type. It will use lexicographical ordering to compare them. The longer, the larger.

(1,2,3) < (1,2,4)
'ABC' < 'C' < 'Pascal' < 'Python'
(1,2,3,4) < (1,2,4)
(1.0,2.0) == (1.0,2.0,3.0)
(1,2,) < ( 1,2,-1)
(1,2,('aa','ab')) < (1,2,('abc','a'),4)

Functions on list