Cộng đồng Hỏi & Đáp của Inflearn
câu hỏi đã được viết
단방향 연결리스트를 활용한 큐의 시간복잡도 관련 질문입니다.
Viết
·
61
0
안녕하세요!
단방향 연결리스트를 활용한 큐가 offer 수행시,
시간복잡도가 O(1) 이 되어야하는건 아닌지 의문이 들어 질문 남깁니다!
LinkedList 가 last 변수를 통해 마지막 노드의 정보를 가지고 있어서 큐에서 offer 시 O(1) 이 될 수 있을거같아서요.
강의 잘보고 있습니다. 감사합니다!
Câu trả lời 1
0
dackkuck
Người chia sẻ kiến thức
안녕하세요
단방향 연결리스트에서 헤드 정보를 통해 특정 노드에 접근하는 방법으로는 O(n) 이 걸리고
양방향 연결리스트에서 헤드랑 테일 노드를 이용하면 양끝은 O(1) 이 걸리도록 할 수 있습니다.
말씀하신대로 단방향 연결리스트에 양방향 연결리스트처럼 테일 노드를 추가해서하면 마지막 노드의 정보를 저장하니까 O(1) 걸리도록 개선시킬 수 있습니다.
하지만 특정노드의 정보를 저장하는 개수가 늘어나면 연결리스트가 배열에 가까워지니까 공간을 희생할지 시간을 희생할지 필요한만큼 결정할 수 있어야합니다.
강의에서도 양방향 연결리스트로 큐를 구현할때는 offer 가 O(1) 으로 나오도록 구현됩니다
감사합니다.
이해해습니다. 감사합니다!