컬렉션 프레임워크(3) List 인터페이스 - LinkedList

컬렉션 프레임워크(Collection Framework)

LinkedList

• List 구현 클래스이므로 ArrayList와 사용 방법은 동일
• 내부 구조가 다르다
• ArrayList: 배열로 만들어져 있어서 인덱스 사용
• LinkedList: 인접 참조를 링크해서 체인처럼 관리 (이전/다음 객체의 주소 갖고 있음)
• 특정 인덱스에서 객체를 제거하거나 추가하게 되면 바로 앞뒤 링크만 변경
• 빈번한 객체 삭제와 삽입이 일어나는 곳에는 ArrayList보다 성능 좋음

순차적으로 추가/삭제 할 경우

• ArrayList가 LInkedList보다 빠름
• ArrayList가 용량이 충분하면 더 빠르지만 충분하지 않으면 새로운 크기의 ArrrayList를 생성하고 데이터를 복사하는 일이 발생하기 때문에 순차적으로 데이터를 추가해도 ArrayList가 더 느릴 수 있음
• 충분한 용량 확보 중요
• 순차적으로 삭제 시 마지막 데이터부터 역순으로 삭제해 나가면 각 요소들을 재배치할 필요가 없기 때문에 더 빠르다

중간 데이터를 추가/삭제 할 경우

• LinkedList가 훨씬 빠름
• 연결(링크)만 변경해주면 되기 때문에 처리 속도가 상당히 빠름
• ArrayList는 삭제 후 각 요소들을 재배치하기 때문에 속도 늦음

LinkedList 예제

LinkedListEx1.java

package linkedlist;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

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("ArrayList : "+add2(ll));

        System.out.println("순차적으로 삭제하기");
        System.out.println("ArrayList: "+remove1(al));
        System.out.println("ArrayList: "+remove2(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 < 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;
    }

    // 중간 데이터 삭제하기
    // 처음 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;
    }
}