[Java] 자료 구조

자료구조(Data Structure)

• 효율적인 로직을 짜기 위한 기본 토대
• 개발하려는 시스템에 가장 효율적인 자료구조를 선택하는게 중요하다.

 

 

---

선형 자료구조

배열(Array)

• 자료의 물리적 위치와 논리적 위치가 같다.
• 인덱스 연산에 의해 배열 내 요소를 바로 꺼낼 수 있다.
• 산술적 연산이 빠르다.
• 배열의 개수에 의존성을 갖는다.

---

연결 리스트(Linked List)

• 노드가 필요할 때마다 메모리를 할당 받고 자료는 링크를 통해 연결된다.
• 자료의 물리적 위치와 논리적 위치가 다를 수 있다.
• 자료뿐만 아니라 다음 요소를 가리킬 링크를 가진다.
  • Ex. C, C++ 의 포인터
• 데이터 수정에 따라 링크 연결만 생성 또는 해제해주면 되기 때문에 배열에 비해 수행속도가 적게 든다.

---

스택(Stack)

• Last In First Out(후입선출)
• 자료의 추가 및 삭제가 top 에서만 이루어진다.

---

큐(Queue)

• First In First Out(선입선출)
• 자료의 추가는 rear에서, 자료의 삭제는 front에서 이루어진다.
• enqueue : 추가 연산
• dequeue : 삭제 연산

---

비선형 자료구조

트리(Tree)

힙(Heap)

• Heap Sort : 힙 트리를 이용한 정렬 알고리즘
• Max heap : 최대 힙 (부모 노드가 항상 자식 노드보다 크거나 같음)
• Min heap : 최소 힙 (부모 노드가 항상 자식 노드보다 작거나 같음)

이진 검색 트리(Binary Search Tree)

• 자료(key)의 중복을 허용하지 않는다.
• 부모 노드를 중심으로 좌측 노드는 부모 노드 보다 작은 값, 우측 노드는 부모 노드 보다 큰 값을 갖는다.
• 자료 검색 평균 시간은 lgN 이다.
• Skewed Tree(편향 이진 트리) 일경우 AVL Tree 나 Red-Black Tree 와 같이 균형을 맞춘 뒤에 이진 탐색을 수행하기도 한다.
• 전위순회로 탐색을 하면 자료가 정렬되어 출력된다.

---

그래프(Graph)

• 정점(vertex) = 노드(node)
• 간선(edge) = 링크(link)

• 그래프 구현 방법
  • 인접 행렬(adjacency matrix) : 연결되어 있을 경우 1, 0
  • 인접 리스트(adjacency list)
• 그래프 탐색 방법
  • DFS(Depth First Search), BFS(Breadth First Search)

---

해시(Hash)

• 검색을 위한 자료 구조 (dictionary)
• key는 유일하고 이에 대한 value를 쌍으로 저장한다.
• 데이터 삽입 순서와는 무관하다.
• 해시 함수를 적용하여 해시 함수를 적용한 인덱스 위치에 데이터를 저장한다.
  • 해시 함수 적용에 따른 유일한 값을 갖도록 다양한 해시 함수를 적용한다.
  • 해시 알고리즘 적용의 이유 -> 검색에 들어가는 속도가 빠르며 산술적으로 가능하다.
  • 해시 함수 적용 이후 충돌이 발생할 수도 있다. (동일한 위치에 데이터 삽입 시)

 

---

제네릭 프로그래밍

제네릭(Generic)

• 클래스에서 사용하는 변수의 자료형이 여러개 일수 있고, 그 기능(메서드)은 동일한 경우 클래스의 자료형을 특정하지 않고 추후 해당 클래스를 사용할 때 지정 할 수 있도록 선언한다.
• 컬렉션 프레임워크에서 많이 사용한다.
• 자료형 매개변수 T(type parameter)를 사용하여 표현한다.

| 📄 Object를 이용한 여러 타입 대체 하기

public class ThreeDPrinter{

    private Object material;

    public void setMaterial(Object material) {
        this.material = material;
    }

    public Object getMaterial() {
        return material;
    }
}

| 📄 Generic을 이용한 여러 타입 대체 하기

public class GenericPrinter<T> {

    private T material;

    public T getMaterial() {
        return material;
    }

    public void setMaterial(T material) {
        this.material = material;
    }

    public String toString(){
        return material.toString();
    }
}

• Generic 을 쓰면 따로 형변환을 하지않아도 된다.
• 런타임시 자동으로 데이터를 넣어서 컴파일한다.

제네릭에서의 자료형 추론   Java 10 부터 가능

ArrayList list = new ArrayList() -> var list = new ArrayList();

• 변수를 선언할 때 var 지역 변수를 사용하여 자료형을 생략할 수 있으며 컴파일시에, 컴파일러가 자료형을 추론한다.

 

---

T extends

• T 자료형의 범위를 제한한다.
• 상위 클래스에서 선언하거나 정의하는 메서드를 활용할 수 있다.

public class GenericPrinter<T extends Material> {

    private T material;

    public T getMaterial() {
        return material;
    }

    public void setMaterial(T material) {
        this.material = material;
    }

    public String toString(){
        return material.toString();
    }
}

• Material 클래스를 상속받은 클래스만 T의 자료형으로 사용할 수 있다.

---

제네릭 메서드

public <자료형 매개 변수> 반환형 메서드 이름(자료형 매개변수...) { }

---

컬렉션 프레임워크

• 자료구조를 구현해놓은 JDK 라이브러리
• java.util 패키지 내에 구현되어있음

ArrayList

• public ArrayList(int initialCapacity)
• public ArrayList()
  • initialCapacity를 지정하지 않을 경우 기본적으로 사이즈 10의 ArrayList가 만들어진다.
• public ArrayList(Collection<? extends E> c)

 

• get(int)
• add(int, E)
• remove(int, Object)

 

---

Iterator

• 컬렉션 프레임워크의 모든 자료구조에서 저장된 요소들을 하나씩 차례로 참조할 때 사용가능하다.
• Set 인터페이스의 경우 get(i) 메서드가 제공되지 않아, Iterator를 활용하여 객체를 순회한다.

 

• boolean hasNext()
• E next
• remove()

 

---

HashSet

• 멤버의 중복 여부를 체크하기 위해 인스턴스의 유일성 확인이 필요하다.
  • equals(), hashCode() 재정의
  • equals()를 재정의하면 동일한 메모리 위치에 데이터가 저장되어야하므로 hashCode() 도 무조건 재정의 해줘야한다.
• hashCode를 equals와 함께 재정의하지 않으면 동일 데이터는 중복 저장된다.
  • ⭐️ hash 값을 사용하는 Collection(HashSet, HashMap, HashTable)을 사용할 때 문제 발생!
  • Collection(HashSet, HashMap, HashTable) 의 내부 로직

Reference : equals와 hashCode는 왜 같이 재정의해야 할까?

---

TreeSet

• 객체의 정렬을 위해 사용한다.
• Set 인터페이스를 구현해서 중복을 허용하지 않고 오름차순이나 내림차순으로 정렬

---

HashMap

• key는 중복될 수 없으며 인스턴스의 유일성 비교를 위해 equals(), hashCode() 재정의 필요
  • key 는 Set의 개념(중복 불가), Value는 컬렉션의 개념