연결리스트 삽입삭제 O(1) 아닌가요?
4
작성한 질문수 1
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.
연결리스트 강의때 O(n)이라고 잘못 얘기하신거 같아요.
답변 2
0
안녕하세요, 인프런 AI 인턴입니다. 김재철님.
연결 리스트의 삽입과 삭제의 시간 복잡도에 대해 궁금하신 점이 있으신 것 같네요. 연결 리스트는 삽입과 삭제가 O(1) 시간 복잡도를 가진다고 일반적으로 알려져 있습니다. 하지만 삽입이나 삭제 작업을 수행하기 위해 탐색이 필요하다면, 탐색하는 데 O(n) 시간이 걸릴 수 있습니다.
즉, 연결 리스트에서 특정 위치에 삽입하거나 삭제하려면 그 위치까지 탐색하는 것이 필요하기 때문에 전체 작업의 시간 복잡도는 O(n)이 됩니다. 하지만 탐색이 완료된 후 실제 삽입 또는 삭제 작업은 O(1)로 이루어집니다.
관련된 기존 답변이 있어서 같이 참고해 보시면 도움이 될 것 같습니다:
연결 리스트 삽입과 삭제 질문드립니다.
여기에서는 연결 리스트 내에서 노드를 삽입하기 위해 필요한 탐색과, 그 후의 삽입의 시간 복잡도에 대해 설명합니다.연결리스트 질문입니다.
연결 리스트에서의 삽입 및 삭제에 대한 조건과 처리 방식에 대해 상세히 설명하고 있습니다.
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.
큐의 마지막 데이터가 head에 위치해야 하는 이유가 궁금합니다.
0
71
2
이중연결 리스트 데이터 삭제시 질문이 있습니다.
1
64
2
자바스크립트 배열은 동적이 아닌가요?
1
87
2
자바스크립트 배열
0
77
2
코테에서 링크리스트 자료구조를 사용해야 하면, 이번 강의에서 구현한 메서드들도 모두 직접 구현하면 되나요?/
0
153
2
공부 방식 질문 드립니다.
1
117
2
메모이제이션과 타뷸레이션 관련해서 질문드립니다.
1
169
2
병합정렬에서 질문이 있습니다.
2
142
1
병합정렬 질문 있습니다.
1
137
5
데이터 삽입, 삭제 함수 오류 범위 설정
0
158
2
해시 테이블에서 질문이 잇습니다.
2
128
2
시간복잡도 계산 시 1회 연산당 연산량은 왜 고려하지 않는 건가요?
1
147
2
터미널 설정
0
114
2
2:13분 관련 질문입니다
0
91
1
8:47초경부터 9:00초까지 질문입니다.
1
135
2
tail을 삭제하는 경우에 관련해서 질문이 있습니다.
0
107
1
2:36초 head 위치가?
1
111
2
환경구축강의 중 터미널 파일 실행오류
0
162
2
4:58 이중for문 질문있습니다.
0
104
1
hanoi함수 처음 호출에 대해서 여쭤봅니다.
1
132
2
해쉬테이블 데이터 관련해서 질문있습니다.
0
149
2
자바스크립트 Map과 어떤 차이가 있나요??
0
205
2
질문이있습니다.
0
104
1
2번째 복습 스터디📖 를 진행하고 스터디원분들과 나눈 질문들 입니다.(자료구조와 알고리즘)
1
148
2