ArrayList와 LinkedList
ArrayList
ArrayList는 List 인터페이스를 구현하는 컬렉션 클래스로 데이터의 저장순서가 유지되고 중복을 허용한다. 내부의Object 배열을 이용해서 데이터를 순차적으로 저장하는데 배열에 더 이상 저장할 공간이 없으면 보다 큰 새로운 배열을 생성해서 기존의 배열에 저장된 내용을 새로운 배열로 복사한 다음에 저장한다. 기존의 Vector를 개선한 것으로 Vector와 구현 원리와 기능적인 측면에서 비슷하지만 동기화 되지 않는다는 점이 다르다. 하지만 자바에서는 Vector와 같이 오래된 컬렉션 클래스 사용을 지양하도록 권고하고 있다(참고: Avoiding Using Old Interfaces and Implementations).
ArrayList의 요소를 삭제하는 경우 삭제할 객체의 바로 다음 데이터를 한 칸씩 앞으로 복사해서 삭제할 객체를 덮은 후 마지막 데이터는 null로 변경하는 방식으로 처리한다. 만일 삭제할 객체가 마지막 데이터라면 복사할 필요 없이 단순히 null로 대체한다. 새로운 요소를 추가할 때도 먼저 추가할 위치 이후의 요소들을 모두 한 칸씩 이동시킨 후 저장한다. 따라서 객체를 순차적으로 저장할 때와 마지막 데이터부터 삭제하면 데이터를 복사해서 옮기지 않아도 되기 때문에 작업 시간이 단축되지만, 배열의 중간에 위치한 객체에 대한 작업인 경우 다른 데이터의 위치를 이동시켜야 하기 때문에 다루는 데이터가 많을수록 작업 시간이 길어지게 된다.
ArrayList arrayList = new ArrayList<>(5);
for (int i = 0; i < 5; i++) {
arrayList.add(i); // ArrayList에 요소 추가
}
System.out.println(Arrays.toString(arrayList.toArray()));
while (!arrayList.isEmpty()) {
arrayList.remove(0); // ArrayList에 요소 삭제
System.out.println(Arrays.toString(arrayList.toArray()));
}- 실행 결과
LinkedList
배열은 가장 기본적인 형태의 자료구조로 구조가 간단하며 사용하기 쉽고 데이터를 읽어 오는데 걸리는 시간(접근 시간, access time)이 가장 빠르다는 장점을 가지고 있지만 다음과 같은 단점도 가지고 있다.
- 크기를 변경할 수 없음.
- 크기를 변경할 수 없으므로 새로운 배열을 생성해서 데이터를 복사해야 함.
- 새로운 배열로 복사해서 옮기는 작업을 줄이고 실행 속도를 향상시키기 위해서는 충분히 큰 크기의 배열을 생성해야 하므로 메모리가 낭비됨.
- 비순차적인 데이터의 추가 또는 삭제가 오래 걸림.
- 차례대로 데이터를 추가하거나 마지막에서부터 데이터를 삭제하지 않고 배열의 중간에서 작업하려면 다른 데이터의 복사 및 이동이 필요
이러한 배열의 단점을 보완하기 위해 연결 리스트(Linked List)라는 자료구조가 고안되었다. 배열은 모든 데이터가 연속적으로 존재하지만 연결 리스트는 불연속적으로 존재하는 데이터를 서로 연결한 형태의 구조를 가지고 있다.
연결 리스트의 각 요소(node)들은 자신과 연결된 다음 요소에 대한 참조(주소값)와 데이터로 구성되어 있다.
연결 리스트에서 데이터를 삭제하려면 삭제하고자 하는 요소의 이전 요소가 삭제하고자 하는 요소의 다음 요소를 참조하도록 변경하면 된다. 배열처럼 데이터를 이동하기 위해 복사하는 과정 없이 단 하나의 참조만 변경하면 삭제되므로 처리 속도가 빠르다
새로운 데이터를 추가할 때는 새로운 요소를 생성한 다음 추가하고자 하는 위치의 이전 요소의 참조를 새로운 요소에 대한 참조로 변경한 후 새로운 요소가 그 다음 요소를 참조하도록 하면 된다.
ArrayList vs. LinkedList
배열은 각 요소들이 연속적으로 메모리상에 존재하기 때문에 간단한 계산으로 원하는 요소의 주소를 얻어 데이터에 접근할 수 있지만 연결 리스트는 각 요소의 위치가 불연속적이기 때문에 처음부터 n번째 데이터까지 차례대로 따라가야만 원하는 값을 얻을 수 있다. 따라서 연결 리스트는 저장해야하는 데이터의 개수가 많아질수록 데이터를 읽어 오는 시간이 길어지는 단점이 있다.
| 컬렉션 | 읽기(접근 시간) | 추가 / 삭제 | 비고 |
|---|---|---|---|
| ArrayList | 빠름 | 느림 | - 순차적인 추가 / 삭제는 더 빠름 |
| - 비효율적인 메모리 사용 | |||
| LinkedList | 느림 | 빠름 | - 데이터가 많을 수록 접근성이 떨어짐 |
References
