트리와 연결리스트

조회수 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)

    무조건 연결리스트에서만 쓰일 수 있는 기능은 연결리스트에서 빠른거겠죠?

    그러면 삽입과 삭제만을 많이 하는 알고리즘에는 연결리스트가 필요하겠네요.

    예를 들자면 요셉문제를 들 수 있겠네요. (그런데 이 문제는 조금더 구현이 어려운 환형리스트를 구현해야 합니다.)

답변을 하려면 로그인이 필요합니다.

프로그래머스 커뮤니티는 개발자들을 위한 Q&A 서비스입니다. 로그인해야 답변을 작성하실 수 있습니다.

(ಠ_ಠ)
(ಠ‿ಠ)