자바 자료구조, 제네릭, 컬렉션

자료구조

• 프로그램에서 사용할 많은 데이터를 메모리 상에서 관리하는 여러 구현 방법들입니다.
• 효율적인 자료구조가 성능 좋은 알고리즘의 기반이 됩니다.
• 자료의 효율적인 관리는 프로그램의 수행속도와 밀접한 연관이 있습니다.
• 여러 자료 구조 중에서 구현하려는 프로그램에 맞는 최적의 자료구조를 활용하기 위해 다양한 자료구조에 대한 이해가 필요합니다.

 

배열(Array)

• 동일한 데이터 타입을 순서에 따라 관리하는 자료 구조입니다.
• 정해진 크기가 있습니다.
• 요소의 추가와 제거 시 다른 요소들의 이동이 필요합니다.
• 배열의 i번째 요소를 찾는 인덱스 연산이 빠릅니다.
• jdk 클래스로는 ArrayList와 Vector가 있습니다.

 

연결 리스트(Linked List)

• 동일한 데이터 타입을 순서에 따라 관리하는 자료구조입니다.
• 자료를 저장하는 노드에는 자료와 다음 요소를 가리키는 링크(포인터)가 있습니다.
• 자료가 추가 될 때 노드 만큼의 메모리를 할당 받고 이전 노드의 링크로 연결합니다.
• 연결 리스트의 i 번재 요소를 찾는데 걸리는 시간은 요소의 개수에 비례합니다.(O(N))
• jdk클래스로는 Linked List가 있습니다.

 

스택(Stack)

• 맨 마지막 위치(top)에서만 자료를 추가, 삭제, 꺼내올 수 있습니다.
• Last In First Out (후입선출) 구조입니다.
• jdK 클래스로는 Stack이 있습니다.

 

큐(Queue)

• 맨 앞(front)d에서 자료를 꺼내거나 삭제하고, 맨 뒤(rear)에서 자료를 추가합니다.
• First In First Out (선입선출) 구조입니다.

 

트리(Tree)

• 부모 노드와 자식 노드간의 연결로 이루어진 자료구조입니다.

 

힙(Heap)

• Priority Queue를 구현한 자료구조입니다.
• Max heap은 부모 노드가 항상 자식 노드보다 큰 경우입니다.
• Min heap은 부모 노드가 자식 노드보다 항상 작거나 같은 경우입니다.

 

이진 트리(Binary Tree)

• 부모 노드에 자식 노드가 두 개 이하인 트리입니다.

 

이진 검색 트리(Binary Search Tree)

• 자료의 중복을 허용하지 않습니다.
• 왼쪽 자식 노드는 부모 노드보다 작은 값, 오른쪽 자식 노드는 부모 노드보다 큰 값을 가집니다.
• 자료 검색 시간은 평균 log(N) 입니다. 자료를 넣는 순서에 따라서 트리의 모양이 달라지게 됩니다.
• jdk 클래스로는 TreeSet과 TreeMap이 있습니다. (Tree로 시작하는 클래스는 정렬을 지원 합니다.)

 

그래프(Graph)

• 정점과 간선들의 유한 집합 G = (V,E) 입니다.
• 정점(vertex) : 여러 특성을 가지는 객체, 노드(node)
• 간선(edge) : 정점들의 연결 관계를 나타냅니다. 링크(Link). 방향성이 있는 경우와 없는 경우가 나뉩니다.
• 탐색 방법 : BFS(Bread First Search), DFS(Depth First Search)

 

해싱

• 자료를 검색하기 위한 자료구조입니다.
• 키(key)에 대한 자료를 검색하기 위한 사전(dictionary) 개념의 자료구조입니다.
• key는 유일하고 value를 쌍으로 저장합니다.
• index = hash(key) : 해시 함수가 key에 대한 인덱스를 반환해줍니다. 해당 인덱스 위치에 자료를 저장하거나 검색하게 됩니다.
• 해시 함수에 의해 인덱스 연산이 산술적으로 가능하기 때문에 key에 대한 value 탐색은 탐색은 O(1) 시간이 걸립니다.
• 저장되는 메모리 구조를 해시 테이블이라고 합니다.
• jdk 클래스로는 HashMap과 Properties가 있습니다.

 

제네릭

• 클래스에서 사용하는 변수의 자료형이 여러개 있고, 그 메서드의 기능은 동일한 경우 클래스의 자료형을 특정하지 않고 추후 해당 클래스를 사용할 때 지정 할 수 있도록 선언합니다.
• 실제 사용되는 자료형의 변환은 컴파일러에 의해 검증되므로 안정적인 프로그래밍 방식입니다.
• 컬렉션 프레임워크에서 많이 사용되고 있습니다.

class GenericClass<T> {
    T genericMember;

    T getMember() {
        return genericMember;
    }

    void setMember(T newMember){
        this.genericMember = newMember
    }
}

GenericClass<String> gc = new GenericClass<String>();
gc.setMember("aaaa");
System.out.println(gc.geMember()); // aaaa 출력

자료형 매개변수 T(type parameter) : 이 클래스를 사용하는 시점에 실제 사용할 자료형을 지정합니다. static 변수는 사용할 수 없습니다.

 

다이아몬드 연산자 <>

• 다이아몬드 연산자 내부에서 자료형은 생략가능합니다. ArrayList list = new ArrayList<>();
• 제네릭에서 자료형 추론이 가능합니다. ArrayList list = new ArrayList() => var list = new ArrayList(); (var로 지역변수 자료형 추론이 가능합니다)

 

제네릭과 상위 클래스

• T 자료형의 범위를 제한 할 수 있습니다.
• 상위 클래스에서 선언하거나 정의하는 메서드를 활용할 수 있습니다.
• 상속을 받지 않는 경우 T는 Object로 변환되어 Object 클래스가 기본으로 제공하는 메서드만 사용가능합니다.

class A {
    String a() { return "aaa"; };
}

class B extends A{}
class C extends A{}

class D<T extends A> {
    T member;

    String d() {
        return member.a();
    }
}

위와 같은 경우 제너릭 타입의 상위 클래스가 A임을 명시해주었으므로 A 클래스의 메서드인 a()를 사용할 수 있습니다.

 

제너릭 메서드

• 자료형 매개변수를 메서드의 매개변수나 반환 값으로 가지는 메서드입니다.
• 자료형 매개변수가 하나 이상인 경우도 있습니다.
• 제너릭 클래스가 아니어도 내부에 제너릭 메서드는 구현할 수 있습니다.
• 형태는 public <자료형 매개 변수> 반환타입 메서드이름(자료형 매개 변수 ...) {}입니다.

 

컬렉션 프레임워크

• 프로그램 구현에 필요한 자료구조를 구현해 놓은 JDK 라이브러리입니다.
• java.util 패키지에 구현되어 있습니다.
• 자료구조들을 직접 구현할 필요 없고, 최적화된 알고리즘을 사용할 수 있도록 해줍니다.

 

Collection 인터페이스

• 하나의 객체를 관리하기 위한 메서드가 선언된 인터페이스입니다.
• 하위에 List와 Set 인터페이스가 있습니다.

 

List 인터페이스

• 객체를 순서에 따라 저장하고 관리하는데 필요한 메서드가 선언된 인터페이스입니다.
• 자료구조 리스트의 구현을 위한 인터페이스입니다.
• 원소들의 중복을 허용합니다.
• 하위에 ArrayList, Vector, LinkedList, Stack, Queue 등이 있습니다.

 

Set 인터페이스

• 순서와 관계없이 중복을 허용하지 않고 유일한 값을 관리하는데 필요한 메서드가 선언됩니다.
• 하위에 HashSet, TreeSet 등이 있습니다.

 

Map 인터페이스

• 쌍으로 이루어진 객체를 관리하는데 사용하는 메서드들이 선언된 인터페이스입니다.
• 객체는 Key-Value의 쌍으로 이루어져 있습니다.
• key는 중복을 허용하지 않습니다.
• 하위에 HashTable, HashMap, Properties, TreeMap 등이 있습니다.

 

요소 순회

• 컬렉션 프레임워크에 저장된 요소들을 하나씩 차례로 참조하는 것을 말합니다.
• 순서가 있는 List인터페이스의 경우 iterator를 사용하지 않고 get(i) 메서드를 활용할 수 있습니다.
• set 인터페이스의 경우 get(i) 메서드가 제공되지 않으므로 iterator를 활용하여 객체를 순회합니다.

 

Iterator

• boolean hasNext() : 이후에 요소가 더 있는지를 체크하는 메서드입니다. 요소가 있다면 true를 반환합니다.
• E next() : 다음 요소를 반환합니다.

List<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
Iterator<Integer> it = list.iterator();

while(it.hasNext()){
    int temp = list.next();
    System.out.println(temp); // 1,2,3이 차례대로 출력됩니다.
}

 

HashSet

• Set 인터페이스를 구현한 클래스입니다.
• 멤버의 중복 여부를 체크하기 위해 인스턴스의 동일성을 확인해야하므로 equals()와 hashCode() 메서드를 재정의해줘야 합니다.

 

TreeSet

• 객체의 정렬에 사용되는 클래스입니다.
• Set 인터페이스를 구현하여 중복을 허용하지 않고, 오름차순이나 내림차순으로 객체를 정렬할 수 있습니다.
• 내부적으로 이진검색트리로 구현되었습니다.
• 비교 대상이 되는 객체에 Comparable이나 Comparator 인터페이스를 구현해야 TreeSet에 추가 될 수 있습니다.

 

class A implements Comparable<A> {
    int a;

    @Override
    public int compareTo(A a){
        return this.a - a.a; // 오름차순
    }
}

 

a 멤버 변수의 크기를 통한 객체의 비교함수를 정의했습니다.

내림차순으로 정렬하고 싶다면 return a.a - this.a; 로 변경하면 됩니다.

 

class StringCompare implements Comparator<String> {
    @Override
    public int compare(String s1, String s2){
        return (s1.compareTo(s2)); // 오름차순 정렬
    }
}

...

Set<String> set = new TreeSet<String>(new StringCompare());
set.add("aaa");
set.add("bbb");
set.add("ccc");

// set = ["aaa","bbb","ccc"]

Comparator를 구현하면 비교 연산을 custom하게 처리할 수 있습니다.

 

HashMap

• Map 인터페이스를 구현한 클래스입니다.
• key - value 쌍으로 관리하는 메서드를 구현합니다.
• key를 이용해 값을 저장하고 key를 이용해 값을 꺼내오는 방식입니다.
• key는 중복될 수 없고, 객체의 유일성 비교를 위해 equals()와 hashCode() 메서드를 구현해야 합니다.

 

TreeMap

• Map 인터페이스를 구현한 클래스이고 key에 대한 정렬을 구현할 수 있습니다.
• key가 되는 클래스에 Comparable이나 Comparator를 구현함으로써 key값을 기준으로 정렬하여 관리할 수 있습니다.