-
질문 & 답변
카테고리
-
세부 분야
게임 프로그래밍
-
해결 여부
미해결
list 중간 삽입 삭제와 임의접근간에 관계성에 대한 질문입니다.
23.12.05 17:31 작성 23.12.05 18:14 수정 조회수 162
0
질문에 앞서 항상 좋은 강의 감사합니다.
공부하면서 생각난 내용에 대한 질문이있어 글 남깁니다.
stl 대표적인 자료구조인 vector와 list에 장단점에 대한 질문들이 면접에서 많이 나오는데
중간 삽입, 삭제 과정에서 결국 vector와 list 둘다 같은 시간복잡도를 가지는게 아닌가 생각이 드는데 잘못 생각한걸까요?
Vector 해당 메모리 참조 및 삭제(O(1)) + 데이터 재정렬(O(N))
List 해당 메모리 참조 및 삭제(O(N)) + 참조 노드 개편(O(1))
아니면 해당 질문에 논점이 전체 과정(참조과정(임의접근) + 삭제 + 삭제 후 재정렬)이 아닌 참조 과정을 제외한 오로지 삽입,삭제 과정 후 참조 노드 개편이 vector의 데이터 재정렬보다 빠르기 때문에 list가 더 좋다고 하는 건가요?
만약 1번에서 중간 삽입, 삭제 과정에서 참조 노드 개편이 vector의 데이터 재정렬보다 빨라서 중간 삽입, 삭제가 좋다고 하는 거라면 면접에서도 vector는 중간 삽입,삭제과정 이후 데이터 재정렬단계가 존재하기 때문에 list가 더 빠르다라고 대답하는 것이 좋은 대답일까요 ?
답변을 작성해보세요.
0
인프런 AI 인턴
2023.12.07
안녕하세요, 인프런 AI 인턴입니다. ji980207님 질문하신 내용에 답변드리겠습니다.
STL의 vector와 list는 서로 다른 방식의 자료구조로, 여러 면에서 다른 성능 특성을 보입니다.
vector는 동적 배열로 구현되어 있어, 중간 삽입이나 삭제 시에 삽입하거나 삭제한 위치 뒤에 있는 모든 요소들을 이동시켜야 합니다. 이것은 O(N)의 시간 복잡도를 가지는 상황입니다. 그러나 임의 접근 측면에서는 O(1)의 시간 복잡도를 가지기 때문에, 인덱스를 통한 접근이 매우 빠릅니다.list는 이중 연결 리스트(Double-Linked List)로 구현되어 있어, 중간 삽입이나 삭제 자체는 이전 노드와 다음 노드의 포인터만 변경하면 되기 때문에 O(1)의 시간 복잡도를 가집니다. 그러나 특정 위치를 찾기 위해서는 처음 노드부터 순차적으로 탐색해야 하므로, 평균적으로 O(N)의 시간이 걸립니다.
따라서, vector에서 원소의 중간 삽입이나 삭제를 할 경우, 해당 위치를 찾는 것이 비교적 빠르나(임의 접근이므로), 삽입 또는 삭제 이후 모든 요소들을 이동시켜야 하는 과정에서 성능이 저하됩니다.
반면 list에서는 특정 위치를 찾는데 시간이 걸리지만, 찾고 난 이후의 삽입 또는 삭제 처리는 매우 빠릅니다.
결론적으로, 면접 등에서 이 대답을 하는 경우에는 전체 과정의 시간복잡도를 계산할 때 vector와 list의 특성을 명확하게 이해하고 대답하는 것이 중요합니다. 즉, vector는 임의 접근은 빠르지만 중간 삽입/삭제 후 데이터 재정렬이 필요하고, list는 임의 접근이 느리지만 삽입/삭제 자체는 빠르다는 사실을 명확히 하면서 대답하시면 됩니다.
STL 컨테이너를 선택할 때는 각각의 장단점을 고려하여, 해당 응용 프로그램의 요구 사항에 가장 적합한 자료구조를 선택하는 것이 중요합니다.
답변 1