# Data structures

## list

list is the most useful collection type. e.g.

``a=[1,2,3]``

list is a mutable type, unlike a string.

### indexing and slicing

``````a[-1]  #the last one

a[:]  #all the elements
a[1:] #from the index 1 to the end
a[1:3] # from index 1, to index 3-1
a[1:-1] # from index 1, to index -1-1``````

### concatenating

``````a=a+['a','b']
a.extend(['a','b'])  # extend() is in-place``````

### create a list

``a=[1,2,3,'a']``

from range, xrange:

``````a=list(range(3))
a=list(xrange(3))
a=list(range(1,3))
a=list(xrange(1,3))``````

from string:

``a=list('abc') #['a','b','c']``

the grammar used below is called "list comprehension" create a list with 100 0's:

``a=[0 for x in xrange(100)]``

create a 10*10 2d list:

``a=[ [0 for y in xrange(10)] for x in xrange(10)]``

create a 3d list:

``a=[ [[0 for z in xrange(10)] for y in xrange(10)] for x in xrange(10)]``

### append/prepend/insert

``    a.append(2**3)  #add 8 to the end``

if len(a)==3, will a=8 do? NO. (it's no like in PHP)

``````a[3:]=   # this will do, however.   or
a[-1:]=
a.insert(3,8)  #

a[:0]=  #prepend an element or a list

append or prepend a list:
* use extend() for prepend;
* splicing for append/prepend.

insert item as a given index:
```python
a.insert(1,5)  #insert 5 at index 1``````

insert a list at an index:

``````a[1:1]=[1,2,3]  #insert at index 1, or
a[1:2]=[1,2,3]``````

### remove by index

``````del a[-1]  # remove the last element
del a[2:2]  # no effect
del a[2:3]   # remove index 2
del a[0:7:2]  #(suppose len(a)=7 )remove the even numbered index
del a[2:4]
del a  #delete the object a; a will become undefined.``````

using del is somewhat equivalent to using the following

``a[2:4]=[]  #remove from index 2 to 3``

### remove by value

``a.remove(2) #remove the first item with value 2. ERROR if 2 not found as a value``

### remove all such items:

``````    while 2 in a:
a.remove(2)``````

using lambda:

``    a=filter(lambda x:x!=2,a)``

### manipulate by value

``````a.count(2) #how many items with value 2
a.index(2) #the first index with value 2.  ERROR if 2 not found as a value``````

change value 2 to 3:

``````i=a.index(2)
a[i]=3``````

### list as a stack

https://docs.python.org/2/tutorial/datastructures.html#using-lists-as-stacks use list as stack. python has pop, but no push.

``````a.append(7)
a.append(8)
a.pop()  #return the poped value;  ERROR if a is empty.
a.pop() ``````

### list as a queue

``````from collections import deque
queue = deque([1,2,3])
queue.append(4)
queue.append(5)
queue.popleft()
queue.popleft()``````

### sort

``a.sort()  #in-place sorting.  ``

Note:

using alphamumeric order: first numbers; then strings. For strings, using ascii to sort. example: [1, 2, 3, 4, 38, '0', '2', '9', '99', 'A', 'b', 'c']

the singature is: `list.sort( cmp=None, key=None, reverse=False)`

``a.sort(reverse=True)  #descending order``

sorted() for non in-place sorting. e.g.

``sorted(a) #return the sorted list. ``

reverse

``````a.reverse()  #in-place
reversed(a)``````

### map filter reduce

3 import functions working with lists:

map, filter, reduce.

filter(function, sequence); signatures are similar for the other two.

``````    filter(lambda x:x%3==0 or x%5==0, range(2, 25))  # retain those that can be divided by 3 or 5.

map(lambda x:x**3, range(1, 11))

reduce(lambda x,y:x+y, range(1, 11))  #reduce returns a single value.
reduce(max, range(1, 11))``````

### list comprehension

``````[(x, y) for x in [1,2,3] for y in [3,1,4] if x != y]
[x for x in a if x >= 0]
[(x, x**2) for x in range(6)] # [(0,0),(1,1),(2,4),..]``````

flatten a 2-d list:

``````vec = [[1,2,3], [4,5,6], [7,8,9]]
[num for elem in vec for num in elem]``````

transpose a 3*3 2-d list:

``````vec = [[1,2,3], [4,5,6], [7,8,9]]
[ [row[i] for row in vec] for i in xrange(3) ]``````

## tuples and sequences

strings,unicode strings, lists, tuples, bytearrays, buffers, and xrange objects are sequence data types. tuple is composed of values seperated by commas(parentheses are optional). Tuples are immutable, but can contain mutable types.

``````t=1,2,3
t=(1,2,3)``````

tuples with 0 or 1 element:

``````t=() #empty tutple
t=1, #tuple with one element, or
t=(1,)``````

tuple unpacking:

``a,b,c=t #suppose t has 3 elements``

zip returns a list of tuples.

## set

A set is composed of unique values.

### create a set

``````s=set() # empty set

s={1,2,3}
s=set(a) #a is a list
list(s) # convert back to list``````

### binary ops are supported on sets:

``````a&b
a|b
a-b
a^b #symmetric difference``````

### set comprehensions:

``{x for x in 'abracadabra' if x not in 'abc'}``

## dictionary

this type is called associate array in other languages(e.g. in PHP).

### create a dictionary

``````d={} #empty dict
d={'a':'apple', 'b':'bush'}
d=dict([('a',1),('b',2)])  #from a list of tuples``````

### other operations:

``````d['a']
d['a']='alias'
'a' in d
d.keys()
d.values()``````

### dict comprehension:

``{x:x**3 for x in range(5)}``

## looping within sequences

### within one sequence

``````for v in a:  # a is a list, or set, ...
print v``````

### to get the index and value altogether

``````for i,v in enumerate(a):
print i, v``````

reversed(), sorted() can be used additionally.

### within two sequences:

``````for i, j in zip(a,b):
print i,j``````

### changing in the course of iterating:

use a copy is recommended, e.g.

``````for x in a[:]:
if x>10:
a.insert(0,10)``````

### looping within a dict:

``````for k, v in d.iteritems():
print k, v``````

## using conditions

in, not in; is, is not

### comparison chaining:

``````3<4==4  #True
3!=4!=5  #True``````

# some tips

how to use docstring? https://docs.python.org/2/tutorial/controlflow.html#documentation-strings