[Collection FrameWork] ArrayList, LinkedList

ArrayList 

List 인터페이스를 구현한 클래스로, 가장 많이 사용되는 컬렉션 클래스.

• 저장 용량을 초과하여 객체들이 추가되더라도 자동으로 저장용량이 늘어난다.
• ArrayList에 객체를 추가하면 인덱스 0부터 차례대로 저장된다.
• 특정 인덱스의 객체를 제거하면 바로 뒤 인덱스부터 마지막 인덱스까지 모두 앞으로 1씩 당겨진다.
  • 따라서 빈번한 객체 삭제와 삽입이 예상된다면 ArrayList보다는 LinkedList를 사용하는 것이 좋다. 

 

 

ArrayList 생성하기

ArrayList<타입 매개변수> 리스트이름 = new ArrayList<타입 매개변수>(초기 저장 용량);

ArrayList<StringL> container1 = new ArrayList<String>();
// String 타입의 객체를 저장하는 ArrayList 생성
// 초기 용량이 인자로 전달되지 않으면 기본적으로 10으로 지정된다.

 

 

ArrayList 활용 예제

public class Test {
    public static void main(String[] args) {

        // ArrayList 를 생성하여 list 에 할당
        ArrayList<String> list = new ArrayList<>();

        // String 타입의 데이터를 ArrayList 에 추가
        list.add("java");
        list.add("mignon");
        list.add("tree");

        // 저장된 총 객체 수 얻기
        int size = list.size();

        // 0번 인덱스의 객체 얻기
        String skill = list.get(0);

        // 저장된 총 객체 수 만큼 조회
        for(int i = 0; i < list.size(); i++) {
            String str = list.get(i);
            System.out.println(i + " : " + str);
        }

        // 0번 인덱스 객체 삭제
        list.remove(0);

        // for-each 문으로 순회
        for(String str : list) {
            System.out.println(str);
        }
    }
}

 

 

LinkedList

데이터를 효율적으로 추가, 삭제, 변경하기 위해 사용된다. 
링크드 리스트는 불연속적으로 존재하는 데이터를 서로 연결(link)한 형태로 구성되어 있다. 

LinkedList의 각 요소(node)들은 자신과 연결된 이전 요소 및 다음 요소의 주소값과 데이터로 구성되어 있다. 

class Node {
	Node next;  // 다음 요소의 주소 저장
    Node prev;  // 이전 요소의 주소 저장
    Object obj; // 데이터 저장
}

• LinkedList 에서의 데이터 삭제
  • 삭제하고자 하는 요소의 이전 요소가 삭제하고자 하는 다음 요소를 참조하도록 변경
  • 배열처럼 데이터를 이동하기 위해 복사할 필요가 없기 때문에 처리 속도가 훨씬 빠르다. 
• LinkedList 에서의 데이터 추가
  
  • 새로운 요소를 추가하고자 하는 위치의 이전 요소와 다음 요소 사이에 연결해주면 된다.
  • 이전 요소가 새로운 요소를 참조하고, 새로운 요소가 다음 요소를 참조하게 만드는 것.

 

 

ArrayList와 LinkedList의 성능차이 비교

public class Test {
    public static void main(String[] args) {

        ArrayList<String> al = new ArrayList<>(5000000);
        LinkedList<String> ll = new LinkedList<>();

        System.out.println("== 순차적으로 추가하기 ==");
        System.out.println("ArrayList  : "  + add1(al));
        System.out.println("LinkedList : " + add1(ll));

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

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

        System.out.println("== 순차적으로 삭제하기 ==");
        System.out.println("ArrayList  : " + remove1(al));
        System.out.println("LinkedList : " + remove1(ll));
    }

    // 순차적으로 요소 100만개 추가하기
    public static long add1(List<String> list) {
        long start = System.currentTimeMillis();
        for(int i = 0; i < 1000000; i++) list.add(i + "");
        long end = System.currentTimeMillis();
        return end - start;
    }

    // 중간에 요소 10000개 추가하기
    public static long add2(List<String> 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<String> 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<String> list) {
        long start = System.currentTimeMillis();
        for(int i = 0; i < 10000; i++) list.remove(i);
        long end = System.currentTimeMillis();
        return end - start;
    }
}


// 출력 결과

== 순차적으로 추가하기 ==
ArrayList  : 69
LinkedList : 146
== 중간에 추가하기 ==
ArrayList  : 2600
LinkedList : 10
== 중간에서 삭제하기 ==
ArrayList  : 2491
LinkedList : 143
== 순차적으로 삭제하기 ==
ArrayList  : 5
LinkedList : 11

순차적으로 추가/삭제하는 경우 :   ArrayList > LinkedList

중간 데이터를 추가/삭제하는 경우 :   LinkedList >>>>> ArrayList