[Java Basic] 32 - 컬렉션 프레임워크2 (ArrayList, LinkedList)

 

 

 

지난 번 컬렉션 프레임워크 개요와 Vector에 대한 포스팅을 진행하면서, Vector는 컬렉션 프레임워크 등장 전 배열을 쉽게 다루기 위한 클래스라는 것을 설명했다. 그리고 이 Vector마저도 사용상의 개선사항이 존재했기 때문에, Java에서 컬렉션 프레임워크 등장과 함께, 기능이 개선된 클래스인 ArrayList가 발생했음을 함께 언급했다.

 

이번 포스팅에서는 데이터 집단을 다루기 위한 컬렉션 프레임워크인 ArrayList와 LinkedList에 대해 알아보려 한다. ArrayList와 LinkedList는 둘 다 List 인터페이스에 속하는, 일종의 배열 형태의 객체지만, 데이터 저장 방식이 조금 차이가 있으며 이로 인해 데이터 조회와 처리에 있어서도 장/단점이 뚜렷하다.

 

하나씩 살펴보자.

 

 

 

1. ArrayList

 

ArrayList는 Vector에서 파생된 컬렉션 프레임워크 객체고, Vector는 배열로부터 파생된 객체다. 따라서 ArrayList 역시 배열 및 Vector와 사용법이 매우 유사하다. 

 

ArrayList는 Vector과 동일한 방식의 생성자를 가진다. 크게 세 가지 방식이 있는데, 기본 생성자, 매개변수로 정수를 받는 생성자 그리고 매개변수로 Collection 인터페이스 객체를 받는 생성자가 있다. 세 가지 생성자의 사용 방법은 아래와 같다.

 

 

 

ArrayList의 경우 기본 생성자로 인스턴스를 생성하면 초기 Capacity, 즉 배열의 크기가 10으로 설정된다. 하지만, 이 Capacity의 크기를 조회할 수 있는 기능을 가진 ArrayList의 매서드는 존재하지 않는다. 그럼에도 불구하고, trimToSize()와 같이 불필요한 배열을 없애주는 메서드는 제공된다. 

 

 

 

배열의 최소 크기를 결정하는 ensureCapacity() 매서드를 사용하여 배열의 크기를 줄이고 모든 값을 삭제하더라도, 최소 크기만큼 null 값이 저장되지는 않는다. Vector와 ArrayList 모두 toString() 매서드로 출력 시 저장된 데이터만 나열하여 출력할 뿐, 배열의 크기와 관련된 내용은 다루지 않기 때문에 최소 배열 크기가 정해진 상태에서 배열 내 모든 요소를 삭제하더라도 단순히 "[]"로 출력된다. 

 

ArrayList의 매서드도, 배열과 Vector를 다루어 봤다면 크게 설명할 것이 없다. 다음으로 LinkedList에 대해 알아보고, ArrayList와 LinkedList 사이 차이점을 살펴보려 한다.

 

 

 

 

2. LinkedList

 

LinkedList는 이름의 접미사 부분이 List라 마치 배열과 같은 형태를 띄지 않을까 생각하는 분들이 많을텐데, 데이터가 저장되는 모양을 보면 배열과는 영 딴판이다. 이 LinkedList는 기본형 타입 변수들이 값을 저장하는 것과 비슷하게 요소들을 메모리에 저장한다. 즉, LinkedList에 포함이 되어 있는 요소끼리도 메모리 주소가 근접해있지 않다. 하지만, LinkedList 내부에는 다음 요소가 저장된 메모리의 주소가 각 요소마다 저장되어 있다. 극단적으로 단순한 그림으로 나타내면 아래와 같다.

 

 

 

위의 그림을 예시로 들면, LinkedList의 첫 요소는 문자열 'W'다. 이 첫 요소는 문자열이라는 데이터 뿐만 아니라, 다음 요소의 메모리 주소 정보, 즉 문자열 'o'가 저장된 메모리의 주소도 저장하고 있다. 마찬가지로 두 번째 요소는 데이터인 문자열 'o'와 다음 요소의 데이터가 저장된 메모리 주소인 'ox302'를 저장한다. 세 번 째 요소도 마찬가지. 마지막 요소는 자기 자신이 마지막이기 때문에 다음 메모리 주소를 저장하는 값이 null로 되어 있다. 

 

LinkedList 역시 앞서 살펴본 ArrayList와 인스턴스 생성 방식이 유사하다. 필자가 '유사하다'라는 단어를 쓴 이유는 LinkedList의 경우 매개 변수로 배열 크기값을 입력받는 생성자가 없기 때문이다.

 

 

 

 

LinkedList 역시 List의 일종이기 때문에 Vector, ArrayList와 동일한 이름의 메서드를 공유한다. 하지만 LinkedList의 경우 기능이 추가된 몇몇 매서드를 더 제공한다. 이 매서드들은 peek(), poll(), pop() 이며 LinkedList 내의 값을 추출하는 기능을 한다..

 

 

 

먼저 peek()을 보자. 위의 documentation 문서에 설명한 내용을 보면 peek()의 경우 가장 첫 요소 값을 반환하나 LinkedList 내에서 삭제하지 않는다고 되어 있다. peekFirst()는 peek()과 동일한 기능을 하나, peekLast()의 경우 반대로 LinkedList의 가장 마지막에 위치한 요소를 반환한다. 이들이 반환하는 객체 타입이 Object(E)기 때문에 String이나 기타 기본형 타입으로 변환하기 위해서는 반환된 값에 형 변환(Type Casting)을 진행해야 한다.

 

 

 

 

 

poll() 매서드는 peek()과 유사하나, LinkedList 내에서 추출한 값을 삭제한다는 점이 다르다. 마찬가지로 pop() 매서드 역시 poll()과 동일한 역할을 한다. 하지만 poll() 매서드는 peek()이나 poll()과 달리 유사 계열의 매서드(First / Last)를 갖지 않는다.

 

 

poll()과 pop()이 동일 기능을 담당하고 있음을 확인할 수 있다.

 

 

 

그럼, 여기서 의문이 생긴다. 도대체 LinkedList를 만든 이유는 무엇일까? ArrayList와 동일한 역할을 하는데 말이다.

 

 

 

3. ArrrayList와 LinkedList 비교

 

 

ArrayList는 배열과 비슷한 형태로 데이터가 저장되나, LinkedList는 ArrayList와 달리 메모리에 널려있는 데이터의 주소를 참조하는 별도의 데이터가 존재함을 바로 위에서 언급했다. 그렇기 때문에 ArrayList와 LinkedList는 데이터 작업 종류에 따른 효율에 차이가 존재할 수 밖에 없다. 

 

 

(1) 순차적인 데이터 추가(삭제)

 

1부터 2000000까지의 숫자를 ArrayList와 LinkedList에 저장한다고 해보자. 필자는 ArrayList와 LinkedList가 이 값들을 추가하는데 걸리는 시간을 측정할 것이다(원래 int의 최댓값까지 넣는 것으로 하려고 했는데, 메모리 부족으로 프로그램이 돌지를 않는다. 값을 아주 조금 더 줄여서 돌렸는데, 노트북 폭발하는 줄 알았다...). 코드는 아래와 같다.

 

결과에 나타난 소요 시간의 단위는 MilliSecond(ms)다.

 

ArrayList가 순차적인 데이터 저장은 LinkedList에 비해 훨씬 빠르다. 당연한 것이, ArrayList는 데이터 집단을 연속된 메모리 공간에 할당해서 넣는 반면, LinkedList는 메모리 이곳저곳에 산재한 자료들을 포인터(메모리 주소를 가리키는 것으로 Java에서는 다루지 않는다)로 일일이 연결해주어야 하기 때문이다. clear()를 통한 데이터의 삭제도 마찬가지로 LinkedList가 ArrayList보다 처리 속도가 느리다. 지금이야 고작(?) 2백만개의 데이터만, 그것도 정수만 테스트했기에 큰 차이가 나지 않는것처럼 보이나, 데이터의 양이 더욱 많아진다면 그 차이는 점점 벌어질 것이다. 실제로 영세한 IT 업체에서 다루는 통신 데이터의 양만 하더라도 생각보다 꽤 된다는 점을 고려한다면 LinkedList는 자료 저장부터 문제가 될 가능성이 매우 높다. 

 

그럼에도 불구하고 LinkedList를 왜 쓸까? 이제 각 List의 중간에 위치한 값을 삭제하거나 새 값을 중간에 삭제하는데 걸리는 시간을 알아보자.

 

 

 

(2) 값의 추가 및 삭제

 

위에서 만든 ArrayList와 LinkedList를 그대로 둔 채, 중간 값인 100000을 삭제해보려고 한다. 삭제되는데 걸리는 시간은 동일한 방식으로 측정한다.

 

 

삭제에 걸린 시간은 ArrayList가 8ms, LinkedList가 2ms로 LinkedList가 더 빠르다. 왜 그럴까? 값이 삭제되는 과정을 살펴보자. 

 

특정 값을 삭제한다고 remove() 매서드를 호출하게 되면, ArrayList와 LinkedLIst 모두 0번 index부터 저장된 값을 순차적으로 찾아 들어가기 시작한다. 물론, 이 과정은 ArrayList가 LinkedList에 비해 빠를 수 밖에 없다. 저장된 값이 인접 메모리에 위치하고 있으니까 말이다.

 

검색과 관련된 작업은 ArrayList가 더 빠르다.

 

하지만 값을 삭제한 뒤, 삭제된 값 뒤의 요소들을 재배치하는 과정은 ArrayList가 불리할 수 밖에 없다. 아무리 ArrayList가 배열에 특화된 클래스라고 하긴 해도, 근본이 배열인 이상 삭제된 값의 앞, 뒤 요소들을 별도로 추출해서 새로운 배열에 복사해 넣어야 하기 때문이다.

 

 

 

반면 LinkedList는 삭제되는 값 앞의 요소에 저장된, 다음 요소의 메모리 주소를 단순히 삭제된 바로 다음의 요소값이 저장된 메모리 주소로만 변경하면 된다. 

 

 

삭제 뿐만이 아니라 추가도 마찬가지다. ArrayList는 다시 추가되는 지점 앞의 배열을 복사하고 값을 추가하고 나머지 배열을 복사해 넣어야하지만, LinkedList는 단지 추가 저장된 값의 메모리 주소를 이전 요소에 저장하고, 추가된 요소에 다음 요소 메모리 주소를 저장하면 끝이기 때문이다. 

 

LinkedList에서 데이터 연결부분만 구현하면 위와 같다. 추가 기능 및 변수가 들어가면 LinkedList와 동일하게 동작할 수 있다.

 

 

따라서 List의 중간에 위치한 값을 추가하거나 삭제하는 작업이 빈번한 프로그램은 LinkedList가 유리하다. 

 

 

---

 

 

정리하자면, 대량의 자료를 순차적으로 추가, 삭제하거나 데이터의 수정, 검색은 ArrayList가 훨씬 더 효율적이지만, 대량의 데이터 중간에 위치한 값을 추가하거나 삭제하는 작업은 LinkedLIst가 더 효율적이다. 

 

다음 포스팅에서는 컬렉션 프레임워크의 또 다른 종류인 Stack과 Queue에 대해 알아보려 한다.

 

 

 

Fin.