ArrayList
ArrayList는 컬렉션 프레임워크에서 가장 많이 사용되는 컬렉션 클래스일 것이다. 이 ArrayList는 List 인터페이스를 구현하기 때문에 데이터의 저장순서가 유지되고 중복을 허용한다는 특징을 갖는다.
ArrayList는 기존의 Vector를 개선한 것으로 Vector와 구현원리와 기능적인 측면에서 동일하다고 할 수 있다. 앞에서 얘기했던 것과 같이 Vector는 기존에 작성된 소스와의 호환성을 위해서 계속 남겨 두고 있을 뿐이기 때문에 가능하면 Vector보다는 ArrayList를 사용하자.
ArrayList는 Object배열의 0번째 위치에 저장되고 그 다음에 저장하는 객체는 1번째 위치에 저장된다. 이런 식으로 계속 배열에 순서대로 저장되며, 배열에 더 이상 저장할 공간이 없으면 보다 큰 새로운 배열을 생성해서 기존의 배열에 저장된 내용을 새로운 배열로 복사한 다음에 저장된다.
ArrayList는 elementData라는 이름의 Object 배열을 멤버변수로 선언하고 있다는 것을 알 수 있다. 선언된 배열의 타입이 모든 객체의 최고조상인 Object이기 때문에 모든 종류의 객체를 담을 수 있다.
void collectionPrac() {
ArrayList list1 = new ArrayList(10);
list1.add(new Integer(5));
list1.add(Integer.valueOf(4));
list1.add(Integer.valueOf(2));
list1.add(Integer.valueOf(0));
list1.add(Integer.valueOf(1));
list1.add(Integer.valueOf(3));
ArrayList list2 = new ArrayList(list1.subList(1, 4));
print(list1, list2);
Collections.sort(list1); // list1과 list2를 정렬한다.
Collections.sort(list2);
print(list1, list2);
System.out.println("list1.containAll(list2) : " + list1.containsAll(list2));
list2.add("B");
list2.add("C");
list2.add(3, "A");
print(list1, list2);
list2.set(3, "AA");
print(list1, list2);
// list1에서 list2와 겹치는 부분만 남기고 나머지는 삭제한다.
System.out.println("list1.retainAll(list2) : " + list1.retainAll(list2));
print(list1, list2);
// list2에서 list1에 포함된 객체들을 삭제한다.
for (int i=list2.size() - 1; i >= 0; i--) {
if (list1.contains(list2.get(i))) {
list2.remove(i);
}
}
print(list1, list2);
}
void print(ArrayList list1, ArrayList list2) {
System.out.println("list1 = " + list1);
System.out.println("list2 = " + list2);
System.out.println();
}
실행결과
list1 = [5, 4, 2, 0, 1, 3]
list2 = [4, 2, 0]
list1 = [0, 1, 2, 3, 4, 5]
list2 = [0, 2, 4]
list1.containAll(list2) : true
list1 = [0, 1, 2, 3, 4, 5]
list2 = [0, 2, 4, A, B, C]
list1 = [0, 1, 2, 3, 4, 5]
list2 = [0, 2, 4, AA, B, C]
list1.retainAll(list2) : true
list1 = [0, 2, 4]
list2 = [0, 2, 4, AA, B, C]
list1 = [0, 2, 4]
list2 = [AA, B, C]LinkedList
배열은 가장 기본적인 형태의 자료구조로 구조가 간단하며 사용하기 쉽고 데이터를 읽어 오는데 걸리는 시간 (접근시간, access time)이 가장 빠르다는 장점을 가지고 있지만 다음과 같은 단점도 가지고 있다.
- 크기를 변경할 수 없다.
- 크기를 변경할 수 없으므로 새로운 배열을 생성해서 데이터를 복사해야한다.
- 실행속도를 향상시키기 위해서는 충분히 큰 크기의 배열을 생성해야 하므로 메모리가 낭비된다.
- 비순차적인 데이터의 추가 또는 삭제에 시간이 많이 걸린다.
- 차례대로 데이터를 추가하고 마지막에서부터 데이터를 삭제하는 것은 빠르지만, 배열의 중간에 데이터를 추가하려면, 빈자리를 만들기 위해서 다른 데이터들을 복사해서 이동해야 한다.
이러한 배열의 단점을 보완하기 위해서 링크드 리스트(linked list)라는 자료구조가 고안되었다. 배열은 모든 데이터가 연속적으로 존재하지만 링크드 리스트는 불연속적으로 존재하는 데이터를 서로 연결(link)한 형태로 구성되어 있다.
링크드 리스트의 각 요소(node)들은 자신과 연결된 다음 요소에 대한 참조(주소값)와 데이터로 구성되어 있다.
링크드 리스트에서의 데이터 삭제는 간단하다. 삭제하고자 하는 요소의 이전요소가 삭제하고자 하는 요소의 다음 요소를 참조하도록 변경하기만 하면 된다. 단 하나의 참조만 변경하면 삭제가 이루어지는 것이다. 배열처럼 데이터를 이동하기 위해 복사하는 과정이 없기 때문에 처리속도가 매우 빠르다.
새로운 데이터를 추가할 때는 새로운 요소를 생성한 다음 추가하고자 하는 위치의 이전 요소의 참조를 새로운 요소에 대한 참조로 변경해주고, 새로운 요소가 그 다음 요소를 참조하도록 변경하기만 하면 되므로 처리속도가 매우 빠르다.
링크드 리스트는 이동방향이 단방향이기 때문에 다음 요소에 대한 접근은 쉽지만 이전요소에 대한 접근은 어렵다. 이 점을 보완한 것이 더블 링크드 리스트 (이중 연결리스트, doubly linked list)이다.
더블 링크드 리스트는 단순히 링크드 리스트에 대한 참조변수를 하나 더 추가하여 다음 요소에 대한 참조뿐 아니라 이전 요소에 대한 참조가 가능하도록 했을 뿐, 그 외에는 링크드 리스트와 같다.
더블 링크드 리스트는 링크드 리스트보다 각 요소에 대한 접근과 이동이 쉽기 때문에 링크드 리스트보다 더 많이 사용된다.
더블 링크드 리스트의 접근성을 보다 향상시킨 것이 '더블 써큘러 링크드 리시트(이중 원형 연결리스트, doubly circular linked list)'인데, 단순히 더블 링크드 리스트의 첫 번째 요소와 마지막 요소를 서로 연결시킨 것이다. 이렇게 하면, 마지막요소의 다음요소가 첫 번째 요소가 되고, 첫 번째 요소의 이전 요소가 마지막 요소가 된다. 마치 TV의 마지막 채널에서 채널을 증가시키면 첫 번째 채널로 이동하고 첫 번째 채널에서 채널을 감소시키면 마지막 채널로 이동하는 것과 같다.
실제로 LinkedList 클래스는 이름과 달리 '링크드 리스트'가 아닌 '더블 링크드 리스트'로 구현되어 있는데, 이는 링크드 리스트의 단점인 낮은 접근성(accessability)을 높이기 위한 것이다.
순차, 중간 추가/삭제에 관한 예제
@Test
public void linkedListTest() {
// 추가할 데이터의 개수를 고려해서 충분히 잡아야한다.
ArrayList al = new ArrayList(4900000);
LinkedList ll = new LinkedList();
//
System.out.println("= 순차적으로 추가하기 =");
System.out.println("ArrayList : " + add1(al));
System.out.println("LinkedList : " + add1(ll));
System.out.println();
System.out.println("= 중간에 추가하기 =");
System.out.println("ArrayList : " + add2(al));
System.out.println("LikedList : " + add2(ll));
System.out.println();
System.out.println("= 중간에서 삭제하기 =");
System.out.println("ArrayList : " + remove2(al));
System.out.println("LinkedList : " + remove2(ll));
System.out.println();
System.out.println("= 순차적으로 삭제하기 =");
System.out.println("ArrayList : " + remove1(al));
System.out.println("LinkedList : " + remove1(ll));
}
long add1(List list) {
long start = System.currentTimeMillis();
for (int i=0; i < 2000000; i++) {
list.add(i + "");
}
long end = System.currentTimeMillis();
return end - start;
}
long add2(List list) {
long start = System.currentTimeMillis();
for (int i=0; i < 10000; i++) {
list.add(500, "X");
}
long end = System.currentTimeMillis();
return end - start;
}
long remove1(List list) {
long start = System.currentTimeMillis();
for (int i=list.size() - 1; i >= 0; i--) {
list.remove(i);
}
long end = System.currentTimeMillis();
return end - start;
}
long remove2(List list) {
long start = System.currentTimeMillis();
for (int i=0; i < 10000; i++) list.remove(i);
long end = System.currentTimeMillis();
return end - start;
}
// 실행결과
= 순차적으로 추가하기 =
ArrayList : 52
LinkedList : 50
= 중간에 추가하기 =
ArrayList : 46777
LikedList : 10
= 중간에서 삭제하기 =
ArrayList : 45408
LinkedList : 154
= 순차적으로 삭제하기 =
ArrayList : 7
LinkedList : 18결론 1 : 순차적으로 추가/삭제하는 경우에는 ArrayList가 LinkedList보다 빠르다.
순차적으로 삭제한다는 것은 마지막 데이터부터 역순으로 삭제해나간다는 것을 의미하며, ArrayList는 마지막 데이터부터 삭제할 경우 각 요소들의 재배치가 필요하지 않기 때문에 상당히 빠르다, 단지 마지막 요소의 값을 null로만 바꾸면 되니까.
결론 2 : 중간 데이터를 추가/삭제하는 경우에는 LinkedList가 ArrayList보다 빠르다.
중간 요소를 추가 또는 삭제하는 경우, LinkedList는 각 요소간의 연결만 변경해주면 되기 때문에 처리속도가 상당히 빠르다. 반면에 ArrayList는 각 요소들을 재배치하여 추가할 공간을 확보하거나 빈 공간을 채워야하기 때문에 처리속도가 늦다.
접근 시간에 대한 예제
@Test
public void arrayListLinkedListTest() {
ArrayList al = new ArrayList(10000000);
LinkedList ll = new LinkedList();
add(al);
add(ll);
System.out.println("= 접근시간테스트 =");
System.out.println("ArrayList : " + access(al));
System.out.println("LinkedList : " + access(ll));
}
void add(List list) {
for (int i=0; i<10000000; i++) {
list.add(i+"");
}
}
long access(List list) {
long start = System.currentTimeMillis();
for (int i=0; i< 100000; i++) {
list.get(i);
}
long end = System.currentTimeMillis();
return end - start;
}
// 실행 결과
= 접근시간테스트 =
ArrayList : 1
LinkedList : 12349배열은 각 요소들이 연속적으로 메모리상에 존재하기 때문에 이처럼 간단한 계산만으로 원하는 요소의 주소를 얻어서 저장된 데이터를 곧바로 읽어올 수 있지만, LinkedList는 불연속적으로 위치한 각 요소들이 서로 연결된 것이라 처음부터 n번째 데이터까지 차례대로 따라가야만 원하는 값을 얻을 수 있다.
그래서 LinkedList는 저장해야하는 데이터의 개수가 많아질수록 데이터를 읽어 오는 시간,
즉 접근시간(access time)이 길어진다는 단점이 있다.
결과
ArrayList
- 접근시간 = 빠르다
- 추가 / 삭제 = 느리다
순차적인 추가삭제는 더 빠름. 비효율적인 메모리 사용.
LinkedList
- 접근시간 = 느리다
- 추가 / 삭제 = 빠르다
데이터가 많을수록 접근성이 떨어짐.
다루고자 하는 데이터의 개수가 변허지 않는 경우라면, ArrayList가 최상의 선택이 되겠지만, 데이터 개수의 변경이 잦다면 LinkedList를 사용하는 것이 더 나은 선택이 될 것이다.
두 클래스의 장점을 이용해서 두 클래스를 조합해서 사용하는 방법도 생각해 볼 수 있다. 처음에 작업하기 전에 데이터를 저장할 땐 ArrayList를 사용한 다음, 작업할 때는 LinkedList로 데이터를 옮겨서 작업하면 좋은 효율을 얻을 수 있을 것이다.
