어나대통령인데님의 면접 결과

배열과 연결 리스트의 기본적인 차이점과 시간 복잡도에 대해서는 어느 정도 이해하고 계시는 것 같습니다. 하지만 답변이 너무 간략하고 부정확한 부분들이 있어 아쉽습니다. 배열은 연속된 메모리 공간에 데이터를 저장하여 인덱스를 통한 랜덤 액세스가 O(1)로 가능하지만, 연결 리스트는 노드들이 포인터로 연결되어 있어 순차 접근만 가능하다는 메모리 구조의 핵심적인 차이를 명확히 설명하시면 좋겠습니다. 또한 배열의 삽입/삭제는 위치에 따라 O(1)~O(n)이고, 연결 리스트는 노드의 참조를 알고 있으면 O(1), 검색이 필요하면 O(n)이라는 정확한 시간 복잡도와 함께 캐시 지역성, 메모리 오버헤드 등의 실무적 고려사항도 함께 학습하시기 바랍니다.

시간 복잡도에 대한 기본적인 이해는 잘 보여주셨고, 각 연산의 최악의 경우를 정확하게 파악하신 점이 좋습니다. 특히 연결 리스트에서 위치를 이미 알고 있을 때와 모를 때를 구분해서 설명하신 부분이 인상적이었습니다. 다만 배열에서 인덱스를 통한 직접 접근이 O(1)이라는 점과, 정렬된 배열에서는 이진 탐색으로 O(log n) 검색이 가능하다는 점을 추가로 언급하시면 더 완성도 높은 답변이 될 것 같습니다. 앞으로는 각 자료구조의 장단점을 메모리 접근 패턴이나 캐시 효율성 관점에서도 생각해보시면 좋겠습니다.

임베디드 환경에서 연결 리스트가 큐/스택 구현 시 헤드와 테일을 통해 직접 접근할 수 있다는 점을 언급하신 것은 좋았습니다. 하지만 배열 기반 큐/스택에서 요소 삭제 시 전체를 이동시켜야 한다고 하신 부분은 잘못된 이해입니다. 배열 기반 큐/스택은 원형 버퍼나 인덱스 포인터를 사용하여 실제로는 요소 이동 없이 O(1) 시간에 삽입/삭제가 가능합니다. 메모리 관리 측면에서는 배열이 연속된 메모리 공간을 사용해 캐시 효율성이 높고 메모리 오버헤드가 적은 반면, 연결 리스트는 각 노드마다 포인터를 위한 추가 메모리가 필요하고 동적 할당으로 인한 메모리 단편화 문제가 발생할 수 있다는 점을 추가로 학습하시면 좋겠습니다.