리스트

Lists, tuples, sets, dictionaries

1. Loop and Lists

• list는 [e1, e2, …, ek]의 형태로 순서가 유지 되는 mutable, iterable, sequence 자료형

  • linearly ordered + randomly accessed by index + useful with for-loop fruits = [‘apples’, ‘oranges’, ‘apricots] change = [1, ‘monkey’, 2, …] #list of different types plants = [‘pinetree’, fruits, ‘bamboo’]#nested list

• lists(tuples) are referencial structres

• for element in list 형태로 매우 유용하게 사용

• making a list elements = [] for k in range(6): elements.append(k) a = [k*k for k in range(10) if k % 2]# odds in [0, 10) genereted by list comprehension

  1. a = range(1, 5) #range(i, j) -> [i, j)
  2. a = range(1, 10, 2) #range(start, end, stop)
  3. a = range(10, 2) #빈 range
  4. list comprehension: [expr for value in iterable if condition]

• range vs list

  • a = range(5)
  • type(a) # type은 class range
  • b = [0, 1, 2, 3, 4]
  • type(b) #b의 type은 class list
  • a == b #False
  • c = list(a)
  • b == c #true

• membership

  1. x in s: True if x is in s, else False
  2. x not in s: True if x is not in s, else False

• updating list

  1. fruits[1] = “pears”

• inserting a new element

  1. fruits.append(“banana”) #가장 뒤에 삽입
  2. fruits.insert(2, “banana) #fruits[2 : ]은 오른쪽으로 한칸씩 이동 후, fruits[2] = “banana
  3. 이론적으로 개수 제한 없이 append 가능 (dynamic-array)

• deleting elements of lists

  1. del fruits[1] or fruits.remove(“pear”)
  2. element를 지우면 그 뒷 원소들은 한 칸씩 왼쪽으로 채워짐

• concatenating lists

  1. a = b + c
  2. opearator overloading 이라 불림

• repetition

  1. s _ 3 or 3 _ s #repeating 3 times
  2. data = [0] * 8 #data = [0, 0, 0, 0, 0, 0, 0, 0]

• unpacking

1. ap, or, ba = fruits #fruits의 element 수와 같은 수의 배열로 unpack 해야함.
2. a, b, c, d = range(7, 11)
3. q, r = divmod(a, b)
4. for x, y in [(1, 2), (3, 4), (5, 6)]

• packing: dual of unpacking
  1. data = 2, 4, 8, 6
  2. return a // b, a % b

• simultaneous assignments:

  1. x, y, z = 1, 2, 3 #1. packed as (1, 2, 3) 2. unpacked into x, y, z
  2. x, y = y, x #swap x, y

• others

  1. s.append(x), s.pop() #same as push, pop of stack
  2. s.pop(0) #same as dequeue of a queue
  3. len(s), min(s), max(s)
  4. s.index(x) #index of the first occurrence of x in s
  5. s.count(x) #total number of occurrences of x in s
  6. s.sort(), s.sort(key=int) #sort the items in s, so no return value
  7. ss = sorted(s) # s is not changed, return a sorted copy

• 시간복잡도 efficiency of operations of lists(and tupes)

  1. len(data): O(1)
  2. data[j], data[j] = x: O(1)
  3. data.count(x): O(n)
  4. data.index(x): O(k+1) #k는 x의 index
  5. x in data: O(k+1)
  6. data1 == (!=, >=, …) data2: O(k+1) k는 왼쪽 index
  7. data[j : k]: O(k - j + 1)
  8. data1 + data2: O(n1 + n2)
  9. c*data: O(cn)
  10. data.append(x): O(1) #평균적으로
  11. data.insert(k, value): O(n - k + 1) #평균적으로
  12. data.pop(): O(1) #평균적으로
  13. del data[k], data.remove(value): O(n-k), O(n) #평균적으로
  14. data.sort() O(nlogn)
• more
  1. while 루프(same control flow as in c/c++)
  2. Strings: immutable data type
     • 앞 뒤의 공백 제거 .strip()
     • 모든 공백제거 .replace(‘ ‘, ‘’)
     • whitespace 제거 ‘‘.join(.split())