Search
Duplicate

2021 카카오 공채 1차 면접

(내가 찾고, 생각한 답변)
Array 와 Linked List의 차이
→ Array는 메모리 공간에 연속적으로 할당된 것으로, 자료형과 할당 하고자 하는 공간의 크기에 따라 할당되는 메모리의 크기가 정해집니다. 예를 들면, int형 array의 크기를 10만큼 할당하게 되면, 총 40byte가 할당됩니다. Random Access가 가능하고, 인덱스를 알고 있다면 시간복잡도 O(1)만에 해당 원소로 접근이 가능합니다. 따라서 값을 저장해 놓고 찾고자 할때 편리한 자료구조 입니다. 하지만 Array 중간에 값을 삭제하거나 삽입해야 한다고 한다면, 매우 좋지 않은 자료구조입니다. 해당 값을 수정하고 나서 그 인덱스 보다 큰 값들을 한 칸씩 Shift 해야 하기 때문에 시간 복잡도는 O(N) 입니다.
Linked List는 자료의 주소 값으로 노드를 이용해서 서로 연결되어 있는 구조입니다. 따라서 메모리에 할당되는 크기는 (노드의 갯수 x 노드의 크기) 라고 할 수 있겠습니다. Linked List는 데이터를 검색할 시에 O(N)의 시간 복잡도를 갖는데 그 이유는 Array와 다르게 인덱스로 접근하는 것이 아니라 모든 노드들을 순차적으로 탐색해야 하기 때문입니다. 데이터를 삽입하거나 삭제할 때는 이전 노드와 다음 노드를 참조하는 상태만 변경하면 되기 때문에 O(1)의 시간 복잡도를 갖습니다.
Stack Queue 비교
여기서 확인
정렬 방식 Stable, Unstable 구분
여기서 확인
Hash Table 충돌