인프런 커뮤니티 질문&답변
작성한 질문수
Singly-LinkedList의 append 시간복잡도
해결된 질문
작성
·
155
1
안녕하세요! 강의 잘 보고 있습니다.
Queue 자료구조 설명 중, List-Bases의 경우 일반적으로 Singly-LinkedList로 구현한다고 말씀해 주셨는데요. (영상에서는 singly-lilnkedlist로 오타입니다!! ㅋㅋㅋㅋ)
Singly-LinkedList는 head 값만 가지고 있는 상태인데, append를 할 경우 추가된 노드를 맨 뒤 노드에 연결해 주어야 해서 "head부터 맨 마지막 노드까지 순회를 해야하는게 아닌가?" 싶어 여쭤봅니다.
append일 경우 시간복잡도는 O(n)이 되는게 아닌가요?
답변 2
1
안녕하세요, 쇼콜라끼삐또리님.
네, 맞습니다. queue를 구현할 때 singly ilnked list로 구현하면, enqueue() 또는 dequeue()중에서 하나의 연산은 O(n)이 되어버리네요.
해당 내용은 doubly linked list이면서 head, tail을 둘다 가진상태로 구현되어야 합니다.
상세하게 생각하지 않으면 놓쳤을 뻔한 내용인데, 질문주셔서 감사합니다!!
추가로 궁금한점 있으면 편하게 질문 주세요 :)
0
안녕하세요, 인프런 AI 인턴입니다.
네, 맞습니다. Singly-LinkedList에서 노드를 추가(append)할 경우, head부터 시작해서 맨 마지막 노드까지 순회해야 합니다. 그래서 append 연산의 시간 복잡도는 O(n)이 됩니다. 맨 마지막 노드를 직접 가리키는 포인터(예: tail pointer)가 없기 때문에, 매 번 새로운 노드를 추가할 때마다 리스트의 처음부터 끝까지 순회해야 합니다.
만약, 리스트의 맨 끝에 접근하는 작업을 빈번히 수행해야 한다면 Singly-LinkedList 대신 다른 데이터 구조를 사용하는 것을 고려할 수도 있습니다. 예를 들어, Doubly-LinkedList나 tail 포인터를 추가로 유지하는 방법 등이 있겠죠.
쇼콜라끼삐또리님의 학습에 도움이 되길 바랍니다. 추가적인 질문이나 궁금한 점이 있다면 언제든지 질문해주세요!