컬렉션 프레임워크 - LinkedList
◎ LinkedList
-> 배열은 구조가 간단하여 사용하기 쉽고, 데이터를 읽어오는데 걸리는 시간이 빠르다.
-> 하지만 배열은 크기를 변경할 수 없기 때문에 새로운 배열을 생성하여 복사하고 참조를 변경하는 과정을 거쳐야하기 때문에 메모리 낭비가 발생한다.
-> 배열은 차례대로 데이터를 추가하고 마지막에서부터 데이터를 삭제하는 것은 빠르지만 배열 중간에서 데이터를 추가하거나 삭제하면 빈자리를 만들기 위해 다른 데이터들을 복사하는 과정을 거쳐야한다.
-> 배열의 단점을 정리하면 다음과 같다.
1. 크기 변경할 수 없다.
2. 비순차적인 데이터의 추가나 삭제에 많은 시간이 걸린다.
-> LinkedList는 이러한 배열의 단점을 보완하기 위해 사용된다.
-> LinkedList는 불연속적으로 존재하는 데이터를 서로 연결한 형태로 구성되어 있다.
-> LinkedList의 각 요소(node)들은 자신과 연결된 다음 요소에 대한 참조와 데이터로 구성되어 있다.
class Node{
Node next; // 다음 요소의 주소 저장
Object obj; // 데이터 저장
}-> LinkedList의 삭제는 삭제하려는 요소의 이전요소가 삭제하려는 요소의 다음 요소를 참조하도록 변경하면 된다.
-> 추가는 새로운 요소를 생성하여 추가하려는 위치의 이전 요소의 참조를 새로운 요소에 대한 참조로 변경하고, 새로운 요소가 그 다음 요소를 참조하도록 변경하면 된다.
-> LinkedList는 이동방향이 단방향이기 때문에 다음 요소에 대한 접근은 용이하지만 이전 요소에 대한 접근이 어렵다.
-> 더블 링크드 리스트는 요소 간 이중연결을 하여 LinkedList의 이전 요소에 대한 접근이 어렵다는 문제를 보완하였다.
class Node{
Node next; // 다음 요소의 주소 저장
Node previous; // 이전 요소의 주소 저장
Object obj; // 데이터 저장
}
-> 더블 링크드 리스트보다 접근성을 더 향상시킨 것이 '더블 써큘러 링크드 리스트'다.
-> 더블 써큘러 링크드 리스트는 더블 링크드 리스트의 첫 번째 요소와 마지막 요소를 연결한 것이다.
◎ ArrayList vs LinkedList
-> 순차적으로 데이터를 추가/삭제하는 경우에는 ArrayList가 더 빠르다.
-> 비순차적으로 데이터를 추가/삭제하는 경우에는 LinkedList가 더 빠르다.
실험
import java.util.*;
public class ArrayLinkedList_VS_LinkedList {
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));
}
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<10000;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가 빠르고, 비순차적인 추가/삭제에서는 LinkedList가 더 빠른 것을 알 수 있다.
★ 참고 및 출처
자바의 정석(3판)