자료구조 & 알고리즘 스토리

코딩테스트 및 알고리즘 준비를 위해 꾸준히 알고리즘 관련 포스팅도 진행할 예정이다.
자바 컬렉션을 시작으로 진행할 예정이고, 추후 STL이나 컬렉션 사용없이 직접 구현해보고 공부할 예정이며 추후에 고급 알고리즘 포스팅까지 달려보겠다.

Collections?

여러 원소들을 담을 수 있는 자료구조를 뜻한다. 참고로 자바에서는 이러한 컬렉션을 따로 클래스로 관리하는 1급 컬렉션을 자주 사용하곤 한다. 관심있으면 찾아보는 것을 추천하고, 현재 velog에 Clean Code 스토리에도 언급되어있다.

주요 인터페이스

• List
  * 순서가 있는 데이터의 집합이며 데이터를 중복으로 허용하는 기본적인 선형구조
• Set
  * 순서를 유지하지 않는 데이터의 집합이며, 빠르게 찾을 수 있고 중복이 허용되지 않는다
• Map
  * 순서는 유지되지 않고 빠르게 찾을 수 있으며, Key는 중복이 안되고, Value는 중복을 허용
  

ArrayList

• 배열의 크기를 임의로 변화시킬 수 있고, 타입을 직접 설정할 수 있다(제너릭활용)
• 데이터의 삭제에 시간이 많이 걸림

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--;
        }

위 예제를 보면 i(index)에 해당하는 값을 지우기 위해서 한칸씩 앞으로 당겨서 저장하는 만큼 O(n)의 시간이 걸리는 것을 직관적으로 확인할 수 있다

LinkedList

• 데이터 추가/삭제시 데이터의 위치를 변경할 필요가 없음
• 메모리에 선형적으로 저장되는 것이 아니기 때문에 검색시에 느리다

Stack & Queue & Deque

• 순서대로 LIFO / FIFO / 자료의 입력과 출력을 양끝에서 가능하게 하는 자료구조
• Full Scan의 경우(DFS, BFS)에서 활용가능
• 다양한 알고리즘에서 활용이 가능

TreeSet

• 검색과 정렬이 뛰어남
• 자바에서는 new Comparator<>(Object a, Object b) 를 활용해서 직접 정렬순서 적용가능
• 데이터의 추가, 삭제에는 느린편
• Set인터페이스를 구현한 클래스로 이진검색트리 구조로 되어있음
• LinkedList형태가 트리구조로 되어있는 것으로 이해하면 좋고, 노드와 리프 등 다양한 용어가 존재함
• 정렬시에 왼쪽 자식값이 부모의 값보다 작고, 오른쪽은 부모보다 큰 값을 저장함
• 검색과 정렬에 유리하지만, HashSet보다 데이터의 추가 삭제시간이 더 걸림 O(log N)

HashSet

• Set 인터페이스 중에서 가장 빠르게 접근할 수 있음
• 순서를 예측할 수 없음

HashMap

• 해싱기법을 이용해서 데이터를 저장해서 많은 양의 데이터를 검색할때 성능이 뛰어남
• Map 인터페이스를 이용해서 구현
• Key - Value 로 구성되어있음

TreeMap

• 이진검색트리의 형태로 키와 값의 쌍으로 이루어진 데이터를 저장함
• Map의 장점인 빠른 검색과 Tree의 장점인 정렬, 2가지를 모두 포함하고 있음 (Key로 정렬)

요약

출처 : https://class-programming.tistory.com/56