파이썬 자료구조 컨닝페이퍼

각 자료구조들 파이썬의 무엇을 이용해서 구현하는지에 대한 간단한 컨닝페이퍼다.

각 자료구조의 기본 함수들의 시간복잡도도 정리했다(어디서 가져왔다)

배열

그냥 당연히 List 써라 파이썬 공부하면 알꺼아냐

출처:https://daimhada.tistory.com/56

딕셔너리

dictionary 쓰면 될것이다.

출처:https://daimhada.tistory.com/56

링크드 리스트

파이썬은 링크드 리스트 그냥 쓰면된다

리스트 자체가 배열의 단점 (크기 고정) 이런거 다 해결되어있다 -> 배열 이어붙이기,중간삽입,삭제 

이제 트리 같은거 만드려고 node 같은거 쓰는 것들은 나중에 정리해야겠다.

 

리스트 쓴다면 위의 시간복잡도 참고하면 될것이다.

스택

그냥 push,pop,top 가 빠르면 스택으로 쓰면되고 파이썬에서는 리스트 쓰면된다 
-> 파이썬의 리스트 시간복잡도 찹고해보자

 

각 기능에대한 파이썬 함수

출처: 솝탁 자료

큐

collections 모듈의 deque(덱) 쓰면된단다

 

각 기능에 대한 파이썬 함수

출처 : 솝탁 자료

함수들의 시간복잡도는 밑에있는 덱의 함수들을 참고하자

덱

Collections 모듈의 deque 클래스로 사용 가능 모든 메서드가 O(1)!!!

 

각 기능에 대한 파이썬 함수

각 함수들의 시간복잡도

출처 : https://daimhada.tistory.com/56

우선순위큐

heapq 라이브러리로 사용

 

각 함수명

push : heappush()

pop : heappop()

 

import heapq

heap_data = [1,3,2,6,8,0,6]

heapq.heapify(heap_data)

heapq.heappush(heap_data, 4)
heapq.heappush(heap_data, 10)

heapq.heappop(heap_data)

 

트리 

anyTree라는게 있다는데 나중에 찾아보자