자료구조(Data Structure)

Array란 무엇인가요?

Array는 인덱스와 인덱스에 대응하는 데이터들로 이루어진 자료 구조를 나타냅니다. 논리적 저장 순서와 물리적 저장 순서가 일치하며 인덱스로 해당 원소에 접근할 수 있습니다.

  • 원소의 인덱스 값을 알고 있으면 검색 및 수정에는 O(1)의 시간이 걸리지만 삽입이나 삭제등이 필요한 경우에는 원소들을 shift 해주어야 하기 때문에 O(n)의 시간이 걸립니다.

LinkedList란 무엇인가요?

LinkedList란 각 노드가 데이터와 포인터를 가지고 연결되어 있는 방식으로 데이터를 저장하는 자료 구조를 나타냅니다. 링크드 리스트의 종류로는 단일 링크드리스트, 이중 링크드리스트, 원형 링크드리스트 등이 존재합니다.

  • 링크드리스트의 경우 인덱스가 존재하지 않기 때문에 검색 및 수정시 첫 번째 노드부터 순차적으로 모든 노드를 검색해야 합니다. 따라서 링크드리스트의 검색과 수정시 시간 복잡도는 O(1) 입니다.
  • 링크드리스트의 경우 노드의 삭제와 삽입시 O(1)만에 해결할 수 있지만, 원하는 위치에 원소를 삽입하거나 삭제하는 경우 위치를 검색하는 시간이 필요하므로 O(n)의 시간이 걸립니다.

선형 자료구조와 비선형 자료구조의 차이는 무엇인가요?

선형 자료구조는 데이터 요소들이 저장되어 있는 모습을 표현했을 때 직선이고, 비선형 자료구조는 데이터 요소들이 저장되어 있는 모습을 표현했을 때 직선이 아닌 것을 의미합니다.

  • 선형 자료구조의 대표적인 예는 Array, Queue 등이 있고, 비선형 자료구조의 대표적인 예는 Tree, Graph 등이 있습니다.

Stack이란 무엇인가요?

Stack이란 선형 자료구조의 일종으로 Last In First Out(LIFO)의 특징을 가지고 있습니다. 즉, Stack에 먼저 들어가게 된 원소는 맨 바닥에 깔리게 되고, 가장 늦게 들어간 원소는 그 위에 쌓이고 호출 시 가장 위에 있는 녀석이 호출되는 구조입니다.

  • LIFO의 특징을 사용하려는 것이 아닌 Stack의 CRUD 시간 복잡도는 계산할 이유가 없는 것 같습니다. Stack 이외에도 CRUD를 위한 더 좋은 자료구조를 사용할 수 있을 것 같네요.

Queue란 무엇인가요?

Queue란 선형 자료구조의 일종으로 First In First Out(FIFO)의 특징을 가지는 자료 구조를 의미합니다.

  • FIFO의 특징을 사용하려는 것이 아닌 Queue의 CRUD 시간 복잡도를 굳이 구해보자면
    • 삽입
      • 맨 뒷 부분에 삽입 시 O(1)
      • 원하는 위치에 삽입 시 O(n)
    • 삭제, 수정, 검색
      • 원하는 노드를 삭제, 수정, 검색할 시 O(n)

Tree란 무엇인가요?

트리는 비선형 자료구조로써 node들과 이를 연결하는 edge들로 구성되어 있습니다.

  • 트리는 하나의 루트 노드를 갖습니다.
  • 트리에는 싸이클이 존재하지 않습니다.
  • 순서나 규칙이 없는 트리의 경우 CRUD시 시간 복잡도는 트리의 모든 노드를 탐색해야 하기 때문에 O(n)의 시간이 걸립니다.

Binary Tree(이진 트리)란 무엇인가요?

이진 트리란 각각의 노드가 최대 두 개의 자식 노드를 갖는 트리를 의미합니다. 이진 트리의 종류로는 완전 이진 트리, 포화 이진 트리, 정 이진 트리 등이 존재합니다.

  • 완전 이진 트리(Complete Binary Tree) : 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있고 마지막 레벨의 노드가 왼쪽에서 오른쪽으로 채워지는 이진 트리를 의미합니다.
  • 정 이진 트리(Full Binary Tree) : 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리를 의미합니다.
  • 포화 이진 트리(Perfect Binary Tree) : 모든 내부(Internal) 노드가 두 개의 자식 노드를 가지며 모든 leaf 노드가 동일한 레벨을 갖는 트리를 의미합니다.
  • 노드 간의 규칙이 없는 이진 트리의 경우 CRUD시 시간 복잡도는 트리의 모든 노드를 탐색해야 하기 때문에 O(n)의 시간이 걸립니다.

Binary Search Tree(이진 탐색 트리, BST)란 무엇인가요?

이진 탐색 트리란 서로 중복된 데이터를 갖는 노드가 없다는 가정하에 부모 노드가 왼쪽 자식 노드보다 크고 오른쪽 자식 노드보다는 작다는 규칙을 만족하는 이진 트리를 Binary Search Tree 라고 합니다.

  • 이진 탐색 트리에서 CRUD의 시간 복잡도는 O(h) 즉, 높이에 비례합니다.
  • 시간 복잡도를 h가 아닌 n으로 표현해 보았을 때 완전 이진 트리의 경우에는 O(log n)으로 표현할 수도 있으나, 편향 트리(Skewed Tree) 즉, 한 쪽으로만 노드가 추가되는 경우 시작 복잡도는 O(n)입니다.
  • 이진 탐색 트리가 편향 트리가 되는 문제를 해결하기 위해 서브 트리의 레벨을 비교해서 균형을 맞추는 Rebalancing 기법이 등장 했으며 이러한 기법을 구현한 대표적인 트리는 Red-Black Tree 입니다.



Binary Heap이란 무엇인가요?

Binary Heap이란 최대 또는 최소를 빠르게 찾아내기 위해 만들어진 완전이진트리(CBT)로써 부모노드와 자식 노드간에 대소 관계가 성립합니다. 이러한 대소 관계를 기반으로 Heap은 Max Heap과 Min Heap으로 나눌 수 있습니다.

  • Heap에 존재하는 노드들의 최대 및 최소를 검색하기 위한 시간 복잡도는 O(1) 입니다.
  • 연산 후 heap의 대소 관계 구조를 계속 유지하기 위해서는 제거된 루트 노트를 대체할 다른 노드가 필요합니다. 여기서 heap은 맨 마지막 노드를 루트 노드로 대체시킨 후, 다시 heapify 과정을 거쳐 heap 구조를 유지합니다.
  • heapify 연산을 수행하는데 걸리는 시간 복잡도는 O(log n)이기 때문에 결국 최대 및 최소를 검색하는데 걸리는 시간은 O(log n) 입니다.
  • 최대 최소가 아닌 다른 노드들의 CRUD 시간 복잡도는 O(log n) 입니다.

Binary Heap과 Binary Search Tree는 각각 어떠한 경우에 사용하는게 좋나요?

Heap은 최대 및 최소 노드를 연산(O(1), heapify를 포함한다면 O(log n))하는데 유용하지만, BST는 모든 노드를 연산(O(log n))하는데 유용합니다.

Red-Black Tree란 무엇인가요? (업데이트)

Red Black Tree(RBT) 란 자가 균형 이진 탐색 트리의 한 종류로써 이진 탐색 트리(BST)의 단점인 편향성을 색깔을 통해서 보완하기 위한 자료구조 입니다. 즉, 트리의 노드의 개수가 동일할 경우 depth를 최소화하여 시간 복잡도를 줄이는 것이 핵심 아이디어 입니다.

  • RBT의 CRUD 시간 복잡도는 O(log n)이다.
  • Root node 부터 leaf node 까지의 모든 경로 중 최소 경로와 최대 경로의 크기 비율은 2보다 크지 않다. (balanced 상태)
  • 노드의 child가 없을 경우 child를 가리키는 포인터는 NIL 값을 저장한다. 이러한 NIL 들을 leaf node로 간주한다.



Red-Black Tree의 정의

  • 각 노드는 Red or Black 색깔을 갖는다.
  • Root node의 색깔은 Black이다.
  • 각 leaf node(NIL)의 색깔은 black이다.
  • 어떤 노드의 색깔이 red라면 두 개의 children의 색깔은 모두 black이다.
    • 어떤 노드의 색깔이 black이라면 두 개의 children 의 색깔은 모두 red이다.
  • 각 노드에 대해서 노드로부터 그 노드의 자손인 leaf node로 가는 경로들은 모두 같은 수의 Black 노드를 포함한다. 이를 Black-Height 라고 한다.
    • Black-Height : 노드 x 로부터 노드 x 를 포함하지 않는 leaf node 까지의 simple path 상에 있는 black nodes 들의 개수

Red-Black Tree 노드 삽입

  1. BST의 특성을 유지하면서 색깔이 red인 노드를 삽입한다.
  2. 삽입한 노드가 색깔 규칙에 어긋난다면 노드의 색깔을 조정하고, Black-Height에 위배된다면 rotation을 통해 height를 조정한다.

Red-Black Tree 노드 삭제

  1. BST의 특성을 유지하면서 해당 노드를 삭제한다.
  2. 지워진 노드의 색깔이 Black 이라면 Black-Height가 1 감소한 경로에 black node가 1개 추가되도록 rotation하고 노드의 색깔을 조정한다.
    • 지워진 노드의 색깔이 red라면 어떠한 문제도 발생하지 않는다.

Hash Table이란 무엇인가요?

Hash Table이란 임의의 길이를 가진 키를 고정된 길이의 Hash Code로 변환시켜서 이를 인덱스로 사용하여 데이터를 저장하는 자료구조를 의미합니다.

Hash Function이란 무엇인가요?

Hash Function이란 임의의 길이를 가진 데이터를 고정된 길이를 가진 고유한 데이터로 변환시키는 함수를 의미합니다. 이러한 함수로부터 얻어지는 값을 해시 값, 해시코드 짧게 말해서 해시라고도 합니다.

  • 어설픈 Hash Function을 사용한다면 서로 다른 두 개의 키가 같은 해시 값으로 표현될 수 있는데 이를 충돌(Collision)이라고 합니다.
  • 해시는 등호(=) 연산에만 특화되어 있기 때문에 부등호 연산(>, <)이 자주 사용되는 데이터베이스 검색을 위해서는 적절하지 않습니다. => 이런 경우 B+ Tree 알고리즘을 자주 사용합니다.
  • 충돌(Collision)이 많아질수록 Search에 필요한 시간 복잡도가 O(1)에서 O(n)에 가까워집니다.
  • hash function을 1:1 맵핑으로 만드는 것보다 Collision을 최소화하는 방향으로 설계하고 발생하는 Collision에 대비해 어떻게 대응할 것인가가 중요하다.

Hash Collision Resolve 방식에는 어떠한 방법이 존재하나요?

  1. Open Address 방식 (개방 주소법)

    해시 충돌이 발생하면 다른 해시 버킷에 해당 자료를 삽입하는 방식입니다. 다른 해시 버킷을 찾기 위해 다양한 방법이 존재하는데 대표적인 방법으로는 순차적으로 비어있는 버킷을 찾을 때까지 계속 탐색하는 Linear Probing 방식이 존재합니다.

    • 해시 버킷을 채운 밀도가 높아질수록 Worst Case 발생 빈도가 높아지기 때문에 시간 복잡도가 O(n)에 가까워진다.

  2. Separate Chaining 방식 (분리 연결법)

    Hash Table의 각 버킷이 여러 값을 저장할 수 있는 자료 구조를 가리키도록 만드는 방법을 의미합니다. 이를 구현할 수 있는 방법으로는 LinkedList를 사용하는 방식과 Tree를 사용하는 방식이 존재합니다. Java util 에서는 HashMap을 Separate Chaining 방식을 사용하여 구현하고 있습니다.

    • Separate Chaining Using LinkedList : 각각의 버킷들을 LinkedList로 만들어 충돌(Collision)이 발생하면 해당 bucket의 list에 값을 추가하는 방식이다.
    • Separate Chaining Using Tree : 각각의 버킷들을 Tree로 만들어 충돌(Collision)이 발생하면 해당 bucket의 tree에 값을 추가하는 방식입니다.
    • Tree는 LinkedList에 비해 메모리 사용량이 많기 때문에 데이터 개수가 적을 때는 링크드리스트를 사용하는게 유리하지만, 개수가 많을 경우 Tree의 시간 복잡도가 LinkedList보다 빠르기 때문에 Tree를 사용하는게 더 유리하다.

Graph란 무엇인가요?

Graph란 Node들과 이를 연결하는 Edge들을 모아 놓은 자료구조입니다. 방향 및 비방향 그래프가 모두 존재하며, 사이클 및 self-loop가 존재해도 무방합니다. 그래프는 인접 행렬과 인접 리스트로 구현할 수 있습니다.

Graph 탐색에는 어떠한 방법이 존재하나요?

그래프는 따로 규칙이 존재하지 않기 때문에 모든 정점을 탐색해야만 합니다. 특정 정점을 기준으로 넓게 탐색하기 전에 깊게 탐색하는 방법인 DFS(Depth First Search)와 깊게 탐색하기 전에 넓게 탐색하는 방법인 BFS(Breadth First Search)가 존재합니다.

  • DFS는 Stack 및 재귀를 사용해서 구현하면 쉽구요, BFS는 Queue를 사용해서 구현하면 쉽습니다.
  • DFS와 BFS를 인접리스트로 구현할 경우에 시간 복잡도는 O(V+E) 이구요, 인접 행렬로써 구현할 경우에 시간복잡도는 O(V^2) 입니다.

Minimum Spanning Tree

Minimum Spanning Tree란 그래프의 여러 Spanning Tree 중 edge의 가중치 합이 최소인 Spanning tree를 의미합니다.

Spanning Tree란 그래프의 모든 정점이 Cycle 없이 연결된 형태를 의미합니다.

Minimum Spanning Tree를 구하는 알고리즘에는 어떤 방법이 존재하나요?

Minimum Spanning Tree를 구하는 알고리즘에는 Edge 값이 가장 작은 것부터 탐색하는 탐욕적인 방법으로 대표적으로 Kruskal Algorithm과 Prim Algorithm이 존재합니다.

  • Kruskal Algorithm이란 Edge없이 vertex로만 구성된 그래프를 만들어서 weight가 제일 작은 edge 부터 검토후 cycle이 생기지 않는 경우에만 edge를 추가하는 방법을 의미하구요 시간 복잡도는 O(ElogE) 입니다.
  • Prim Algorithm이란 한 개의 vertex로 구성된 그래프 A를 만들어서 그래프 A 내부에 있는 vertex와 외부에 있는 vertex 사이의 edge를 연결했을 때 가장 작은 weight를 가진 vertex와 edge를 그래프 A에 추가하는 방법을 의미하구요 시간 복잡도는 O(ElogV)입니다.

Java

Java 8의 특징은 무엇인가요??

Java 8의 주요 특징으로는 자바에 함수형 프로그래밍이 처음으로 도입되었다는 것입니다. 새롭게 도입된 기능으로는 Stream API, Lambda Expression, Method Reference, Optional Class, Functional Interface, Default Methods 등이 있습니다.

Java 9의 특징은 무엇인가요??

Java 9의 주요 특징으로는 모듈화가 도입되었다는 것입니다. Package와 여러 데이터 자원을 포함하는 Module을 런타임시에 가져옴으로써 더 잘 구조화된 어플리케이션을 작성할 수 있게 되었고 성능을 향상시킬 수 있게 되었습니다.

Java 10의 특징은 무엇인가요?

Java 10의 주요 특징으로는 Local Variable Type Inference가 도입되었다는 것입니다. 자바는 기존의 엄격한 타입 선언 방식에서 탈피하여 컴파일러에게 타입을 추론할 수 있게끔 해 개발자가 직접 지역 변수 타입을 작성하는 것을 없애 생산성을 증가시킬 수 있게 되었습니다.

Java 11의 특징은 무엇인가요?

Java 11의 주요 특징으로는 새로운 HTTP 클라이언트인 HttpClient가 등장했다는 것입니다. 해당 라이브러리를 사용해서 개발자는 어플리케이션의 많고 복잡한 요구사항들을 처리할 수 있게 되었습니다.

Stream API란 무엇인가요?

Stream API란 자바에서의 일련의 데이터 요소인 배열이나 컬렌션 등을 처리하기 위해 함수형 스타일을 지원해주는 API 입니다. Stream API를 사용하면 멀티 스레드를 활용해서 병렬로 연산을 수행할 수 있고, 내부 반복으로 연산을 수행하기 때문에 코드가 매우 간단해집니다.

Functional Interface란 무엇인가요?

Functional Interface란 정확히 하나의 추상 메서드가 정의된 인터페이스를 의미합니다. 함수형 인터페이스의 예로는 Predicate, Comparator, Runnable 인터페이스 등이 존재합니다.

Lamda Expression이란 무엇인가요?

Lamda Expression이란 Functional Interface를 구현하는 객체를 만들지 않고도 추상 메서드를 구현해서 해당 인터페이스 사용할 수 있는 표현식을 의미합니다. 특정 인터페이스를 사용하기 위해 일회용 객체를 만들지 않아도 됨으로 성능면에서 좋다고 생각합니다.

Method Reference란 무엇인가요?

Method Reference는 기존에 정의된 메서드와 동일한 람다 표현식을 매번 작성하는데 발생하는 불편함에서 나온 기법이며 람다 표현식을 직접 작성하는 대신에 기존의 메서드 정의를 이용하는 방법입니다. 이를 통해 개발자는 중복된 코드를 없앨 수 있으며 자연스레 생산성과 가독성 증가 효과를 얻을 수 있다고 생각합니다.

Optional 클래스는 무엇인가요?

Optional 클래스는 Java 8에서 새롭게 등장한 클래스이구요 util 패키지에 속해 있습니다. Optional 클래스는 자바 프로그래머들이 가장 자주 접하는 예외인 NPE(NullPointerException)를 관리 하기 위해 기존 객체를 감싼 Wrapper Class 입니다.

Default Method는 무엇인가요?

Default Method는 인터페이스에서 메서드 정의 뿐만 아니라 구현도 포함하는 메서드를 만들기 위해 사용되어집니다. 해당 인터페이스를 구현하는 클래스는 인터페이스의 Default Method도 상속받기 때문에 최소한의 추상 메서드만 구현하면 됩니다. 즉, 디폴트 메서드를 통해 인터페이스는 서브 클래스가 구현해야하는 최소한의 인터페이스 스펙을 유지할 수 있습니다.

추상클래스와 인터페이스의 차이는 무엇인가요?

추상 클래스는 추상화된 클래스를 의미하고 인터페이스는 클래스에서 구현해야 하는 스펙을 의미합니다. 이러한 이유에서 추상 클래스와 인터페이스의 가장 큰 차이는 사용법에서 존재한다고 생각합니다. 추상 클래스는 멤버 변수와, 메소드 명세, 구현 등 모든 부분이 상속 되기 때문에 코드의 재사용을 위해서 사용하는 경우가 많고 인터페이스는 Java 8 이전에는 메서드 명세만 상속되었기 때문에 메소드 명세의 상속을 위해서 사용된다고 생각합니다.

또한 단일 상속만을 지원하는 자바의 특성상 클래스를 상속하는 추상화 계층이 많아질수록 상속되는 클래스간에 결합도가 증가하기 때문에 관련 도메인에 잘 맞추어서 인터페이스와 추상클래스를 적절히 사용해야 한다고 생각합니다.

오버라이딩(Overriding)과 오버로딩(Overloading)은 각각 무엇인가요?

오버라이딩이란 서브클래스가 상속받은 메서드를 해당 클래스에 맞게 재구현 하는 것을 의미하구요 오버로딩이란 동일한 메서드 이름이지만 매개 변수 타입이나 개수가 다른 즉, 다른 명세를 가진 함수를 같은 클래스내에 만드는 것을 의미합니다.

  • 리턴 타입이 다른 경우는 오버로딩이 아닙니다. 컴파일러는 메서드 시그니처를 통해서 메서드 간의 차이를 식별합니다. 메서드 시그니처가 동일한 경우 리턴 타입이 달라도 컴파일 에러가 발생합니다. (같은 클래스에 동일한 메서드가 존재할 수 없기 때문)

메서드 시그니처(Method Signature)

Java에서 메서드 시그니처란 메서드 정의에서 메서드 이름과 매개변수 리스트의 조합을 말한다.

업캐스팅(Up Casting)과 다운캐스팅(Down Casting)이란 무엇인가요?

업캐스팅이란 슈퍼 클래스의 변수에 서브 클래스의 인스턴스가 들어가는 것을 의미하구요, 다운캐스팅이란 업캐스팅 된 변수의 타입을 서브 클래스 타입으로 변경하는 것을 의미합니다. 서브 클래스는 슈퍼 클래스의 명세를 상속받기 때문에 슈퍼 클래스의 변수에 들어가서 슈퍼 클래스 인스턴스인 것처럼 사용될 수 있는 것은 당연하구요, 업캐스팅 된 변수의 타입이 다시 서브 클래스로 돌아와서 다시 본인의 클래스 변수인 것처럼 사용될 수 있는 것도 당연합니다.

제네릭(Generic)이란 무엇인가요?

제네릭(Generic)이란 컴파일 타임에 강한 타입체크와 불필요한 캐스팅 코드를 삭제하기 위해서 사용하는 기능입니다. 제네릭 사용을 통해서 클래스나 메소드 내부에서 사용되는 객체의 타입 안정성을 높일 수 있었고 매번 Object나 bounded type으로 캐스팅 시 발생하는 반복적인 코드를 없앨 수 있었습니다.

제네릭(Generic)을 사용해 보셨나요?

많은 프레임워크와 라이브러리에서 제네릭을 사용해 보았지만 Pinpoint Webhook 프로젝트에서 제네릭을 사용했던 경험이 가장 기억에 남습니다. 상위 추상 클래스인 AgentChecker가 검색하는 Metric 타입을 제네릭 타입으로 지정해 놓고 이를 상속하는 서브 타입의 Checker에서 제네릭 타입을 설정해 구현한 경험이 생각 납니다.

이를 통해서 특정 Metric을 검색하는 Checker클래스를 여러개 만들 필요가 없었고, 컴파일 시에 타입 에러를 볼 수 있어서 확실한 장점이 있었지만, 처음 코드를 보는 사람들한테는 어려워서 가독성 측면에서는 좋지 않았던 것 같습니다.

String과 StringBuffer, StringBuilder의 차이를 설명해주세요.

String과 StringBuffer, StringBuilder는 모두 문자열을 다룰 수 있는 java.lang 패키지의 클래스입니다. 하지만 String은 불변 객체이구요, StringBuffer와 StringBuilder는 가변 객체 입니다. StringBuffer는 멀티스레드 환경에서 thread-safe하게 동작할 수 있는 동기화 기능을 지원해주구요, StringBuilder는 동기화 기능을 지원해주지 않아서 멀티스레드 환경에서 thread-safe하지 않습니다.

불변 객체(Immutable Object)

불변 객체란 객체 생성 후에 그 상태나 값을 바꿀 수 없는 객체를 말합니다.

Annotation이란 무엇인가요?

애노테이션(Annotation)이란 Java 버젼 5부터 추가된 기능으로 소스코드에 메타데이터 정보를 추가하기 위해 사용되어집니다. 애노테이션은 컴파일 타임에 컴파일러에게 특정 정보를 제공해 주기 위해 사용되어지거나, 런타임에 JVM에게 특정 정보를 제공해 주기 위해서 사용되어집니다.

메타데이터(Metadata)

데이터에 관한 구조화된 데이터로, 다른 데이터를 설명해 주는 데이터이다. 대량의 정보 가운데에서 찾고 있는 정보를 효율적으로 찾아내서 이용하기 위해 일정한 규칙에 따라 콘텐츠에 대하여 부여되는 데이터이다. 어떤 데이터 즉 구조화된 정보를 분석, 분류하고 부가적 정보를 추가하기 위해 그 데이터 뒤에 함께 따라가는 정보를 말한다.

Java Collection Framework에 대해서 설명해주세요.

자바에서 Collection이란 데이터의 집합과 그룹을 의미하며 이를 저장하고 연산할 수 있는 집합을 Collection Framework라고 합니다. Collection 프레임워크는 크게 두개의 명세로 나눌 수 있는데요 순서나 집합적인 저장 공간의 명세를 나타내는 Collection 인터페이스와 키와 값으로 데이터를 핸들링하는 명세를 정의하는 Map 인터페이스로 나눌 수 있습니다.

Set, List, Queue 인터페이스가 Collection 인터페이스를 상속해서 각 특성에 맞게 명세를 구체화하구요, HashMap, TreeMap 등이 Map 인터페이스를 구현해서 컬렉션 프레임워크를 형성합니다.

Set, List, Queue의 차이를 설명해주실 수 있나요?

List 인터페이스는 객체의 순서가 존재하며 원소가 중복될 수 있는 명세를 가지고 있습니다. List 인터페이스의 대표적인 구현체로는 ArrayList(동기화 보장 x)가 있습니다.

Queue 인터페이스는 FIFO의 특성을 갖고 있으며 원소가 중복될 수 있는 명세를 가지고 있습니다. Queue 인터페이스의 대표적인 구현체로는 LinkedList가 있습니다.

Set 인터페이스는 원소의 집합을 의미하며 원소의 순서가 없고 동일한 원소를 중복 저장할 수 없는 명세를 가지고 있습니다. Set 인터페이스의 대표적인 구현체로는 HashSet, TreeSet 등이 있습니다.

LinkedList와 ArrayList의 차이는 무엇인가요?

ArrayList는 내부적으로 원소를 배열에서 관리하고, LinkedList는 노드에 데이터를 저장하고 포인터를 사용해서 앞 뒤의 노드와 연결지어 데이터를 관리합니다.

삽입 및 삭제시 LinkedList는 O(1)의 시간이 걸리고, ArrayList는 O(n)의 시간이 걸립니다. 하지만 인덱스를 통해서 검색시 ArrayList는 O(1)의 시간이 걸리고 LinkedList는 O(n)의 시간이 걸립니다. 인덱스를 통해서 데이터를 관리하고 싶은 경우 ArrayList를 사용하면 좋을 것 같구요, 그렇지 않다면 LinkedList를 사용하면 좋을것 같습니다.

HashMap은 무엇인가요?

HashMap은 Hash Function을 사용해서 Key를 Hash값으로 바꾼 뒤 이를 사용해서 데이터를 관리 및 연산하는 데이터 구조를 의미합니다. HashMap의 CRUD 시간 복잡도는 O(1)이지만, 충돌(Collision)이 자주나는 경우 시간 복잡도는 O(n)까지 안좋아질 수 있음으로 Open Address나 Separate Chaining 방식을 고려해야 합니다.

HashMap과 HashTable의 차이를 아시나요?

HashTable은 동기화 기능을 제공해주기 때문에 멀티 스레드 환경에서 Thread-Safe하고, HashMap은 동기화 기능을 제공해주지 않기 때문에 멀티 스레드 환경에서 Non Thread-Safe 합니다.

ArrayList와 Vector의 차이는 무엇인가요?

ArrayList와 Vector의 차이는 동기화 기능 제공의 유무라고 생각합니다. Vector는 동기화 기능을 제공해주기 때문에 멀티 스레드 환경에서 Thread-Safe하고, ArrayList는 동기화 기능을 제공해주지 않기 때문에 멀티 스레드 환경에서 Non Thread-Safe 합니다.

TreeMap과 TreeSet의 차이는 무엇인가요?

TreeSet과 TreeMap은 모두 Red Black Tree를 기반으로하는 자료구조입니다. 가장 큰 차이라고 하면 Set과 Map의 차이입니다.

Red Black Tree

Red Black Tree는 Balanced Binary Search Tree의 일종으로써 BST에서 발생하는 편향성 문제를 색깔을 통해서 자체적으로 해결하는 자료구조입니다.