인프런 커뮤니티 질문&답변
작성한 질문수
Linked list의 장점
작성
·
508
1
선생님 안녕하세요. Linked list의 시간 복잡도에서 질문이 있습니다.
Linked list는 이론상 삽입 삭제가 O(1)이고, 실제 구현해보면 조회의 과정이 필요하기 때문에 O(n) 이라는 점 잘 이해했습니다.
그러면 Array가 Linked list에 비해
조회는 빠르고 (O(1) vs O(n))
삽입 삭제는 동일하며 (O(n))
주소를 저장 할 필요가 없어 동일한 양의 데이터를 저장시 필요한 메모리도 적습니다. (Array가 꽉 찼다고 가정)
이러면 결국 Linked list를 써야하는 경우가 얼마만큼의 데이터가 들어올지 예측을 할 수 없을 때 말고 다른 경우가 있나요??
감사합니다.
답변 1
1
개발남노씨
지식공유자
안녕하세요 준환님.
linked list는 어떻게 구현하냐에 따라서 무궁무진한 활용도가 있습니다.
트리나, 그래프 같은 다른 자료구조를 구현하는데 사용할 수 도 있고,
특정 상황에서는 삽입삭제를 O(1)으로 지속적으로 사용할 수 도 있습니다.
current_node를 활용해서, 한 번 삽입삭제 했던 위치를 계속 가리키고 있음으로써, 실질적인 O(1)가 될 수 있습니다.
또한, deque 자료구조의 경우 (queue강의에서 설명해드릴텐데) linkedlist로 구현하는게 일반적입니다.
질문에 대한 답이 됐을까요~?
또 궁금하신점 있으시면 언제든지 질문주세요
답이 된 것 같아요 감사합니다!