자료구조 면접 질문) "array와 linked list 의 차이점을 말해주세요."

자료구조 선택 기준:

• 시간 복잡도:
  • 삽입, 삭제, 탐색, 접근
  • 삽입이 중요한 기능 예시:
    • 로깅:
      • std::deque - 여러 고정 크기의 array의 순서를 관리하는 map을 갖는 자료구조
        • 장점: 크기 초과 시 데이터 이동이 없음
        • 비교: std::vector는 크기 초과 시 전체 데이터 이동이 일어남. 최악의 경우 O(n) 걸림
  • 중간 삽입이 중요한 기능 예시:
    • 스케줄:
      • std::list - doubly linked list
        • 장점: 중간 삽입이 O(1)
        • 비교: std::vector 는 연속적 메모리 사용. std::list 는 비연속적 메모리 사용
  • 검색이 중요한 기능 예시:
    
    • 캐싱 시스템:
      • std::unordered_map - hash table
        
        • 장점: 검색이 O(1)

array의 특징:

• 시간 복잡도:
  • 검색 - O(n)
  • 할당된 메모리 공간 내 끝에 삽입/삭제 - O(1)
    • 할당된 메모리 공간 초과 시 - O(n): 데이터 복사 필요
  • 중간 삽입/삭제 - O(n): 데이터 이동 필요
  • 접근 - O(1)
• C++ 구조체:
  • std::array: 정적 배열
  • std::vector: 동적 배열
• 직관적
• 캐시 친화적:
  
  • 연속적 메모리 사용

linked list의 특징:

• 시간 복잡도:
  • 삽입/삭제 - O(1)
  • 중간 삽입/삭제 - O(1)
  • 검색 - O(n)
  • 접근 - O(n): n번째 요소를 찾아가려면 필요하 시간
• C++ 구조체:
  • std::list - doubly linked list

다음 글:

- 알고리즘 면접 질문) "정렬 알고리즘 중 사용해보신 것이 있으신가요? 왜 그 알고리즘을 사용하셨나요?"

- 자료구조 면접 질문) "binary search tree가 뭔가요? 어떨 때 사용하나요?"