11장 컬렉션 프레임워크 20201026

컬렉션 프레임워크 p578~

 

컬렉션 프레임워크는 데이터 군(group)을 저장하는 클래스들을 표준화한 설계를 뜻함

 

컬렉션 - 다수의 데이터(데이터 그룹)

프레임워크 - 표준화된 프로그래밍 방식

 

 

컬렉션 프레임워크는 컬렉션, 다수의 데이터를 다루는 데 필요한 다양하고 풍부한 클래스들을 제공하고, 인터페이스와 다형성을 이용한 객체지향적 설계를 통해 표준화되어 있어 사용법 익히기 편리하고 재사용성 높은 코드를 작성할 수 있다

 

 

 

컬렉션 프레임워크의 핵심 인터페이스

 

Collection인터페이스

List와 Set의 조상인 인터페이스

 

컬렉션 클래스에 저장된 데이터를 읽고, 추가하고 삭제하는 등 컬렉션을 다루는데 가장 기본적인 메소드들을 정의

 

 

List인터페이스

중복을 허용하면서 저장순서가 유지되는 컬렉션을 구현하는데 사용

구현클래스) ArrayList, LinkedList, Stack, Vector등

 

 

Set인터페이스

중복을 허용하지 않고 저장순서가 유지되지 않는 컬렉션 클래스를 구현하는데 사용

구현클래스) HashSet, TreeSet등

 

 

Map인터페이스

키(key)와 값(value)을 하나의 쌍으로 묶어서 저장하는 컬렉션 클래스를 구현하는 데 사용

키는 중복될 수 없지만 값은 중복 허용

구현클래스) Hashtable, HashMap, LinkedHashMap, SortedMap, TreeMap등

 

values()에서는 반환타입이 Collection이고, KeySet()에서는 반환타입이 Set인데, 이유는

값(value) - 중복허용 o, Collection타입으로 반환

키(key) - 중복허용 x, Set타입으로 반환

 

 

 

 

 

 

 

 

ArrayList

 

List인터페이스를 구현 -> 데이터 저장순서 유지, 중복허용 O

 

Vector와 구현원리와 기능적인 측면에서 동일

 

Object배열을 이용해 데이터를 순차적으로 저장

 

ArrayList나 Vector같이 배열을 이용한 자료구조는 데이터를 읽어오고 저장하는 데는 효율이 좋지만, 용량을 변경해야 할 때는 새로운 배열을 생성한 후 기존의 배열로부터 새로 생성된 배열로 데이터를 복사해야하기 때문에 상당히 효율이 떨어지는 단점이 있음

-> 처음 인스턴스 생성 시, 저장할 데이터의 개수를 잘 고려하여 충분한 용량의 인스턴스를 생성하는 것이 좋음

 

import java.util.ArrayList;
import java.util.Collections;
 
public class ArrayListEx1 {
    public static void print(ArrayList list1, ArrayList list2) {
        System.out.println("list1 : " + list1);
        System.out.println("list2 : " + list2);
    }
    
    public static void main(String[] args) {
        // ArrayList 생성
        ArrayList list1 = new ArrayList(10);
        
        // list1에 요소추가 (int)
        list1.add(new Integer(5));
        list1.add(new Integer(4));
        list1.add(new Integer(2));
        list1.add(new Integer(0));
        list1.add(new Integer(7));
        list1.add(new Integer(6));
        list1.add(new Integer(1));
        
        // ArrayList를 추가로 생성해 list1의 일부를 복사
        ArrayList list2 = new ArrayList(list1.subList(1, 4));    // list1의 1~3번째 요소값을 list2에 저장
        print(list1, list2);
        
        // list1, list2정렬
        Collections.sort(list1);
        Collections.sort(list2);
        print(list1, list2);
        
        // list1이 list2를 전부 포함하고 있는지?
        System.out.println("list1.containsAll(list2):"
                                + list1.containsAll(list2));
        
        // list2에 요소추가 (String)
        list2.add("B");
        list2.add("C");
        list2.add(3,"A");        
        list2.add(3,"AA");
        print(list1, list2);
        
        list2.set(3, "AA");
        print(list1, list2);
        
        // list1에서 list2와 겹치는 부분만 남기고 나머지 삭제
        System.out.println("list1.retainAll(list2):"
                        + list1.retainAll(list2));    // list1에 변화가 있으므로 true반환
        
        print(list1, list2);
        
        // list2에서 list1에 포함된 객체 삭제// i를 증가시켜 삭제하면, 요소 삭제할때마다 빈공간 채우기위해 나머지 요소들이 자리이동 -> 올바른 결과 도출x
        for(int i=list2.size()-1; i>=0; i--) {
            if(list1.contains(list2.get(i)))        // list2의 객체가 list1에 포함되는지?
                    list2.remove(i);
        }
        print(list1, list2);
    }
 
}
 

출력

list1 : [5, 4, 2, 0, 7, 6, 1]
list2 : [4, 2, 0]
list1 : [0, 1, 2, 4, 5, 6, 7]
list2 : [0, 2, 4]
list1.containsAll(list2):true
list1 : [0, 1, 2, 4, 5, 6, 7]
list2 : [0, 2, 4, AA, A, B, C]
list1 : [0, 1, 2, 4, 5, 6, 7]
list2 : [0, 2, 4, AA, A, B, C]
list1.retainAll(list2):true
list1 : [0, 2, 4]
list2 : [0, 2, 4, AA, A, B, C]
list1 : [0, 2, 4]
list2 : [AA, A, B, C]

 

 

 

 

import java.util.ArrayList;
import java.util.List;
 
public class ArrayLIstEx2 {
    public static void main(String[] args) {
 
        final int LIMIT = 10;
        String source = "0123456789abcdefghijABCDEFGHIJ!@#$%^&*()ZZZ";
        int length = source.length();
        
        List list = new ArrayList(length/LIMIT + 10);
        
        for(int i=0; i<length; i+=LIMIT) {
            if(i+LIMIT < length)
                list.add(source.substring(i, i+LIMIT));
            else
                list.add(source.substring(i));
        }
        
        for(int i=0; i<list.size(); i++) {
            System.out.println(list.get(i));
        }
    }
 
}
 

출력

0123456789
abcdefghij
ABCDEFGHIJ
!@#$%^&*()
ZZZ

 

 

 

 

 

 

 

LinkedList

 

배열은 가장 기본적인 형태의 자료구조로 구조가 간단하며 사용하기 쉽고 데이터를 읽어오는데 걸리는 시간(접근시간, access time)이 가장 빠르다는 장점이 있지만 다음과 같은 단점도 있다

 

1. 크기변경 불가

- 크기변경 불가 -> 새로운 배열 생성해 데이터 복사

- 실행속도 향상위해선 충분히 큰 크기의 배열을 생성해야 하므로 메모리 낭비

 

2. 비순차적인 데이터의 추가 / 삭제에 시간이 많이 걸림

- 배열의 중간에 데이터 추가하려면, 빈자리 만들기 위해 다른 데이터들을 복사해서 이동해야함

 

 

이러한 배열의 단점을 보완하기 위해 '링크드 리스트(linked list)' 자료구조 사용

 

링크드 리스트의 각 요소(node)들은 자신과 연결된 다음 요소에 대한 참조(주소값)와 데이터로 구성되어 있음

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

 

배열 - 모든 데이터가 연속적으로 존재

링크드 리스트 - 불연속적으로 존재하는 데이터를 서로 연결(link)한 형태로 구성

 

데이터를 이동하기 위해 복사하는 과정이 없어 처리속도가 빠름

 

이동방향이 단방향이기 때문에 다음 요소에 대한 접근은 쉽지만 이전 요소에 대한 접근은 어려움

이를 보완한 것이 '더블 링크드 리스트(이중 연결리스트, doubly linked list)'

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

 

더블 링크드 리스트는 단순히 링크드 리스트에 참조변수를 하나 더 추가한 것 뿐, 그 외에는 링크드 리스트와 같음

 

 

더블 링크드 리스트의 접근성을 보다 향상시킨 것이

'더블 써큘러 링크드 리스트(이중 원형 연결리스트 doubly circular linked list)'

단순히  더블 링크드 리스트의 첫 번째 요소와 마지막 요소를 서로 연결시킨 것

-> 마지막 요소의 다음요소가 첫번째 요소가 되고, 첫번째 요소의 이전요소가 마지막요소가 됨

 

 

 

LinkedList클래스는 '더블 링크드 리스트'로 구현되어 있음

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
 
public class ArrayListLinkedListTest {
    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;
    }
    
 
    public static void main(String[] args) {
        ArrayList al = new ArrayList(200000);
        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("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));
 
    }
 
}
 

출력

= 순차적으로 추가하기 =
ArrayList : 712
LinkedList : 1321
= 중간에 추가하기 =
ArrayList : 6065
LinkedList : 18
= 중간에서 삭제하기 =
ArrayList : 8047
LinkedList : 252
= 순차적으로 삭제하기 =
ArrayList : 9
LinkedList : 63

 

 

순차적으로 추가/삭제하는 경우에는 ArrayList가 LinkedList보다 빠름

--> 각 요소들을 복사, 재배치 할 일이 없어 매우 빠름

 

중간 데이터를 추가/삭제하는 경우에는 LinkedList가 ArrayList보다 빠름

--> 각 요소간의 연결만 변경해주면 되기 때문에 매우 빠름 / ArrayList는 각 요소들을 재배치하고 복사하기때문에 느림

 

 

 

 

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
 
public class ArrayListLinkedListTest2 {
    public static void add(List list) {
        for(int i=0; i<100000; i++) list.add(i+"");
    }
    
    public static long access(List list) {
        long start = System.currentTimeMillis();
        for(int i=0; i<10000; i++) list.get(i);
        long end = System.currentTimeMillis();
        return end - start;
    }
    
    public static void main(String[] args) {
        ArrayList al = new ArrayList(1000000);
        LinkedList ll = new LinkedList();
        add(al);
        add(ll);
        
        System.out.println("= 접근시간테스트 =");
        System.out.println("ArrayList : " + access(al));
        System.out.println("LinkedList : " + access(ll));
    }
}
 

출력

= 접근시간테스트 =
ArrayList : 0
LinkedList : 307

 

 

배열은 각 요소들이 연속적으로 메모리상에 존재해 저장된 데이터를 빠르게 읽어올 수 있음

링크드 리스트는 불연속적으로 위치한 각 요소들이 연결되어서 처음부터 n번째 데이터까지 따라가야하기 때문에 느림

 

--> 링크드 리스트는 데이터 개수가 많아질수록 데이터를 읽어오는 접근시간(access time)이 길어짐

 

 

 

컬렉션	읽기(접근시간)	추가 / 삭제	비 고
ArrayList	빠르다	느리다	순차적인 추가삭제는 더 빠름 비효율적인 메모리사용
LinkedList	느리다	빠르다	데이터가 많을수록 접근성 떨어짐

 

다루고자 하는 데이터의 개수가 변하지 않는 경우라면 ArrayList

데이터 개수의 변경이 잦다면 LinkedList