array(list)
장점
- 순서가 있다.
인덱싱이 된다.
이런 특징을 가지는 이유는 메모리상에 옆에 존재하므로.
단점
- 중간에 하나 지우면 뒤의 것들 다 하나씩 순서 땡겨줘야함.
ㅡ> 굉장히 비싼 operation. - 중간에 삽입하는 것도 그럼.
append는 상관없음.
아주 큰 단점
- resizing
ㅡ> 만약에 array가 저장된 메모리 바로 옆에 뭔가가 이미 저장되어 있었으면, 내가 array 크기를 늘리려 할때 단점이 발생.
ㅡ> 그래서 파이썬의 array는 200개 정도의 cell을 기본으로 지정해주게 되어있음.
ps. C같은 low-level 언어는 메모리 공간을 사용자가 애초에 몇개만 쓰겠다고 지정해주게 됨.
ㅡ> 단점의 해결 = 메모리 공간을 재할당 해야 함.
말만 들어도 굉장히 비쌈.
이런 게 자주 일어나면 굉장히 비효율적.
tuple
특징
- 있는 언어도 있고 없는 언어도 있다.
- list랑 굉장히 비슷.
- 2~5개 사이의 element만 저장할 용도로 많이 사용.
- 간단한 값들을 빨리 표현하고 싶을 때 사용. ex) 좌표
ㅡ> list는 tuple보다 무겁.
ㅡ> 누가봐도 명확한 데이터만 표현해야함. 사실 5개도 많고, 2~3개 정도만 쓸 때 유용.
set
- 면접에서 가장 유용(list와 set의 차이)
- 순서가 없다는 게 list와 가장 큰 차이
- 중복된 값을 허용 안 함.(새로운 값이 중복된 값을 치환)
- 왜 순서가 없냐면 각 값의 hash 값 뽑아내서 그걸 각각 저장해줌.
그럼, 왜 중복이 없냐.
입력값 같으면 hash값 같으므로.
그럼 set에서 각 값마다 hash가 일치하는 메모리에 저장이 된다는데 이게 어떻게 가능...?
ps. set도 누가 만들어 놓은 프로그램. set의 기저도 list임. 그래서 set도 어느정도 size 차면 list처럼 resizing을 함.
메모리가 hardware. 파이썬, list, set은 프로그램.
컴공 박사면 어떻게 hash 충돌을 줄이느냐 이런 걸로 논문 씀.
dictionary
- 어떤 field명에 대해 그 값을 저장하고자 할때 사용.
- set에선 중복된 값이 저장 안되고, dictionary는 중복된 key를 사용 안함.
- 객체는 겉으론 같아보여도, 메모리가 다르기 때문에 같지 않은 것으로 취급.
- key는 set처럼 hash로 저장함.
stack & queue
-
stack : 쌓고 나중거 먼저 빼기.
stack도 array를 기저에 씀. array가 가장 효율적인 자료구조이므로. -
보통 함수에는 호출할 수 있는 stack size가 정해져있음. 그래서 그거 이상으로 호출하면 stackoverflow.
-
브라우저에서 뒤로가기 할 때. 랑 함수호출할 때 사용.
-
queue : 쌓고 먼저거 먼저 빼기.
-
얘도 밑단엔 array를 씀.
logic을 붙여서 먼저 쌓인거 먼저 빼게 한 것. -
queue지만 우선 순위가 높은 애들 순서대로 뽑는 게 priority queue.
-
운영 system에서 많이 씀.
tree
- 그냥 리스트에서 찾는 것보다 tree가 빠름.
- 탐색을 많이 해야 하는 걸 이진 트리로 저장.
ps. big O notation.
O(logN) - 트리의 탐색에 걸리는 시간 표현.
O(N) - array의 탐색에 걸리는 시간.
O(1) - set의 size와 상관없이 특정요소 찾는게 항상 동
일한 시간이 걸림. set는 값의 해당 hash를 가진 메모리를 찾음. 찾아서 있으면 true. 없으면 false.
linked list
- 기존 array의 resizing이나 미리 메모리를 확보하는 문제에서 자유로움.
- ps. head next next value 로 값을 읽어들임.
효율성을 늘린 대신에 메모리를 희생함.
컴공에서는 시간을 희생하거나, 메모리를 희생하거나. 택일.
