Queue
2
1 asked
Queue에서 array list의 경우 dequeue시 앞의 공간이 남아있는채로 점점 뒤로 가서 불필요한 공간이 많이 생기는 것으로 알고있는데
linked list의 경우 dequeue를 하게 된다면 공간도 같이 삭제가 되는건가요?
Answer 1
0
안녕하세요, 인프런 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 구현 참고 원본
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.
노션 공유 링크
0
171
2
수업 중간에 내주신 문제는 해답을 알 수 없는걸까요?
0
146
2
최신 강의와 비교
0
144
2
Min Cost Climbing stairs 질문
0
126
2
노션 공유 부탁드립니다!
1
147
2
for 문에 sort 함수 를 사용하면
1
152
2
노션 공유 부탁드립니다.
0
141
2
디스코드가 올바르지 않다고 뜹니다..!
0
147
1
그래프
0
145
2
노션 공유
1
163
2
시간복잡도 질문
2
175
3
11강 질문
1
118
2
노션 공유 부탁드립니다
0
121
2
linkedList - BrowserHistory 코드 질문
0
107
1
list1.append(list2)와 list1.append(list2[:])의 차이가 무엇인가요?
1
201
1
라이브러리 사용
1
175
2
문제 교재는 따로 없는 거 맞나요?
1
245
2
LCA 관련해서 질문이 있습니다.
1
163
2
[Unique Paths] 완전탐색 / DP (후반부)
0
139
1
dp 계단오르기최소비용질문입니다.
0
152
1
Dynamic Array 의 size 정보가 저장되는 곳
2
200
2
노션공유가 안된듯 합니다
1
204
2
[코테 적용] 👉 [3번 문제] 완전탐색 (DFS, BFS) (전반부)
1
146
1
강의자료 만들 때 사용하신 프로그램이 뭘까요?
1
271
1