TIL

오늘 한 일

왜 Queue 구현에 LinkedList보다 ArrayDeque이 효율적일까?

1. 메모리 관리 효율 (Memory Overhead)

LinkedList: 데이터를 추가할 때마다 ‘Node’라는 객체를 새로 생성합니다. 이 노드에는 실제 데이터 외에도 앞뒤 노드의 주소값(포인터) 정보가 포함되어 있어 추가적인 메모리 소모가 큽니다.

ArrayDeque: 내부적으로 가변 배열을 사용합니다. 별도의 객체를 생성하지 않고 배열에 값만 저장하기 때문에 메모리 점유율이 훨씬 낮습니다.

2. 속도 및 캐시 효율 (Cache Locality)

ArrayDeque: 데이터가 메모리상에 연속적으로 배치되어 있어 CPU 캐시를 활용하기에 유리하며 탐색 속도가 빠릅니다.

LinkedList: 노드들이 메모리 여기저기에 흩어져 있어 데이터에 접근할 때마다 CPU가 메모리 주소를 찾아다녀야 하므로 상대적으로 느립니다.

3. 가비지 컬렉션(GC) 부담 저감

LinkedList: 큐에 데이터를 넣고 뺄 때마다 노드 객체가 생성되고 삭제됩니다. 이는 가비지 컬렉터가 정리해야 할 대상을 계속 만들어내어 프로그램 성능에 영향을 줄 수 있습니다.

ArrayDeque: 배열을 재사용하므로 새로운 객체 생성이 적고 GC의 부담이 거의 없습니다.