링크드 리스트 중간 삽입삭제 시간복잡도 질문
32
1 asked
1. 현재 학습 진도
몇 챕터/몇 강을 수강 중이신가요?
어떤 알고리즘을 학습하고 계신가요?
여기까지 이해하신 내용은 무엇인가요?
16강 2-2 어레이와 링크드 리스트
2. 어려움을 겪는 부분
어느 부분에서 막히셨나요?
코드의 어떤 로직이 이해가 안 되시나요?
어떤 개념이 헷갈리시나요?
강의에서는 링크드리스트의 중간 삽입/삭제시 시간복잡도가 O(1)이라고 설명해주신 부분이 이해가 안돼서 질문 드립니다! 예를들어 특정 index에 값을 노드를 추가한다 라고 한다면, 제 생각에는 해당 index-1번째에 해당하는 노드를 찾기 위해 처음부터 노드를 타고 들어가야 하므로 탐색 비용 때문에 O(n)이 되어야 할 것 같다는 생각이 들어서요!
강의 너무 잘 듣고 있습니다. 감사합니다!
3. 시도해보신 내용
문제 해결을 위해 어떤 시도를 해보셨나요?
에러가 발생했다면 어떤 에러인가요?
현재 작성하신 코드를 공유해주세요
이렇게 구체적으로 알려주시면, 더 정확하고 도움이 되는 답변을 드릴 수 있습니다! 😊
Answer 1
0
안녕하세요, 인프런 AI 인턴입니다. Jihoon Lee님,
링크드 리스트의 중간 삽입·삭제 시간 복잡도에 대해 같은 내용을 다룬 기존 답변을 참고해 주세요.
링크드리스트 중간에 삽입 삭제 연산
핵심은 노드를 찾는 과정과 실제 삽입·삭제 과정의 시간 복잡도를 구분하는 것입니다.
- 삽입·삭제할 위치의 노드 또는 포인터를 이미 알고 있다면, 연결만 변경하면 되므로 O(1)입니다.
- 하지만 특정
index에 삽입·삭제하기 위해 처음부터 리스트를 순회하며 해당 노드를 찾아야 한다면, 탐색에 O(n)이 걸립니다.
- 따라서
index를 입력받아 위치를 찾는 전체 연산은 일반적으로 O(n)이고, 위치를 이미 알고 있을 때의 순수한 삽입·삭제 연산만 O(1)이라고 이해하시면 됩니다.
즉, 질문자님께서 생각하신 것처럼 index - 1번째 노드를 찾는 과정까지 포함하면 O(n)이 되는 것이 맞습니다. 강의에서 설명한 O(1)은 이미 해당 노드의 주소나 포인터를 알고 있다는 전제에서의 시간 복잡도입니다.
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.
재귀함수 종료조건
0
27
1
백준 사이트 준비중이라 문제를 볼 수 가 없어요
0
52
1
해당 차수 영상이 짤려 나갑니다
0
52
1
1-11 소수 나열하기 (에라토스테네스의 체)
0
69
1
수강평 이벤트
0
94
2
코딩테스트 처음인데 이런 공부방법이어도 괜찮을까요
0
185
2
3-3 정렬-2 선택정렬 로직
0
82
2
링크드 리스트 끝에서 k번째 값 출력하기
0
77
2
LinkedList 과제 Fast, slow 포인터
0
76
2
투포인터 시간복잡도
0
90
2
수강평 작성 후 자료
0
82
2
수업교재 링크 오류
2
147
2
프로그래머스에서 제출 후 채점시 틀림ㅠ
0
193
2
1-10 알고리즘 더 풀어보기(2) 질문 있습니다
0
109
2
문제 풀이 방식 관련 질문입니다!
0
124
2
1-5 알고리즘과 친해지기 (2) - 최빈값찾기 질문 있습니다
0
127
2
수업자료 pdf 받고싶습니다
0
140
2
강의 자료 오류 수정
0
99
1
2-10 더하거나 빼거나 관련 질문입니다
0
89
2
3-8 해쉬 -2
0
69
2
Linked List Element Delete Explanation Problem
0
96
2
강의3-4 스택 탑 문제
0
105
2
코드스니펫 입출력 케이스에 오류가 있는것 같아요
0
132
3
링크드 리스트 원소 찾기 구현 방식 질문드립니다.
0
109
2