인프런 커뮤니티 질문&답변
작성한 질문수
큐의 마지막 데이터가 head에 위치해야 하는 이유가 궁금합니다.
작성
·
15
0
제가 이해한 강의 내용은 아래와 같습니다.
"데이터 추가는 첫번째 위치에 데이터를 삽입을 한다. 결국 처음에 추가한 데이터는 리스트의 마지막 에 위치한다"
"데이터를 내보낼때는 리스트의 마지막 데이터를 내보낸다"
"연결리스트만으로는 구현이 어렵기 때문에 이중연결리스트로 구현한다"
하지만 제가 생각했을 때는 "첫번째로 추가한 데이터는 head로 고정, 데이터를 추가하면 노드로 연결 > 데이터를 내보낼때는 리스트의 첫번째 데이터인 head 를 내보낸다" 이런식으로 구현하게 되면 이중연결리스트를 이용하지 않고 간단하게 구현이 가능할 것 같다는 생각이 들었습니다.
제가 생각한 구현방식이 올바른지, 강사님께서 말씀하신 방식의 장점이 궁금합니다.
답변 2
0
안녕하세요, cyb258님!
head 위치에 대해 궁금증이 생기셨군요.
말씀드린 방법으로 큐를 구현할 때 문제가 생기는 부분을 설명드리겠습니다.
첫 번째로 넣은 데이터를 head로 고정하고 한 방향으로 데이터를 삽입하게 되면,
삽입할 때마다 가장 뒤 노드까지 타고 들어가야 합니다.
예를 들어 A가 가장 먼저 삽입되었고, A가 head 상태로 다음과 같이 삽입되어 있다고 가정해 보겠습니다.
head
↓
A - B - C - D여기서 새로운 데이터 E를 삽입하게 되면,head는 A이기 때문에
A → B → C → D를 참조하고 D의 다음 노드로 E를 삽입해야 하기 때문에 O(1)의 성능을 취하지 못합니다.
head의 위치를 끝에 고정하나 앞에 고정하나, 삽입·제거의 시간 복잡도 순서만 바뀔 뿐 결국 O(n)의 시간이 걸리는 것은 피할 수 없습니다.
이런 이유로 이중 연결 리스트를 구현하는 것입니다.
궁긍즘이 해결되셨나요? 😊
0
안녕하세요, 인프런 AI 인턴입니다. cyb258님!
큐에서 데이터를 추가하고 제거하는 방식이 헷갈리실 수 있습니다.
질문에서 큐의 구현을 어떻게 해야 하는지, 그리고 강의에서 설명한 방식의 이유에 대한 부분을 보고 계신 것 같은데요.
큐의 기본 개념: 큐는 FIFO(First In First Out) 구조입니다. 즉, 먼저 들어온 데이터가 먼저 나가는 구조입니다. 따라서 큐에서는 데이터를 추가할 때 리스트의 끝에 삽입하고, 데이터를 빼낼 때 리스트의 시작에서 데이터를 제거하는 것이 일반적입니다.
단방향 연결 리스트의 한계: 단방향 연결 리스트로 큐를 구현하게 되면, 데이터를 추가하는 작업은 O(1)로 효율적이지만 데이터를 제거하는 작업이 O(n)이 됩니다. 왜냐하면 마지막 노드를 찾기 위해 처음부터 끝까지 탐색해야 하기 때문입니다.
이중 연결 리스트의 장점: 이중 연결 리스트를 사용하면 이러한 비효율성을 해결할 수 있습니다. 이중 연결 리스트는 노드가 두 개의 포인터(이전, 다음)를 가지고 있어서, 리스트의 처음과 끝에서 모두 효율적인 삽입 및 삭제 작업을 수행할 수 있습니다. 따라서 이중연결리스트로 구현하면 데이터 추가와 제거 작업이 모두 O(1)로 처리됩니다.
즉, 이중 연결 리스트를 사용하면 큐의 특성에 맞게 데이터를 추가하고 제거하는 작업을 효율적으로 수행할 수 있습니다. 이는 데이터의 삽입과 삭제가 빈번히 발생하는 상황에서 성능상의 큰 이점을 제공합니다.
관련된 유사한 질문의 답변을 참고하시면 더 이해하기 쉬울 수 있습니다:
- 큐에서 사용하는 연결리스트
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.