Queue

Question

Queue에서 array list의 경우 dequeue시 앞의 공간이 남아있는채로 점점 뒤로 가서 불필요한 공간이 많이 생기는 것으로 알고있는데

linked list의 경우 dequeue를 하게 된다면 공간도 같이 삭제가 되는건가요?

communityai8509 · Answer

안녕하세요, 인프런 AI 인턴입니다. Jh K님 질문하신 내용처럼 연결 리스트 기반 Queue에서는 dequeue 시 가장 앞 노드를 제거하고 front 포인터를 다음 노드로 이동 시킵니다. 따라서 배열처럼 앞쪽에 빈 공간이 계속 누적되지는 않습니다. 다만 실제 메모리에서 노드 공간이 즉시 반환되는지는 언어의 메모리 관리 방식에 따라 다릅니다. Python에서는 제거된 노드를 더 이상 참조하지 않으면 가비지 컬렉터가 회수합니다. 연결 리스트 Queue의 dequeue 연산 자체는 일반적으로 O(1) 입니다. 반대로 배열 기반 Queue는 앞의 공간이 비어 있을 수 있으므로, 이를 재사용하기 위해 front 와 rear 인덱스를 이동시키는 Circular Queue 방식으로 구현할 수 있습니다. 따라서 배열 Queue라고 해서 반드시 빈 공간을 계속 버리는 것은 아닙니다. 관련 답변을 참고해 주세요. doubly linked list 질문입니다. 연결 리스트에서 노드를 삽입·삭제하는 연산과, 해당 위치를 찾는 데 필요한 시간 복잡도의 차이를 설명하고 있습니다. Circular Queue에 대해서 질문드려요 배열 기반 Queue에서 front 와 rear 를 이동시켜 앞쪽의 빈 공간을 재사용하는 방법을 설명하고 있습니다. Circular Queue 구현 참고 원본 저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.