인프런 커뮤니티 질문&답변
작성한 질문수
Dynamic Array와 Linked List의 시간복잡도에 대해서..
작성
·
48
0
안녕하세요. 강의를 보다 궁금한 점이 생겨서 질문하게되었습니다.
배열의 경우에는 중간에 데이터를 삽입 삭제를 하게되면 중간데이터를 기점으로 왼쪽이나 오른쪽으로 모든 데이터를 쉬프트를 해야하기 때문에 빅오n의 시간을 가진다고 볼 수 있는데 그렇다면 링크드리스트에서는 중간 데이터를 삽입, 삭제하게되면 다음 노드나 이전 노드의 주소를 참조만 하기만 하면되기 때문에 빅오 일의 시간복잡도를 가지게 된다고하였습니다. 그런데 중간에 데이터를 삽입,삭제할 때 이전 노드, 다음 노드의 주소를 참조하기 위해서는 해당 노드에 접근해서 참조 주소를 알아내야하지않나요? 그렇다면 링크드리스트의 경우 조회할 때 빅오 n의 시간복잡도를 가지기 때문에 빅오 n이라고 생각이 들 수도 있는데 아닌가요? 제 생각의 오류가 있는지 알고 싶습니다.
링크드리스트의 삽입 삭제시
삽입삭제 o(1) + 이전노드주소참조하기위한조회 o(n)
이므로 o(n)의 시간복잡도를 가지는게 아닌지 궁금합니다.
답변 1
0
안녕하세요, 인프런 AI 인턴입니다. 김민규님.
Linked List와 Dynamic Array의 시간 복잡도에 대한 질문 주셨네요.
김민규님께서 지적하신 내용이 정확합니다. Linked List의 원소 삽입 또는 삭제 시, 상대적으로 간단한 포인터 조작을 통해 삽입 삭제 자체는 O(1)의 시간 복잡도를 가질 수 있습니다. 하지만 실제로 삽입하거나 삭제할 노드를 찾는 과정은 Linked List에서는 O(n)의 시간 복잡도를 가집니다. 따라서, 전체적인 삽입 및 삭제의 시간 복잡도는 조회 과정이 포함된 O(n)로 보는 것이 맞습니다.
이와 관련된 기존 질문과 답변도 살펴볼 수 있으니, 아래 링크를 참고해 주세요.
- Linked List 시간 복잡도에서는 Linked List에서 인덱스를 찾을 때의 시간 복잡도와 연관된 점을 다루고 있습니다.
질문해 주신 내용은 많은 학생들이 헷갈릴 수 있는 부분이기 때문에 관련해서 강의에서 직접 시연을 보실 수 있습니다. 혹시 더 자세한 설명이나 추가적인 궁금한 사항이 있으시면 강의 내용에서 해당 부분을 다시 한 번 확인해 보셔도 좋습니다.
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.