자바 컬렉션 (Java Collection) 정리

Collection 이란 ?

 - 여러 원소들을 담을 수 있는 자료구조를 뜻함

※ 자료구조? 자료를 효율적으로 이용할 수 있도록 컴퓨터에 저장하는 방법

 

 

참http://funnyksoo.blogspot.com/2015/09/collection-frameworkjava.html

 

핵심 인터페이스

1. List 

 - 특징 : 순서가 있는 데이터의 집합, 데이터의 중복을 허용

2. Set

 - 특징 : 순서를 유지하지 않는 데이터의 집합, 데이터의 중복을 허용하지 않는다.

3. Map

 - 특징 : 순서는 유지되지 않으며, 키는 중복을 허용하지 않고, 값은 중복을 허용한다.

 

ArrayList

 - 장점 : 배열의 크기를 임의로 변화시킬 수 있고, 타입을 직접 설정할 수 있음

 - 단점 : 데이터의 추가, 삭제에 시간이 많이 걸림

    ※느린 이유 : ArrayList는 배열 방이 다 차면 배열의 크기를 두배로 늘림

 

 두 배 큰 크기의 새로운 배열을 선언하고 그 배열에 기존 배열에 있었던 데이터를 전부 다 갖다 복사하는 작업을 더블링 이라고함(더블링에 소요되는 시간은 O(n), 입력시간은 O(1), 검색시간O(1))

 

테스트

public class Main {
    static class ArrayList {
        private Object[] data;
        private int size;
        private int index;

        public ArrayList() {
            this.data = new Object[this.size];
            this.size = 1;
            this.index = 0;
        }

        public void add(Object object) {
            System.out.println("index: " + this.index + ", size: " + this.size + ", data size: " + this.data.length);
            if (this.index == this.size - 1) {
                doubling();
            }
            data[this.index] = object;
            this.index++;
        }

        private void doubling() {
            this.size = this.size * 2;
            Object[] newData = new Object[this.size];
            for (int i = 0; i < data.length; i++) {
                newData[i] = data[i];
            }
            this.data = newData;
            System.out.println("*** index: " + this.index + ", size: " + this.size + ", data size: " + this.data.length);
        }

        public Object get(int i) throws Exception {
            if (i > this.index - 1) {
                throw new Exception("ArrayIndexOutOfBound");
            } else if (i < 0) {
                throw new Exception("Negative Value");
            }
            return this.data[i];
        }

        public void remove(int i) throws Exception {
            if (i > this.index - 1) {
                throw new Exception("ArrayIndexOutOfBound");
            } else if (i < 0) {
                throw new Exception("Negative Value");
            }
            System.out.println("data removed: " + this.data[i]);
            for (int x = i; x < this.data.length - 1; x++) {
                data[x] = data[x + 1];
            }
            this.index--;
        }
    }

    public static void main(String[] args) throws Exception {
        ArrayList al = new ArrayList();
        al.add("0");
        al.add("1");
        al.add("2");
        al.add("3");
        al.add("4");
        al.add("5");
        al.add("6");
        al.add("7");
        al.add("8");
        al.add("9");
        System.out.println(al.get(5));
        al.remove(5);
        System.out.println(al.get(5));
    }
}

위에 사진와 같이 ArrayList는 배열의 방이 다 차면 더 이상 넣을 공간이 없기 때문에 더블링을 한다.

방 크기가 x2 가 되는 걸 볼 수 있다.

 

 

LinkedList 

 - 장점 : 데이터 추가/삭제시 데이터의 위치를 변경시킬 필요 없음

 - 단점 : 첫 노드부터 정보를 찾아야 할때 검색 시 느리다

 

검색을 할 떄 단방향, 양방향으로 할 수 있다.

단방향으로 했을 때는 앞에서부터 노드가 자기 다음 주소를 가지고 있고

양방향은 노드가 자기 앞,뒤 주소를 가지고 있다.

 

 

ArrayList vs LinkedList

Collection	Read(Access time)	add/remove	비교
ArrayList	빠르다	느리다	순차적인 추가삭제는 빠름 비효율적인 메모리 사용
LinkedList	느리다	빠르다	데이터가 많을수록 접근성이 떨어짐

 

 

Stack & Queue & Deque

Stack : 쌓다라는 뜻, LIFO(Last in First Out) 구조, 마지막에 저장된 것을 제일 먼저 꺼내게 된다.

 - 수식계산, 수식괄호검사, undo/redo, 뒤로/앞으로(웹)

 

Queue : 먼저 집어 넣은 데이터를 먼저 꺼내게 되는 저장 구조, FIFO(First in First Out)

 - 최근 사용문서, 인쇄 작업대기 목록, 버퍼(buffer)

 

Deque : 자료의 입력과 출력을 양 쪽 끝에서 가능하게 하는 자료구조

 

 

TreeSet

 - 장점 : 검색과 정렬이 뛰어나다

 - 단점 : 데이터의 추가, 삭제에는 느리다.

 

Set인터페이스를 구현한 컬렉션 클래스(중복허용x, 순서유지x, 정렬저장o)

이진검색트리(binary search tree - 정렬, 검색에 유리)의 구조로 되어 있음

LinkedList와 같이 각 요소(node)가 나무(tree)형태로 연결된 구조

모든 트리는 하나의 루트(root node)를 가지며, 서로 연결된 두 요소를 부모-자식 관계에 있다 하고, 하나의 부모에 최대 두개의 자식을 갖는다. (binary tree)

왼쪽 자식의 값은 부모의 값보다 작은 값을, 오른쪽 자신의 값은 부모보다 큰 값을 저장한다.(binary search tree)

검색과 정렬에 유리하지만, HastSet보다 데이터 추가, 삭제시간이 더 걸린다.

 

HashSet

 - 장점 : Set인터페이스 중 가장 빠르게 접근할 수 있음

 - 단점 : 순서를 전혀 예측할 수 없음

 

Set인터페이스를 구현한 대표적인 컬렉션 클래스(중복허용x, 순서유지x)

 

 

HashMap

 HashMap은 해싱(hashing) 기법을 사용해서 데이터를 저장하기 때문에 많은 양의 데이터를 검색할 때 성능이 뛰어나다. Map인터페이스를 구현하였으며, 데이터를 키와 값의 쌍으로 저장한다.

 key - 컬렉션 내의 중에서 유일해야한다.

 value - 키와 달리 데이터의 중복을 허용한다.

※해싱(hashing)

 - 해시함수(hash function)를 이용해서 해시테이블(hash table)에 저장하고 검색하는 기법

 - 해싱에 사용되는 자료구조는 array + linkedlist 가 조합된 형태

 

※키를 이용해서 해시테이블로부터 데이터를 가져오는 과정

 1. 키를 이용해서 해시함수를 호출

 2. 해시 함수의 호출결과인 해시코드에 대응하는 배열에 저장된 링크드리스트를 찾는다.

 3. 링크드리스트에서 키와 일치하는 데이터를 찾는다.

 (해시함수는 같은 키값에 대해 항상 같은 해시코드를 반환해야 한다, 서로 다른 키값일지라도 같은 값의 해시코드를 반환할 수 있다.

 

TreeMap

 이진검색트리(binary search tree)의 형태로 키와 값의 쌍으로 이루어진 데이터를 저장한다.

 Map의 장점인 빠른 검색과 Tree의 장점인 정렬과 범위검색의 장점을 모두 갖고 있다.

 이진검색트리처럼, 데이터를 저장할 때 정렬하기 떄문에 저장시간이 길다는 단점을 가지고 있다.

 정렬된 상태로 데이터를 조회하는 경우가 빈법하다면, 데이터를 조회할 때 정렬해야 하는 HashMap보다는 이미 정렬된 상태로 저장되어 있는 TreeMap이 빠른 조회결과를 얻을 수 있다.

(주로 HashMap을 사용함, 정렬이나 범위검색이 필요한 경우에만 TreeMap을 사용하는 것이 좋음)

 

 

정리 및 요약

 

 

ArrayList	배열기반 데이터의 추가와 삭제에 불리 순차적인 추가삭제는 제일 빠름 임의의 요소에 대한 접근성이 뛰어남
LinkedList	연결기반 데이터의 추가와 삭제에 유리 임의의 요소에 대한 접근성이 좋지 않음
HashMap	배열과 연결이 결합된 형태 추가, 삭제, 검색, 접근성이 모두 뛰어남 검색에는 최고성능을 보임
TreeMap	연결기반 정렬과 검색(특히 범위검색)에 적합 검색성능은 HashMap보다 떨어짐
Stack	Vector를 상속받아 구현
Queue	LinkedList가 Queue 인터페이스를 구현
Properties	Hashtable을 상속받아 구현
HashSet	HashMap을 이용해서 구현
TreeSet	TreeMap을 이용해서 구현
LinkedHashMap LinkedHastSet	HashMap과 HashSet에 저장순서유지기능을 추가하였음

 

참:엔지니어대한민국

참:Java의정석