Linked List의 시간 복잡도에 대한 질문입니다

Question

- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.   일반적으로 연결 리스트의 시간 복잡도를 설명할 때 삽입/삭제의 시간복잡도를 O(1)이라고 말하기는 하고, 면접때도 이렇게 답변하는 게 맞겠지만 그냥 궁금증 때문에 여쭤봅니다!   실질적으로 봤을 때는 예를 들어 현재 10개의 노드를 가진 연결리스트의 4번째와 5번째 노드에 데이터를 추가하고 싶다고 가정하면 4번째 노드까지 O(n)의 시간 복잡도로 이동한 뒤 O(1)의 속도로 삽입하기 때문에 head, 혹은 tail(원형 더블 링크드 리스트이라면)를 제외한 다른 곳에 데이터를 삽입하는 속도를 O(N)이라고 봐도 무방한 게 맞을까요? 반대로 삭제의 경우에도 마찬가지가 아닌가 궁금합니다

kundol · Answer

안녕하세요 ㅎㅎ 보통 어떤 연산의 시간 복잡도라고 했을 때 그 연산을 중점으로 봅니다. 해당 연산은 O(1)이 맞습니다. 다만, 수강생님 말씀처럼. 실질적으로 봤을 때는 예를 들어 현재 10개의 노드를 가진 연결리스트의 4번째와 5번째 노드에 데이터를 추가하고 싶다고 가정하면 4번째 노드까지 O(n)의 시간 복잡도로 이동한 뒤 O(1)의 속도로 삽입하기 때문에 head, 혹은 tail(원형 더블 링크드 리스트이라면)를 제외한 다른 곳에 데이터를 삽입하는 속도를 O(N)이라고 봐도 무방한 게 맞을까요? 실질적으로 구현하려면 순차적접근 + 삭제이기 때문에 O(N + 1)이 되어 O(N)이라고 보는게 맞습니다. 그렇다면 이런 질문이 있을 수 있겠죠. 아니 그러면.. 삽입, 삭제가 빈번할 때는 연결리스트가 O(1)이 되어 빠르다고 했는데. 이렇게 되면 배열의 랜덤접근 + 삽입, 삭제 또한 O(N + 1) = O(N)이 되어 똑같은 거 아닌가? 라고 생각이 들 수 있습니다. 제거로 예로 들면 연결리스트는 순차적접근 + 제거시 포인터 수정입니다. 배열은 랜덤접근 + 제거시 나머지 요소를 "이동" 시켜야 합니다. 이 때 이 접근 비용보다 이동시키는 비용이 더 많이 드는 작업이기 때문에 삽입 / 삭제에는 연결리스트가 더 효율적입니다. 또 질문 있으시면 언제든지 질문 부탁드립니다. 좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :) 감사합니다. 강사 큰돌 올림.