트리와 연결리스트
조회수 1440회
1 답변
-
먼저 트리와 연결리스트를 비교해봅시다.
종류 연결리스트 트리 배열 삽입(insert) O(1) O(log n) O(n) 탐색(find) O(n) O(log n) O(n) 삭제(erase) O(1) O(log n) O(n) 참조(at) O(n) x O(1) 정렬(sort) O(n log n) O(1) O(n log n) 무조건 연결리스트에서만 쓰일 수 있는 기능은 연결리스트에서 빠른거겠죠?
그러면 삽입과 삭제만을 많이 하는 알고리즘에는 연결리스트가 필요하겠네요.
예를 들자면 요셉문제를 들 수 있겠네요. (그런데 이 문제는 조금더 구현이 어려운 환형리스트를 구현해야 합니다.)
댓글 입력