자료 구조 기술 지식

1. Array와 LinkedList 차이

• 접근
  • Array: Random Access를 지원한다. 요소들을 인덱스를 통해 직접 접근할 수 있다. 따라서 특정 요소에 접근하는 시간 복잡도는 O(1)이다.
  • LinkedList: Sequential Access를 지원한다. 어떤 요소를 접근할 때 순차적으로 검색하며 찾아서 시간복잡도는 O(n)이다.
• 삽입과 삭제
  • 저장 방식도 배열에서 요소들은 인접한 메모리에 연이어 저장된다.
  • LinkedList에서 새로운 요소에 할당된 메모리의 위치 주소가 LinkedList의 이전 요소에 저장된다.
  • Array의 시간 복잡도는 O(n)이 소요되지만 LinkedList의 시간 복잡도는 O(1)이 소요된다.

• 메모리 할당
  • 배열에서 메모리는 선언 시 컴파일 타임에 할당(정적 메모리 할당)
  • LinkedList는 새로운 요소가 추가될 때 런타임에 메모리를 할당한다.(동적 메모리 할당)
  • 배열은 stack 색션에 할당되고 LinkedList는 힙영역에 할당된다.

2. ArrayList와 LinkedList의 차이

• 공간적 제약
  • ArrayList: 결국 배열이기 때문에 길이가 고정되어있다. 새로 배열에 새로운 요소를 추가하려고 할 때 가득 차있다면 새로운 배열을 생성해야한다.
  • LinkedList: 한 개의 Node는 다른 Node에 대한 참조만 가지고 있다. 따라서 공간적 제약을 ArrayList에 비해 받지 않는다.

• 새로운 요소 추가
  • ArrayList: 새로운 요소를 추가할 때 여유 공간이 있는 경우에는 O(1)이지만 없으면 O(n)이므로 결과적으로는 O(n)이다.
  • LinkedList: 새로운 요소를 추가할 때 항상 O(1)이다. 마지막 요소의 참조값만 바꿔주면 되기 때문

3. Array와 ArrayList의 차이

• 공통점
  • add, get method
    • 요소를 추가하거나 가져올 때 성능은 비슷하다. 두 작업 모두 일정한 시간에 실행
  • Duplicate element
    • 중복되는 요소를 가질 수 있다.
  • Null values
    • null 값을 가질 수 있고 참조할 수 있다.
  • 순서
    • 순서가 지정되지 않는다.
• 차이점
  • 길이의 조정 유무
    • Array: 고정 길이 길이를 늘이고 싶다면 새로운 배열을 생성해줘야한다.
      • ArrayList: 가변길이, 기본 값으로 10개의 사이즈로 시작하지만 요소들이 더해지만 크기가 자동적으로 늘어난다.
  • 속도가 ArrayListd의 자동 길이 조정으로 인해 array에 비해 느리다.
  • Primitives
    • ArrayList는 Array에 비해 오직 Object(Integer, String ...) 을 가질 수 있고 int, float과 같은 타입을 가질 수 없다.

4. List와 Set의 차이점

• List는 중복이 가능하지만 Set은 중복이 불가능하다.
• List에 있는 데이터를 Set에 삽입할 시 중복 제거

5. Stack과 Queue의 차이점

• Stack
  • FILO(First in Last Out)
  • push, pop을 사용
  • DFS, 재귀에서 사용
• Queue
  - FIFO(First in First Out)
  • 주로 데이터가 입력된 시간 순서대로 처리되어야 할 때 사용
  • BFS, 캐시 구현할 때 사용

6. PriorityQueue 동작 원리

• 우선 선위가 가장 높은 데이터를 먼저 꺼내기 위해 고안된 자료구조
• 일반적으로 힙을 사용
• 힙은 완전이진트리를 통해서 구현되었기 때문에 우선 순위 큐의 시간복잡도는 O(logn)

7. BST, Binary Tree

• BST(이진 탐색 트리)
  • 이진 탐색 + 연결 리스트
  • 이진 탐색의 효율적인 탐색 능력을 유지하면서, 빈번한 자료 검색가 삭제가 가능하다는 장점
  • 이진 탐색 트리는 왼쪽 트리의 모든 값이 반드시 부모 노드보다 작아야하고 오른쪽은 커야하는 특징
  • 삽입과 삭제의 시간복잡도는 O(h)
  • 트리가 균형이 맞지 않으면 워스트케이스가 나올 수 있다. 그래서 이 균형을 맞춘 구조가 AVL Tree

8. Hash Table

• key, value으로 구성된 자료 구조
• 해쉬 함수를 통해 index를 생성한다.
• 충돌이 발생할 수 있으며 최악의 경우 검색할 때 O(n)의 시간복잡도가 발생하고 잘 구현된 경우는 O(1)의 시간 복잡도를 가진다. 충돌응 Chaining, Open addressing 등의 방식으로 해결 가능
• 원래는 연결 리스트로 구현하지만 이진 탐색 트리로도 구현이 가능한데 이 경우는 탐색 시간이 O(logn)이 된다. 이 방법은 크기가 큰 배열을 미리 할당하지 않아도 되기 때문에 적은 공간을 사용한다는 장점이 있다.

9. HashMap과 HashTabl의 차이

• 동기화의 지원 여부 차이
• HashTable은 동기화된 메소드로 구성되어서 멀티 쓰레드들이 동시에 이 메소드들을 실행할 없다. 따라서 멀티 쓰레드 환경에서 안전하게 사용 가능
  - Hashtable은 멀티 스레드 환경에서 안전하게 Map 자료구조를 사용할 수 있다는 점

10. HashTable 충돌 문제 해결

• Open Addressing

  • 충돌이 발생하면 다른 해시 버켓에 해당 자료를 삽입하는 방식

• Chaining(자바에서 사용)

  • 충돌이 발생하면 키에 해당하는 데이터들을 LinkedList 형태로 연결하는 방식

• 현재 자바 8에서는 체이닝 데이터의 개수가 8개 이상인 경우 이진 트리(검색 효율성을 위해) 형태를 변환한다