---
title: Data Structure
tags: python, data structure
---

[TOC]

## Inbuilt Data Structure
### List

> List is a mutable object.

> List is like one dimension array, more like vector in C/C++

#### 1. List Functions
- `list.append(elem)`
- Append elem to the tail of list
- `list.extend(iterable)`
- Extend the iterable and append all elems of it to the list
- EX: `[1,2].extend( (4,5) ) --> [1,2,4,5]`
- `list.insert(idx, elem)`
- Insert the elem to the idx
- EX: `[1,3,4,5].insert(1,2) --> [1,2,3,4,5]`
- `list.remove(elem)`
- Remove the **first** elem in the list
- Raise ValueError if elem is not in the list
- EX: `[1,2,1].remove(1) --> [2,1]`
- `list.pop([idx])`
- Remove the idx-th elem
- Remove the last elem if no idx
- `list.clear()`
- Clear all elems from the list
- Same as `del list[:]`
- `list.index(elem, [start [, end]])`
- Return the idx of the **first** elem
- Raise ValueError if elem is not in the list
- `list.sort(key=None, reverse=False)`
- Sort the list by key
- In-place Sort
- `list.copy()`
- Return the copied list

# Sort Example

# Initialize var
a = [9, 4, 7, 1]
a.sort()
## a = [1,4,7,9]

# Initialize var
b = [ (1, 'FC'), (-9, 'XY'), (4, 'KC'), (11, 'BZ') ]

# sort by default
# Try & Test & Think, What is default
b.sort()
## b = [(-9, 'XY'), (1, 'FC'), (4, 'KC'), (11, 'BZ')]

# sorted by 'word'
b.sort(key=lambda x : x[1])
## b = [(11, 'BZ'), (1, 'FC'), (4, 'KC'), (-9, 'XY')]

# sorted by the second character of the 'word'
b.sort(key=lambda x : x[1][1])
## b = [(1, 'FC'), (4, 'KC'), (-9, 'XY'), (11, 'BZ')] 

# Four ways of copy

# Initilize var
a = [1,2,3]

# Copy
# Bad Way
b = []
for x in a:
    b.append(x) or b.insert(len(b), x)
# Better Way
b = a.copy()        # Use list copy function
b = [] + a          # Use list concatenation
b = [x for x in a]  # Use list comprehension


# Try & Test & Think
# Why don't we simply use
b = a

#### 2. List Slicing
> List 可以一次取出不只一個元素，用的就是 Slicing

##### Syntax

list[index1 : index2] #從index1取到index2(不包含index2)

##### Example

x = [1, 2, 3, 4]
x[0:2]  # [1, 2]
x[1:-1] # [2, 3], 1和倒數第一個之間的元素
x[2:0]  # []    , 若第一個索引的位置在第二個索引的位置之前
x[ :2]  # [1, 2], 從開頭開始切
x[2: ]  # [3, 4], 從2開始切到尾
x[ : ]  # [1,2,3,4], 這邊是不一樣的list只是切出所有元素

#### 3. List Comprehension
> 這招必學，學會程式碼可以非常簡短!!

##### Basic Type

list_var = [ x for x in iterable ]

a = [1, 3, 5]
b = [x for x in a]
## b = [1, 3, 5]

apple = [c for c in 'apple']
## apple = ['a', 'p', 'p', 'l', 'e']

##### With Condition

odd_num = [n**2 for n in range(10) if n % 2]
## odd_num = [1, 9, 25, 49, 81]

# Equal to
odd_num = []
for n in range(10):
    if n % 2:
        odd_num.append(n**2)

# Nested If
nums = [n for n in range(100) if n % 2 == 0 if n % 5 == 0]
## nums = [0, 10, 20, 30, 40, 50, 60, 70, 80, 90]

# Equal to
nums = []
for n in range(100):
    if n % 2 == 0:
        if n % 5 == 0:
            nums.append(n)

##### With Nested Loop

nums = [ x*y for x in [1,2,3] for y in [10,20,30] ]
## nums = [10, 20, 30, 20, 40, 60, 30, 60, 90] 

# Equal to what?
# Try & Test

#### 4. List Common Usage

# 1. Transform input to int
nums = list(map(int, input('Input Numbers: ').split(' ')))

# 2. Access elems dirtectly, not access by index
for elem in aList:
    pass

# 3. Get list size
size = len(aList)

# 4. Delete element in list
aList = ['a', 'b', 'c', 3, 4, 5]
del aList[1]     # aList == ['a', 'c', 3, 4, 5]
del aList[ :2]   # aList == [3, 4, 5]

#### 5. List Common Error

aList = list(1, 2, 3)
## Raise TypeError

# Create a list just simply use
aList = [1, 2, 3]

# list(iterable) correct usage
aList = list( (1, 2, 3) )
aList = list( range(1,4) )

### Tuple
> 1. Tuple is a immutable object
> 2. Common usage is to store value
> 3. Can't insert value to the tuple and remove value from the tuple

### Dictionary
> 1. 使用key-value的方式儲存資料
> 2. 如同C++ hash map
> 3. key-value可以為任意型別

#### 1. Dictionary Function
- `dict(mapping)`:
- Return the dict of mapping
- EX:`dict([('one', 1) ,('two', 2)]) --> {'one': 1, 'two': 2}`
- `dict(**kwargs)`:
- EX:`dict(k1='A', k2='B') --> {'k1': 'A', 'k2': 'B'}`
- `[]`:
- Add the value to the key
- EX: `dict_obj[key] = value`
- Get the value of the key
- EX: `var = dict_obj[key]`
- If no key, raise KeyError
- `dict.update(**kwargs or dict_obj)`
- Add the value to the original dict_obj
- `dict.clear()`
- Remove all elems in the dict
- `dict.copy()`
- Return the copy of the dict
- `dict.get(key, default=None)`
- Return the value of the key
- If no key, return default
- EX:`dict.get(fun, lambda:print('no fun'))()`
- `dict.setdefault(key, default=None)`
- If the key set, then return the value of key
- If no key, then set *default* to key and return *default*
- If *default* not set, then set None to *default*
- `dict.keys()`
- Return a list of the key in dict
- `dict.values()`
- Return a list of the value in dict
- `dict.items()`
- Return a list of the key-value pair in dict
- `dict.pop(key, [default])`
- Return the value of the key, and pop the key from the dict
- If key isn't exist, return default
- If no default , raise KeyError
- `dict.__contain__(key)`
- Return True if key in the dict
- EX:`True if key in dict else False`

#### 2. Dictionary Example

# dict example with sorted and lambda
dic = {'Mary' : 50, 'Bob': 30, 'Cindy' : 80, 'John' : 100, 'Can' : 10}

# Sort by key
sort_by_key = sorted(dic.items(), key = lambda x:x[0])
## sort_by_key =
## [('Bob', 30), ('Can', 10), ('Cindy', 80), ('John', 100), ('Mary', 50)]

# Sort by value
sort_by_val = sorted(dic.items(), key = lambda x:x[1])
## sort_by_val =
## [('Can', 10), ('Bob', 30), ('Mary', 50), ('Cindy', 80), ('John', 100)]


# Sort with the second word of name and reverse
sort_ch = sorted(dic.items(), key = lambda x:x[0][1], reverse = True)
## sort_ch =
## [('Bob', 30), ('John', 100), ('Cindy', 80), ('Mary', 50), ('Can', 10)]

3. Dictionary Compresion
> Syntax: { key : value for ... in ... if ... }

Example

squre = { i : i*i for i in range(N) }