이 글은 남궁성님의 자바의 정석 3/e를 기반으로 공부한 내용을 정리한 글입니다.
Collection
은 모든 자료구조가 구현(implement)하는 인터페이스입니다. 아래 배우는 모든 자료구조에 해당하는 클래스, 인터페이스는 언제나 Collection
인터페이스를 구현하고 있습니다.
기존의 Vector를 개선한 것, 배열을 이용해서 데이터를 순차적으로 저장
배열을 이용하기 때문에 저장, 조회에는 용이하나 용량을 변경하면 새로운 배열을 생성해야돼서 효율성이 떨어짐
배열의 중간에 위치한 객체를 추가하거나 삭제하는 경우 System.arraycopy()
를 호출해서 다른 데이터의 위치를 이동시켜 줘야 하기 때문에 작업시간이 오래걸린다.
불연속적으로 존재하는 데이터를 서로 연결(link)한 형태로 구성
링크드리스트의 각 요소(node)들은 자신과 연결된 다음 요소에 대한 참조(주소값)와 데이터로 구성
링크드리스트는 이동방향이 단방향이기 때문에, 다음 요소에대한 접근은 쉽지만 이전 요소에 대한 접근은 어려움 -> 이를 보완한 것이 더블링크드리스트
package Chapter11.day22;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
public class ArrayListLinkedListTest {
public static void main(String[] args) {
// 추가할 데이터의 개수를 고려하여 충분히 잡아야한다.
ArrayList al = new ArrayList(2000000);
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("LinkedList: "+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));
System.out.println();
}
public static long add1(List list) {
long start = System.currentTimeMillis();
for (int i = 0; i < 1000000; i++) list.add(i+"");
long end = System.currentTimeMillis();
return end - start;
}
public static long add2(List list) {
long start = System.currentTimeMillis();
for (int i = 0; i < 1000000; i++) list.add(500+"X");
long end = System.currentTimeMillis();
return end - start;
}
public static 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;
}
public static 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: 119
LinkedList: 160
= 중간에 추가하기 =
ArrayList: 16
LinkedList: 161
= 중간에서 삭제하기 =
ArrayList: 5859
LinkedList: 289
= 순차적으로 삭제하기 =
ArrayList: 17
LinkedList: 45
결론1 순차적으로 추가/삭제하는 경우에는 ArrayList가 빠름
결론2 중간 데이터를 추가/삭제하는 경우에는 LinkedList가 빠름
컬렉션 | 읽기(접근시간) | 추가 / 삭제 | 비 고 |
---|---|---|---|
ArrayList | 빠르다 | 느리다 | 순차적인 추가삭제는 더 빠름. 비효율적인 메모리 사용 |
LinkedList | 느리다 | 빠르다 | 데이터가 많을수록 접근성이 떨어짐 |