질문이 있습니다 선생님!

- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.

이 부분에서 삽입삭제가 O(1)인 이유는 알겠는데요,

한가지 궁금한게있습니다!

링크르리스트는 논리적으로 연결되어있어 랜덤엑세스가 안되는것으로 이해를 했는데요, 만약 n이라는 숫자의 뒤에 m이라는 숫자를 추가하거나 삭제를 해야할 경우 head에서 부터 시작하여 n의 위치를 찾기위한 탐색시간이 추가로 들어가지는 않는건가요!?

안녕하세요, 인프런 AI 인턴입니다.

alopp님이 질문하신 링크드 리스트에서 삽입 및 삭제 연산에 대한 시간 복잡도에 대해 답변드리겠습니다.

링크드 리스트는 본질적으로 각 노드가 포인터를 통해 연결된 선형 구조로, 랜덤 엑세스가 불가능합니다. 그렇기 때문에 특정 값을 추가하거나 삭제하기 위해서는 그 위치를 찾아야 하는데, 이 과정에서 탐색 시간(즉, 위치를 찾기 위한 시간)이 추가됩니다.

귀하의 질문에 적합한 유사한 질문 답변을 다음에서 확인하실 수 있습니다:

Linked List 시간 복잡도: 이 답변에서는 링크드 리스트의 삽입/삭제 연산이 O(1)인 이유와 동시에 특정 위치를 찾기 위한 탐색 시간이 O(n)인 것에 대해 설명됩니다.
Linked list의 장점: 이 답변에서는 링크드 리스트의 활용 사례와 삽입/삭제 연산의 효율성에 대해 논의됩니다.

요약: 링크드 리스트에서 삽입 및 삭제 연산이 O(1)인 이유는 노드 간의 연결만 변경하면 되기 때문입니다. 그러나 특정 노드를 찾기 위해 탐색하는 과정에서는 O(n)의 시간이 추가됩니다. 즉, 위치를 찾기 위한 탐색과 실제 삽입/삭제를 분리해서 생각해야 합니다. 탐색 과정까지 고려하면 전체 시간 복잡도는 O(n)이 됩니다.

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.

인프런 커뮤니티 질문&답변