배열

파이썬은 리스트를 사용해서 구현함

벡터

벡터는 잘 안씀

연결리스트

삽입/삭제 : O(1)
기본적으로 파이썬에는 연결리스트가 없어서 필요하면 직접 구현해야함
특징에는 특정 노드로 가기위해서는 바로 직전에 연결된 노드로 먼저 가야한다
그 특정 노드가 어디에 있는지는 연결된 노드들만 알고있기 떄문이다

스택 (Stack)

파이썬은 리스트로 구현함
삽입/삭제 : O(1)

s = []
s.append(123) //append는 리스트의 뒤에부터 값을 넣어줌
s.append(456)
s.append(789)
while len(s) >0:
    print(s[-1]) // 리스트에 -1 인덱스는 맨 뒤를 의미함
    s.pop(-1)    // 그냥 s.pop()이랑 같음

큐 (Queue)

삽입/삭제 : O(1)
원래 파이썬에 from queue import Queue가 있긴한데
thread-safe (멀티쓰레딩 프로그래밍 시 필요)기능이 있어서 속도가 좀 느림
따라서 알고리즘 문제를 풀때는 멀티쓰레드를 고려하지 않아도 되기때문에
collections에 있는 deque을 사용함
deque은 double-ended-queue 임
그냥 queue랑 같은건데 앞뒤로 다 넣을 수 있는 queue라고 보면 됨

appendleft하면 왼쪽에서 넣고 그냥 append한면 뒤(오른쪽)에서 넣음

from collections import deque

q= deque()
q.append(123)
q.append(456)
q.append(789)
while len(s) > 0:
    printf(q.popleft())

우선순위 큐 (Priority Queue)

먼저 들어오면 먼저 나가는 큐와 다르게 우선순위큐는 우선순위가 높은 데이터먼저 나가도록 한다
완전 이진트리의 종류의 하나인 heap 을 기반으로함
파이썬은 min-heap이므로 최상위 노드(root node)가 가장 작은 값이 위치하게됨

import heapq as hq
pq = []
hq.heappush(pq,6)
hq.heappop(pq)

맵 MAP (Dicionary)

key, value 형식을 저장하기 적합한 자료구조는 MAP이다
key는 중복x / value는 중복가능

• c++은 map이 red-black tree도 되어있어 삽입/삭제가 O(logN)인 반면
  파이썬은 map이 hash로 되어있어 삽입/삭제가 O(1)이다
  y=f(x)와 같은 느낌이라 한 번에 찾아갈 수가 있는것

파이썬 for문정리