링크드리스트 중간에 삽입 삭제 연산

Question

1. 현재 학습 진도 몇 챕터/몇 강을 수강 중이신가요?   3주차 어떤 알고리즘을 학습하고 계신가요? 링크드리스트 여기까지 이해하신 내용은 무엇인가요?     2. 어려움을 겪는 부분 어느 부분에서 막히셨나요? 코드의 어떤 로직이 이해가 안 되시나요? 어떤 개념이 헷갈리시나요?   노션에서 링크드 리스트 중간에 삽입 삭제가 O(1)이라고 되어있는데 삽입을 특정위치에 하기위해서 get_node()로 순회를 해야하기 때문에 O(N)이 아닌가 궁금합니다. 혹시 놓친 부분이 있는걸까요?   3. 시도해보신 내용 문제 해결을 위해 어떤 시도를 해보셨나요? 에러가 발생했다면 어떤 에러인가요? 현재 작성하신 코드를 공유해주세요   이렇게 구체적으로 알려주시면, 더 정확하고 도움이 되는 답변을 드릴 수 있습니다! 😊

딩코딩코 · Answer

안녕하세요 석기님 좋은 질문 감사합니다!!!   조금 애매한 부분을 정확하게 질문해주신 것 같습니다 삽입 & 삭제 하는 행위 자체에만 집중할 것이냐, 혹은 삽입 & 삭제 하기 위한 전체 행위에 대해서 파악할 것이냐에 따라 다를 것 같습니다   삽입 & 삭제 하는 행위 자체에만 집중한다면 O(1) 이 맞는데, 석기님이 말씀해주신 것처럼 찾아서 삭제하는 전체 과정을 의미한다면, 찾기위한 전제 과정에서 O(N) 이 소요될 것 같습니다   즉, 노션에서 말하는 O(1)은 "순수한 삽입/삭제 동작 자체"를 의미하는 거예요. 하지만 실제 문제에서는 대부분 위치를 찾는 과정이 포함되므로 O(N)이 되는 게 맞습니다. 이런 식으로 깊게 생각하시면 자료구조 이해도가 확실히 높아지실 것 같습니다. 다음에 링크드리스트 문제 만나시면 "위치를 찾아야 하나? 아니면 이미 알고 있나?"를 먼저 생각해보시고 시간 복잡도를 결정하시면 좋을 것 같습니다 좋은 질문 감사합니다!

인프런 AI 인턴 · Answer

안녕하세요, 인프런 AI 인턴입니다. 권석기님, 링크드 리스트의 중간에 삽입 또는 삭제할 때 시간 복잡도가 O(1)으로 될 수 있는 경우는, 삽입이나 삭제할 특정 노드까지의 포인터를 이미 가지고 있는 경우입니다. 즉, 현재 위치를 알고 있을 때 바로 삽입이나 삭제가 가능하기 때문에 O(1)로 처리됩니다. 그러나 질문하신 대로 특정 위치에 삽입하기 위해 그 위치의 노드를 찾기 위해서는 순회를 해야 하며, 이 경우 시간 복잡도가 O(N)입니다. 즉, 노드를 찾는 시간이 O(N)이나, 위치를 이미 알고 있는 경우 삽입/삭제 연산 자체는 O(1)이라는 것을 이해하시면 될 것 같습니다. 추가적인 질문이나 궁금한 점이 있으시면 언제든지 말씀해 주세요! 학습에 도움 되시길 바랍니다. 😊 강의 자료 또는 관련 정보는 수업 자료 버튼을 이용해 강의실 내 커리큘럼 메뉴에서 확인하실 수 있습니다. 수업 자료 확인하기