* 겪고 있는 문제 상황을 최대한 자세하게 작성해주세요.

* 문제 해결을 위해 어떤 시도를 해보았는지 구체적으로 함께 알려주세요.

안녕하세요 좋은 강의 해주셔서 잘 듣고 있습니다.

강의를 듣는 도중 연결리스트 관련하여 궁금증이 생겨서 글 올립니다.

설명 중에 연결리스트의 중간 특정 위치에 값을 삽입하는 경우 시간복잡도가 O(1)이라고 말씀해 주셨습니다.

이 때 특정위치에 값을 삽입하기 위해선 앞 뒤의 연결을 끊고 그 위치에 값을 삽입 후 다시 연결해주면 되기에 O(1)인 것은 이해했습니다.

그런데 연결리스트 중간의 특정 위치에 값을 삽입하기 위해선 그 위치를 찾기 위해 연결리스트의 처음부터 next를 통해 찾아가야 할텐데, 이 과정이 결국 O(N)이라고 생각되었습니다.

그렇다면 결론적으로 연결리스트에서 중간에 값을 삽입하려면, 1. 특정 위치를 찾는 행위: O(N) + 2. 값 삽입 후 연결: O(1) 이렇게 되면서 결국엔 O(N)이 아닌가요?

좋은 강의 해주셔서 감사합니다.