보통 큐를 구현할 때는 LinkedList를 사용하고, 그래프에서 인접 리스트를 구현할 때는 ArrayList를 사용한다.
LinkedList와 ArrayList의 차이점을 알아보자
먼저 ArrayList는 기본적으로 배열을 사용한다. 크기를 지정하지 않아도 동적으로 조절이 가능하다.
그리고 Index를 가지고 있기 때문에, 데이터의 조회 속도가 매우 빠르다. 하지만 데이터의 삽입과 삭제의 경우 데이터의 위치를 그때마다 조정해줘야 하기 때문에 속도가 느리다.
LinkedList는 양방향의 연결 리스트로 구성되어 있다.
아래 그림과 같이 각각의 노드는 자신의 전의 노드, 후의 노드의 위치를 참조하고 있다. (가리키고 있다.)
각각의 데이터는 서로 데이터를 순차적으로 접근하기 위해 조회 속도가 느리다.
단, 데이터의 삽입 삭제 시 참조값만 바꿔주면 되므로 속도가 매우 빠르다.
큐를 구현할 때 ArrayList를 사용하지 않고 LinkedList를 사용하는 이유에 대해 알게 되었다. 큐는 데이터의 조회가 필요 없고 (head만 조회하므로) 데이터의 삽입, 삭제의 동작만 하므로 이에 유리한 LinkedList를 사용하는 것이다.
Reference
Backend Developer 💻 😺