Collection Framework

- 컬렉션 프레임웍이란, '데이터 군을 저장하는 클래스들을 표준화한 설계'를 뜻합니다. 

- collection : 다수의 데이터

- framework : 표준화된 프로그래밍 방식

 

- 컬렉션 프레임 워크에서는 그룹을 크게 3가지 타입이 존재한다고 인식하고 각 컬랙션을 다루는데 필요한 기능을 가진 3개의 인터페이스를 정의하였습니다.

- List, Set, Map

- List : 순서가 있는 데이터의 집합으로, 데이터의 중복을 허용합니다. (ArrayList, LinkedList, Stack, Vector등)

- Set : 순서를 유지하지 않는 데이터의 집합으로, 데이터의 중복을 허용하지 않습니다. (HashSet, TreeSet)

- Map: 키와 값의 쌍으로 이루어진 데이터의 집합으로, 순서는 유지되지 않으며 키는 중복을 허용하지 않고 값은 중복을 허용합니다. ( HashMap, TreeMap, HashTable, Properties)

ArrayList

- List인터페이스를 구현하는 클래스입니다.

import java.util.ArrayList;
import java.util.Collections;

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

        ArrayList list1 = new ArrayList(10);

        list1.add(new Integer(5));
        list1.add(new Integer(4));
        list1.add(new Integer(2));
        list1.add(new Integer(0));
        list1.add(new Integer(1));
        list1.add(new Integer(3));

        // fromIndex부터 toIndex사이에 저장된 객체를 반환합니다.
        ArrayList list2 = new ArrayList(list1.subList(1,4));
        print(list1, list2);

        Collections.sort(list1);
        Collections.sort(list2);

        print(list1,list2);

        list2.add("B");
        list2.add("C");
        list2.add(3,"A");
        print(list1, list2);
        
        list2.set(3,"AA");
        print(list1,list2);

        // list1에서 list2와 겹치는 부분만 남기고 나머지는 삭제합니다. 
        System.out.println("list1.retainAll(list2): " + list1.retainAll(list2));
        
        print(list1,list2);
        
        //list2애서 list1에 포함된 객체들 삭제한다.
        for(int i = list2.size()-1; i>=0; i--){
            if(list1.contains(list2.get(i)))
                list2.remove(i);
        }
        print(list1,list2);
        
        
    }

    static void print(ArrayList list1, ArrayList list2){
        System.out.println("list1:" + list1);
        System.out.println("list2: " + list2);
        System.out.println();
    }
}

- ArrayList는 List인터페이스를 구현하여 저장된 순서를 유지합니다.

final int LIMIT = 10;

        String source ="ABCDEFGHIJKLM!@#%^&*()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));
        }

LinkedList

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

 1. 크기를 변경할 수 없다. -> 크기를 변경할 수 없으므로 새로운 배열을 생성해서 데이터를 복사해야합니다. 실행속도를 향상시키기 위해서는 충분히 큰 크기의 배열을 생성해야하므로 메모리가 낭비됩니다. 

 2. 비순차적인 데이터의 추가 또는 삭제에 시간이 많이 걸립니다. -> 배열의 중간에 데이터를 추가하려면 빈자리를 만들기 위해 다른 데이터를 복사해서 이동시켜야합니다. 

 

-> 이러한 배열의 단점을 보완하기 위해서 링크드 리스트라는 자료구조가 고안되었습니다. 

링크드 리스트는 불연속적으로 존재하는 데이터를 서로 연결한 형태로 구성되어있습니다. 

 

링크드 리스트의 각 노드들은 자신과 연결된 다음 요소에 대한 참조와 데이터로 구성되어 있습니다.

class Node{
	Node next;
    Object obj;
}

 다음 요소의 데이터를 추가 혹은 삭제해주려한다면 해당 요소를 next에서 참조할 수 있도록 설정해주거나, 기존의 다음 요소를 다다음 요소로 바꾸어주면 됩니다. 

 

다만 링크드 리스트는 이동방향이 단방향이기 때문에 다음 요소에 대한 접근은 쉽지만, 이전 요소에 대한 접근은 어렵습니다. 이 점을 보완한 것이 더블 링크드 리스트입니다. (이중연결리스트, doubly linked list) 

 

class Node{
	Node next;
    Node previous;
    Object obj;
}

 

다음은 ArrayList와 LinkedList의 성능 차이 및 장단점을 비교하기 위한 예제입니다. 

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

public class ArrayListLinkedListTest {
    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보다 더 빠르고 (마지막 요소의 값을 null로만 바꾸어주면 되니..) 

중간 데이터를 추가.삭제하는 경우는 LinkedList가 ArrayList보다 빠릅니다.( LinkedList같은 경우 각 요소간의 연결만 변경해주면 되니까...)

 

STACK과 QUEUE

 - 스택은 마지막에 저장한 데이터를 가장 먼저 꺼내게 되는 LIFO구조로 되어있고, 큐는 처음에 저장한 데이터를 가장 먼저 꺼내게 되는 FIFO구조로 되어있습니다. 

- 순차적으로  데이터를 추가하고 삭제하는 스택에는 ArrayList와 같은 배열 기반의 컬렉션 클래스가 적합하지만, 

- 큐는 데이터를 꺼낼 때 항상 첫번째 저장된 데이터를 삭제하므로 ArrayList와 같은 배열기반의 컬렌션 클래스를 사용한다면 데이터를 꺼낼때마다 빈 공간을 채우기 위해 데이터의 복사가 발생하므로 비효율적입니다. 따라서 큐는  ArrayList보다 LinkedList로 구현하는 것이 더욱 적합하다고 합니다. 

 

boolean empty()	Stack이 비어있는지 알려준다.
Object peek()	Stack의 맨 위에 저장된 객체를 반환, pop()과 달리 Stack에서 객체를 꺼내지는 않음
Object pop()	Stack의 맨 위에 저장된 객체를 꺼낸다. (비었을 때는 EmptyStackException 발생)
Object push(Object item)	Stack에 객체(item)를 저장한다.
int search(Object o)	Stack에서 주어진 객체를 찾아서 그 위치를 반환한다. 못 찾으면 -1을 반환한다.

 

boolean add(Object o)	지정된 객체를 Queue에 추가합니다. 성공하면 true를 반환합니다.
Object remove()	Queue에서 객체를 꺼내 반환합니다. 비어있으면 NoSuchElementException을 반환합니다.
Object element()	삭제 없이 요소를 읽어옵니다. peek와 달리 Queue가 비었을대 NoSuchElementException이 발생합니다.
boolean offer(Object o)	Queue에서 객체를 저장합니다. 성공하면 true이고, 실패하면 false를 반환합니다.
Object poll()	Queue에서 객체를 꺼내서 반환합니다. 비어있으면 null을 반환합니다.
Object peek()	삭제없이 요소를 읽어옵니다. Queue가 비어있으면 null을 반호나합니다.

 

다음은 스택과 큐에 관한 간단한 예제입니디. 

package ch11;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class StackQueueEx {
    public static void main(String[] args) {
        Stack st = new Stack();
        Queue q = new LinkedList();

        // stack에 객체 item을 저장한다.
        st.push("0");
        st.push("1");
        st.push("2");

        // q에 객체를 저장. 성공하면 true, 실패하면 false 반환
        q.offer("0");
        q.offer("1");
        q.offer("2");

        System.out.println(" = Stack = ");
        while(!st.empty()){
            System.out.println(st.pop());
        }

        System.out.println(" = Queue = ");
        while(!q.isEmpty()){
            // queue에서 객체를 꺼내서 반환, 비어있으면 null을 반환.
            System.out.println(q.poll());
        }

    }
}

- 스택과 큐에 각각 0,1,2를 같은 순서로 넣고 꺼냈을때 결과가 다른 것을 알 수 있습니다. 

- 큐는 먼저 넣은 것이 FIFO 구조이기 때문에 넣을 때와 같은 순서이고, 스택은 먼저 넣은 것이 나중에 꺼내지는 구조이기 때문에 넣을 때의 순서와 반대로 꺼내집니다. 

 

PriorityQueue

 - Queue인터페이스 구현체 중의 하나로, 저장한 순서에 관계없이 우선순위가 높은 것 부터 꺼내는 특징이 있습니다.  -   - null은 저장할 수 없으며, null을 저장하면 NullPointerException이 발생하게 됩니다.

 - PriorityQueue는 저장공간으로 배열을 사용하며, 각 요소를 heap이라는 자료구조의 형태로 저장합니다. 

package ch11;

import java.util.PriorityQueue;
import java.util.Queue;

public class PrioriryQueueEx {
    public static void main(String[] args) {
        Queue pq = new PriorityQueue();

        pq.offer(3); // pq.offer(new Integer(3)); 오토박싱
        pq.offer(1);
        pq.offer(5);
        pq.offer(2);
        pq.offer(4);

        System.out.println(pq);

        Object obj = null;
		
        // PriorityQueue에 저장된 요소를 하나씩 꺼낸다. 
        while((obj = pq.poll()) != null){
            System.out.println(obj);
        }
    }
}

 

 - 우선 순위는 숫자가 작을수록 높으므로, 1이 가장 먼저 출력되었습니다. 

Deque

 - Queue의 변형으로, 한쪽 끝으로만 추가/삭제할 수 있는 Queue와 달리, Deque는 양쪽 끝에 추가/삭제가 가능합니다. 

 

Iterator 

 - 컬렉션 프레임워크에서는 컬렉션에 저장된 요소들을 읽어오는 표준화하였습니다. 컬렉션에 저장된 각 요소에 접근하는 기능을 가진 iterator인터페이스를 정의하고, Collection인터페이스는 'Iterator'를 반환하는 iterator()를 정의하고 있습니다. 

public interface Iterator{
	boolean hasNext();
    Object next();
    void remove();
}

public interface Collection{
	public Iterator iterator();
}

boolean hasNext()	읽어올 요소가 남아있는지 확인합니다.
Object next()	다음 요소를 읽어옵니다.
void remove()	next()로 읽어 온 요소를 삭제합니다.

Collection c = new ArrayList();
Iterator it = c.iterator();

while(it.hasNext()){
	System.out.println(it.next());
}

- ArrayList에 저장된 요소들을 출력하기 위한 코드입니다.

 

Map인터페이스를 구현한 컬렉션 클래스는 키와 값을 쌍으로 저장하기 대문에 iterator()를 직접 호출할 수 없고 그 대신 keySet()나 entrySet()와 같은 메서드를 통해서 키와 값을 각각 따로 set형태로 얻어와 다사 iterator()를 호출해야 Iterator를 얻을 수 있다고 합니다. 

Map map = new HashMap();

Iterator it = map.entrySet().iterator();

 

Arrays

 - Arrays클래스에는 배열을 다루는데 유용한 메서드가 정의되어 있습니다. 다음은 Arrays의 유용한 메서드 종류입니다.

 

copyOf(), copyOfRange()

int[] arr = {0,1,2,3,4};
int[] arr2 = Arrays.copyOf(arr,arr.length); // arr2 = [0,1,2,3,4];
int[] arr3 = Arrays.copyOf(arr,3); // arr3 = [0,1,2];
int[] arr4 = Arrays.copyOf(arr,7); // arr4 = [0,1,2,3,4,0,0];
int[] arr5 = Arrays.copyOfRange(arr,2,4); // arr5 = [2,3];
int[] arr6 = Arrays.copyOfRange(arr,0,7); // arr6 = [0,1,2,3,0,0];

-copyOf()는 배열 전체를, copyOfRange()는 배열의 일부를 복사해서 새로운 배열을 만들어 반환합니다. 

 

 

fill(), setAll()

int[] arr = new int[5];
Arrays.fill(arr,9); // arr=[9,9,9,9,9];
Arrays.setAll(arr, () -> (int)(Math.random() * 5) + 1);

- fill()은 배열의 모든 요소를 지정된 값으로 채웁니다. 

- setAll()은 배열을 채우는데 사용할 함수형 인터페이스를 매개변수로 받습니다. 이 메서드를 호출할때는 함수형 인터페이스를 구현한 객체를 매개변수로 지정 혹은 람다식을 지정해야한다고 합니다.

 

sort(), binarySearch()

int[] arr = {3,2,0,1,4};
int idx = Arrays.binarySearch(arr,2); // idx = -5 -> 잘못된 결과입니다. 

Arrays.sort(arr); 
System.out.println(Arrays.toString(arr)); // [0,1,2,3,4]
int idx = Arrays.binarySearch(arr,2); // idx = 2;

- sort()는 배열을 정렬할때, 그리고 binarySearch()는 배열에 지정된 값이 저장된 위치를 찾아서 반환하는데, 반드시 배열이 저장된 상태여야 올바른 결과를 얻습니다. (이진검색이기 때문에...)

https://ko.wikipedia.org/wiki/%EC%9D%B4%EC%A7%84_%EA%B2%80%EC%83%89_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

이진 검색 알고리즘 - 위키백과, 우리 모두의 백과사전

 

equals(), toString()

int[] arr = {0,1,2,3,4};
int[][] arr2D = {{11,12}, {21,22}};

System.out.println(Arrays.toString(arr)); // [0,1,2,3,4]
System.out.println(Arrays.deepToString(arr2D)); // [[11,12], [21,22]]

String[][] str2D = new String[][]{{"aaa","bbb"},{"AAA","BBB"}};
String[][] str2D2 = new String[][]{{"aaa","bbb"},{"AAA","BBB"}};

System.out.println(Arrays.equals(str2D, str2D2)); // false
System.out.println(Arrays.deepEquals(str2D, str2D2)); // true

 - toString()은 배열의 모든 요소를 문자열로 편하게 출력해서 사용할 수 있습니다.

 - 다차원 배열을 출력하기 위해서는 deepToString()을 사용해야 합니다.

- equals()는 두 배열에 저장된 모든 요소를 비교해서 같으면 true, 다르면 false를 반환합니다.

- 2차원 배열을 비교하기 위해서는 deepEquals()를 사용해야합니다. 다차원배열은 배열의 배열의 형태로 구성되기 때문에 equals()를 사용하면 배열에 저장된 배열의 주소를 비교하기 때문입니다.

 

HashSet

 - HashSet은 Set인터페이스를 구현한 가장 대표적인 컬렉션이며, Set인터페이스의 특징대로 중복된 요소를 저장하지 않습니다.

- 저장순서를 유지하지 않습니다.

- 저장순서를 유지하고 싶다면 LinkedHashSet을 쓰면 됩니다.

 

import java.util.HashSet;
import java.util.Set;

public class HashSetEx1 {
    public static void main(String[] args) {
        Object[] objArr= {"1",new Integer(1),"2","2","3","3","4","4","4"};
        Set set = new HashSet();

        for(int i=0; i<objArr.length; i++){
            set.add(objArr[i]);
        }

        System.out.println(set);
    }
}

- 이렇듯 HashSet은 중복을 저장하지 않습니다. add메서드는 객체를 추가할 때 HashSet에 이미 같은 객체가 있으면 중복으로 간주하고 저장하지 않습니다.

 

TreeSet

 - TreeSet은 이진 검색 트리라는 자료구조의 형태로 데이터를 저장하는 컬렉션 클래스입니다. Set인터페이스를 구현하였으므로 중복된 데이터의 저장을 허용하지 않으며, 정렬된 위치에 저장하므로 저장순서를 유지하지도 않습니다.

 

- 이진트리는 링크드리스트처럼 여러 개의 노드가 서로 연결된 구조로, 각 노드에 최대 2개의 노드를 연결할 수 있으며 'root'라고 불리는 하나의 노드에서부터 시작하여 계속해서 확장해나갈 수 있습니다. 

class TreeNode{
	TreeNode left;
    Object element;
    TreeNode right;
}

 

HashMap과 HashTable

 - HashMap은 Map을 구현하였고, Map의 특징인 키와 값을 묶어서 하나의 데이터로 저장한다는 특징을 지닙니다.

 - 해싱을 사용하기때문에 많응 양의 데이터를 검색하는데 있어서 뛰어난 성능을 보입니다. 

public class HashMap extends AbstractMap implements Map,Cloneable, Serializable {
	transient Entry[] table;
    
    static class Entry implements Map.Entry{
    	final Object key;
        Obejct value;
    }
}

- HashMap은 Entry라는 내부 클래스를 정의하고 다시  Entry타입의 배열을 선언하고 있습니다. 

- key와 value는 별개의 값이 아니라 서로 관련된 값이므로 각각의 배열로 선언하기보다는 하나의 클래스로 정의해서 하나의 배열로 다루고 있음을 알 수 있다.

- 키와 값을 Object타입으로 저장합니다.

- 키는 컬렉션 내의 키 중에서 유일해야합니다.

- 값은 키와 달리 데이터의 중복을 허용해야합니다.

 

Properties

 - Properties는 HashMap의 구버전인 Hashtable을 상속받아 구현한 것으로 Hashtable은 키와 값을 Object, Object형태로 저장하는데 비해 Properties(String,String)형탸로 저장하는 단순화된 컬렉션 클래스입니다.

import java.util.Enumeration;
import java.util.Properties;

public class PropertiesEx {
    public static void main(String[] args) {
        Properties prop = new Properties();

        prop.setProperty("timeout","30");
        prop.setProperty("language","kr");
        prop.setProperty("size","10");
        prop.setProperty("capacity","10");

        // prop에 저장된 내용을 enumeration을 통해 출력합니다.
        Enumeration e = prop.propertyNames();

        while(e.hasMoreElements()){
            String element = (String)e.nextElement();
            System.out.println(element + "=" + prop.getProperty(element));
        }

        System.out.println();
        prop.setProperty("size","20");

        System.out.println("size=" + prop.getProperty("size"));
        System.out.println("capacity=" + prop.getProperty("capacity","20"));
        System.out.println("loadFactor=" + prop.getProperty("loadFactor","0.75"));

        System.out.println(prop); // prop에 저장된 요소들을 출력한다.
        prop.list(System.out); // prop에 저장된 요소들을 화면(System.out)에 출력한다.

    }
}

 

-String getProperty(String key)는 Properties에 저장된 값을 읽어옵니다. 

-String getProperty(String key, String defaultValue)는  읽어오려는 값이 없으면 defaultValue를 반환하는 메서드입니다. 

- Properties는 Hashtable을 상속받아 구현하므로 Map의 특성상 저장순서를 유지하지 않습니다.

- list메서드를 이용하면 Properties에 저장된 모든 데이터를 화면 또는 파일에 편리하게 출력할 수 있습니다.