큐 ( Queue ) 가 ArrayList가 아닌 Linkedlist를 쓰는이유

우선 주제를 생각하기전에 ArrayList 와 LinkedList의 차이점을 집고 넘어가겠다

 

ArrayList

 

ArrayList는 중복을 허용하고 순서를 유지하며 인덱스로 원소들을 관리한다는 점에서 배열과 상당히 유사하다.

배열은 크기가 지정되면 고정되지만 ArrayList는 클래스이기 때문에 배열을 추가, 삭제 할 수 있는 메소드들도 존재한다.

 

단. 배열,데이터를 추가 할 시에 배열의 크기가 늘어나는 것이 아니라, 기존 가득찼던 데이터들을 복사하여

배열의 크기를 늘린 곳에 다시 붙여넣는 방식이다.

 

다시말해

1

2

3

의 배열에 4와 5의 데이터를 추가한다고 생각하면

 

첫번째로 위와같은 확장된 배열을 만들고

 

1

2

3

4

5

기존의 데이터와 추가할 데이터를 합치고 그를 복사 붙여넣기 한다.

 

따라서 만약 ArrayList사용하여 작업하고 있을 경우에는 위와같은 작업과정을 거치며 시간을 소비하게 두기 보다는

ArrayList 를 만들때 초기 용량을 설정해 두고 하는것이 좋다고 볼 수 있겠다.

 

 

 

LinkedList

LinkedList는 내부적으로 양방향의 연결 리스트로 구성되어 있어서 참조하려는 원소에 따라 처음부터 순방향으로 또는 역순으로 순회할 수 있다. (기존 배열의 단점을 보완하기 위해서 링크드리스트(Linked list)라는 형태가 나오게 된것.)

 

ArrayList의 예시처럼 예를 들어보자

 

앞서 설명했다 싶이 LinkedList는 양방향의 연결 리스트로 구성되어 있어 앞 뒤 구분이 흐릿하다고 보면된다.

LinkedList에서 방향은 원소 값을 찾아 앞뒤를 찾는다고 보면 된다는 것

 

1

만일 1,2 라는 데이터를 LinkedList를 이용하여 사용하게된다면 위,아래와 같은 형태를 생각하면 되겠다

 

2

이 둘의 데이터를 ArrayList로 사용하게되었더라면

 

1

2

이러한 형태에서 그치고 말았을것

 

허나 LinkedList는 모두가 한칸씩 떨어져있다는 생각을 하면 이해하기 쉬울것이다.

1

2

3

4

위와 같은 형태가 되겠는데 나누어서 보자면

 

1

Space

2

이러한 형태일 것이다

 

이때 Space는 1의 Next Link Field가 될것이고 동시에 2의 Previous Link Field가 될것이다

따라서 LinkedList에서의 데이터 편집은 원소의 위치를 찾게되면 순방향이던 역방향이던 문제가 없게되는 것이다

 

 

간단 정리

간단히 ArrayList와 LinkedList의 기능을 정리하자면 아래와같다

 

• 순차적으로 데이터를 추가할시

ArrayList  LinkedList - 차이 거의 없음

 

• 순차적으로 데이터를 삭제할시

ArrayList  LinkedList - 차이 거의 없음

 

• 데이터 중간에 데이터를 추가할시

ArrayList < LinkedList 

중간에서 추가하기위해서는 ArrayList는 중간에 빈공간을 만들어야 하는 반면 LinkedList는 원소값만 알면 빠르게 해결가능하다

 

• 데이터 중간에 데이터를 삭제할시

ArrayList < LinkedList 

중간에서 삭제하기위해서는 ArrayList는 중간에 빈공간이 만들어지기에 이를 채우기 위해서 원소들의 이동이 일어나는 반면 LinkedList는 원소값만 알면 빠르게 해결가능하다

 

 

 

 

자 이를 바탕으로 왜 Queue가 ArrayList가 아닌 LinkedList를 쓰는지 알아보자

 

큐의 구조는

이와같이 한쪽으로만 데이터가 들어가고 한쪽으로 데이터가 나가는 일방향 적인 구조를 가지고 있다.

 

즉, 큐를 사용시에 일어나는 데이터 변화는

항상 첫번째 데이터가 삭제되는 형식이기에 ArrayList를 사용하게 되면 빈 첫번째 공간을 메꾸기 위해 원소들이 모조리 이동해야하는 불상사가 일어난다

 

그렇기 때문에 큐 ( Queue ) 는 ArrayList 보다 데이터의 추가,삭제가 편리한 LinkedList를 이용하는것이 좋다