[TIL] Queue, ArrayList가 아닌 LinkedList사용 이유

java로 알고리즘 푸는 나는 너비 우선 탐색을 풀 때 Queue를 사용한다.

그런데 왜 Queue를 선언할 때 LinkedList를 사용하는지, 구조적으로 어떤 차이가 있어 LinkedList를 사용하는지 알아보고자 했다.

 

먼저 ArrayList와 LinkedList 각각에 대해 알아보자.

ArrayList

• ArrayList는 중복이 가능하다.
• ArrayList는 순서가 유지된다. 
  • index로 원소를 관리함.
• ArrayList는 크기가 고정되어있지 않다.
  • 동적으로 늘어나는 것이 아니라, 넘치게 되면 내부에서 일정 수만큼 늘려주게 됨.

add(E element) 

제일 뒤에 원소를 추가한다.

index로 원소를 관리하기 때문에 마지막 index의 원소 뒤에 넣기만 하면 된다. -> 빠름!

add(int index, E element)

원하는 index에 원소를 추가한다.

원하는 곳에 바로 넣을 수 있는 것은 좋지만 한 자리에 넣으려면 그 뒤에 있는 원소들은 칸을 확보하기 위해 뒤로 옮겨야한다. -> 느림!

remove(int index)

원하는 index 원소를 제거한다.

위의 add와 같은 맥락으로, 제거한 자리를 채우기 위해 앞으로 옮겨야한다. -> 느림!

get(int index)

index 위치의 원소를 가져온다.

index로 관리하기 때문에 빠르게 찾을 수 있다.

 

LinkedList

• LinkedList는 양방향 연결 리스트로, 순방향 역방향 모두 접근이 가능하다.
• LinkedList는 크기가 고정되어 있다.
  • 새로운 배열을 생성해 복사해야 함 (느림)
• LinkedList는 중간에 추가/삭제 시 빈공간을 만들고 채우기 위해 데이터 이동이 필요하다.

add(E element)

제일 뒤에 원소를 추가한다.

Head에서부터 마지막을 찾아야한다. -> 느림!

add(int index, E element)

원하는 index에 원소를 추가한다.

위의 add와 같이, Head에서부터 index 위치까지 찾아야한다. -> 느림!

remove(int index)

원하는 index의 원소를 제거한다.

ArrayList처럼 빈 공간을 채울 필요가 없다.

삭제하고 싶은 원소 앞/뒤로 가서 가리키는 값을 null로 변경하기만 하면 된다. -> 효율Good

get(int index)

index 위치의 원소를 가져온다.

이도 똑같이 Head에서부터 index까지 찾아야 한다.

 

Queue에서 LinkedList를 사용하는 이유

Queue는 선입선출 즉, FIFO구조이다.

 

ArrayList를 사용하게 된다면 어떨까?

맨 앞에 것을 꺼내야하는데, 꺼내고 나면 그 앞자리를 채우기 위해 모든 원소들을 한 칸씩 앞으로 옮겨야한다.

원소의 수가 많아지면 그만큼 비효율적인 것이다.

 

LinkedList를 사용하면 어떨까?

LinkedList의 remove 함수 설명을 보면 '빈 공간을 채울 필요가 없다'고 되어있다.

삭제하고 싶은 원소를 null로 변경하기만 하면 되기때문에 매우 효율적이다.

 

 

하나를 써도 이유는 알고 써야하지 않을까 해서 찾아보았다.

 

참고

https://github.com/wjdrbs96/Today-I-Learn/blob/master/Java/Collection/List/ArrayList%20vs%20LinkedList.md