컬렉션 프레임워크 - LinkedList

Algorithmday_3 정리 (2021.11.30 화요일)

LinkedList

• List 구현 클래스이므로 ArrayList와 사용 방법은 동일
• 내부 구조 다름
• ArrayList : 배열로 만들어져 있어서 인덱스 사용
• LinkedList : 인접 참조를 링크해서 체인처럼 관리 (이전/다음 객체의 주소 갖고 있음)
• 특정 인덱스에서 객체를 제거하거나 추가하게 되면 바로 앞뒤 링크만 변경
• 빈번한 객체 삭제와 삽입이 일어나는 곳에서는 ArrayList보다 성능 좋음
• 순차적으로 추가/삭제 시
  • ArrayList가 LinkedList 보다 빠름
  • ArrayList가 용량이 충분하면 더 빠르지만 충분하지 않으면 새로운 크기의 ArrayList를 생성하고 데이터를 복사는 일이 발생해서 순차적으로 데이터를 추가해도 ArrayList가 더 느릴 수 있음
    • 충분한 용량 확보 중요
  • 마지막 데이터부터 역순으로 삭제해 나가면 각 요소들을 재배치할 필요가 없기 때문에 더 빠름
• 중간 데이터 추가/삭제 시
  • 링크만 변경해주면 되기 때문에 LinkedList가 훨씬 빠르다.
  • ArrayList는 삭제 후 각 요소들을 재배치하기 때문에 처리 속도가 늦다.

LinkedList 예제

public class LinkedListEx1 {
    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();
        //순차적으로 추가하기
        //ArrayList : 90
        //LinkedList : 210

        System.out.println("중간에 추가하기");
        System.out.println("ArrayList : " + add2(al));
        System.out.println("LinkedList : " + add2(ll));
        System.out.println();
        //중간에 추가하기
        //ArrayList : 2009
        //LinkedList : 11

        System.out.println("중간에서 삭제하기");
        System.out.println("ArrayList : " + remove2(al));
        System.out.println("LinkedList : " + remove2(ll));
        System.out.println();
        //중간에서 삭제하기
        //ArrayList : 1310
        //LinkedList : 110

        System.out.println("순차적으로 삭제하기");
        System.out.println("ArrayList : " + remove1(al));
        System.out.println("LinkedList : " + remove1(ll));
        System.out.println();
        //순차적으로 삭제하기
        //ArrayList : 7
        //LinkedList : 29
    }
    // 순차적으로 추가
    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;
    }
    //중간 데이터 삭제하기
    // 처음 0 삭제, 이동. 1삭제, 이동, 2삭제, ...
    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;
    }
}