ADT와 자료구조에 대하여

I. ADT와 DS

1. ADT (Abstract Data Type)

• 자료구조의 속성과 행위를 설명하는 인터페이스이다.
  • 예시: Stack
    • Stack의 행위를 정의하지만 내부적인 로직 구현을 설명하지는 않는다.
      • push(obj): Stack의 Top 위치에 obj를 추가
      • pop(): Stack의 Top 위치에 있는 데이터를 삭제
      • peek(): Stack의 Top 위치에 있는 데이터를 조회

2. DS (Data Structure)

• ADT를 코드로 구현한 클래스이다.
  • 예시 1: Stack을 ArrayList로 구현한 경우
  • 예시 2: Stack을 LinkedList로 구현한 경우

II. Array와 List

1. Array

• 연속적인 메모리 공간에서 같은 종류의 데이터를 저장할 수 있는 자료구조이다.
• 인덱싱이 가능하다.

2. List

• 순서를 가지며 추가, 삭제, 탐색이 가능한 ADT이다.
• 예시: List의 행위를 정의하지만 내부적인 로직 구현을 설명하지는 않는다.
  • add(obj): List에 obj를 추가
  • remove(obj): List에 있는 obj를 제거
  • get(index): List의 index번째에 있는 원소를 반환
  • contains(obj): List에 obj가 있는지 확인

III. ArrayList와 LinkedList

1. ArrayList

• Array (또는 Array List)를 Java 언어로 구현한 자료구조이다.
• 연속적인 공간에 데이터를 순차적으로 저장하는 자료구조이다.
• 저장된 데이터의 변경이 빈번하게 일어나지 않을 때 유용하다.

---

• 장점
  • 인덱싱이 가능하기 때문에 원하는 데이터를 빠르게 찾을 수 있다.

---

• 단점
  • 데이터를 추가하거나 삭제할 경우 해당 인덱스 이후에 있는 데이터 전부를 앞 또는 뒤로 이동시켜야 하기 때문에 데이터의 추가 및 삭제가 오래 걸린다.
  • 크기가 불변적이기 때문에 데이터의 추가 및 삭제가 일어나는 경우 ArrayList의 복제본을 만들고 ArrayList 원본을 지워야 한다.

2. LinkedList

• Linked Node를 Java 언어로 구현한 자료구조이다.
• 비연속적인 공간에 데이터를 순서대로 저장하는 자료구조이다.
• 저장된 데이터의 변경이 빈번히 일어날 때 유용하다.

---

• 장점
  • 데이터의 추가 및 삭제가 용이하다.
  • 크기가 가변적이기 때문에 데이터의 추가 및 삭제가 일어나는 경우 LinkedList의 복제본을 만들지 않는다.

---

• 단점
  • 처음부터 탐색해야 하기 때문에 원하는 데이터를 찾는 데 오래 걸린다.
  • 저장하고자 하는 데이터뿐만 아니라 다음 데이터를 가리키는 추가적인 공간이 더 필요하기 때문에 저장 공간을 더 많이 차지한다.

IV. List와 Set

1. List

• 같은 종류의 데이터를 저장하는 ADT이다.
• 데이터의 순서를 보장하고 중복을 허용한다.
• 자료구조 (Java 구현체) 예시: ArrayList, LinkedList

2. Set

• 같은 종류의 데이터를 저장하는 ADT이다.
• 데이터의 순서를 보장하지 않고 중복을 허용하지 않는다.
• 자료구조 (Java 구현체) 예시: SortedSet, HashSet

V. HashMap과 HashSet

1. HashMap

• Key - Value의 형태로 저장하는 자료구조이다.
• 삽입, 탐색, 삭제, 갱신이 상수 시간에 처리된다. [시간복잡도: $O(1)$]
• 기본적으로 Array로 구현되어 있어 인덱싱이 가능하며, Key를 index로 바꿔주는 함수인 Hash Function을 사용한다.

---

• Hash Function
  • Key를 Array 크기 내의 index로 바꿔주는 함수이다.
  • 해시 함수를 어떻게 구현하느냐에 따라 충돌이 발생하지 않을 수도 있고, 많이 발생할 수도 있다.

2. HashSet

• HashMap을 이용하여 구현된 클래스.