카테고리 없음

기술면접 자바-3 ( 컬렉션 )

pows1011 2023. 3. 29. 19:33

컬렉션 프레임워크란

더보기

컬렉션은 다수의 객체,데이터들을 지칭하는 말이고, 프레임워크는 틀(뼈대), 표준화된 프로그래밍 방식을 의미한다. 

즉 컬렉션 프레임워크는  다수의 데이터를 하나의 그룹으로 묶어 효율적으로 관리(추가,삭제,검색,저장) 하기 위해서 사용하는 라이브러리를 의미한다.

배열은 크기가 고정되어 있는데에 반해, 컬렉션 프레임워크는 가변적인 크기를 갖는 (Resizable) 등의 특징을 갖는다. 또한 데이터 삽입, 탐색, 정렬 등 편리한 API 를 다수 제공한다. 이런 이점으로 개발자는 배열보다는 적절한 컬렉션 클래스를 선택해 사용하는 것이 권장된다.

 

장점
  1. List,Queue,Set,Map 등의 인터페이스를 제공하고, 이를 구현하는 클래스를 제공하여 일관된 API를 사용가능
  2. 가변적인 저장 공간을 제공한다. 고정적인 저장 공간을 제공하는 배열에 대비되는 특징이다.
  3. 자료구조,알고리즘을 구현하기 위한 코드를 직접 작성할 필요 없이, 이미 구현된 컬렉션 클래스를 목적에 맞게 사용하면 된다.
  4. 제공되는 API의 코드는 검증되어있으며, 고도로 최적화 되어 있다.

구성 요소

  1. 인터페이스 : 각 컬렉션을 나타내는 추상 데이터에 대한 인터페이스 (List,Set,Map 등) 클래스는 이 인터페이스를 구현하는 방식으로 작성되었기 때문에 상세 동작은 달라도 일관된 조작법으로 사용가능
  2. 클래스 : 컬렉션 별 인터페이스의 구현, 위에서 언급했듯 같은 List 컬렉션이더라도 목적에 따라 ArrayList,LinkedList등으로 상세 구현이 달라 질 수 있다.
  3. 알고리즘 : 컬렉션이 제공하는 연산,검색,정렬,셔플 등에 대한 메서드

CollectinFramework 종류

  • 리스트 (List) : 인덱스 순서로 요소를 저장한다. 중복된 데이터를 저장 할 수 있다.
    • 객체를 인덱스로 관리하기 때문에 객체를 저장하면 자동 인덱스가 부여되고 인덱스로 객체를 검색, 삭제할 수 있는 기능을 제공한다.
    • List 컬렉션은 객체 자체를 저장하는 것이 아니라 위와 같이 객체의 번지를 참조한다. 
    • 동일한 객체를 중복 저장할 수 있는데 이 경우 동일한 번지가 참조된다. null도 저장이 가능한데, 이 경우 해당 인덱스는 객체를 참조하지 않는다.
    • List 컬렉션을 구현하는 대표적인 클래스들은 ArrayList, LinkedList, Vector가 있다.
  • 큐 (Queue) : 데이터가 저장된 순서대로 출력되는 선입선출(FIFO)의 구조를 갖는 선형 자료 구조이다.
  • 집합 (Set) : 순서가 없으며, 데이터를 중복하여 저장할 수 없다. 집합 연산(합집합,교집합,차집합 등)을 지원한다.
    • List 컬렉션은 저장 순서를 유지하지만, Set 컬렉션은 저장 순서가 유지되지 않는다.
    • 또한 객체를 중복해서 저장할 수 없고, 하나의 null만 저장할 수 있다.
    • Set컬렉션은 순서 자체가 없으므로 인덱스로 객체를 검색해서 가져오는 get(index) 메소드도 없다. 대신 전체 객체를 대상으로 한 번씩 반복해서 가져오는 반복자(Iterator)를 제공한다.
    • Set 컬렉션을 구현하는 대표적인 클래스들은 HashSet과 TreeSet이 있다.
  • 맵 (Map) : Key-Value 쌍으로 데이터를 저장한다. 순서가 존재하지 않으며 Key가 중복될 수 없다.
    • 키(key)와 값(value)으로 구성된 객체를 저장하는 구조를 가지고 있다.
    • 키는 중복 저장될 수 없지만 값은 중복 저장될 수 있으며 중복된 key값이 들어온다면 기존의 값은 없어지고 새로운 값으로 대치된다.
    • 대표적인 클래스들은 HashMap, Hashtable, LinkedHashMap, TreeMap 등이 있다.
    • 리스트나 배열처럼 순차적으로 해당 요소 값을 구하지 않고 key를 통해 value를 얻는게 큰 특징이다.

선형 자료구조

더보기

자료구조 분류법은 많은 분류법이 있지만, 대표적으로 많이 분류되는 방법은 선형 자료구조(Linear Data Structure)과 비선형 자료구조(Nonlinear Data Structure)로 나눌 수도 있다. 이러한 분류를 보통 '형태에 따른 자료구조'라고 보고, 각 자료구조에 알맞게 구체화 된 것들을 '구현된 자료구조'이라고 한다.

 

선형 자료구조는 쉽게 말하면 데이터가 일렬로 연결된 형태라고 보면 된다. 우리가 흔히 쓰는 int[] 배열같은 것이라 생각하면 쉽다. 대표적으로 리스트(List), 큐(Queue),덱(Deque)이 있다.

 

비선형 자료구조는 선형 자료구조의 반대다. 일렬로 나열된 것이 아닌, 각 요소가 여러 개의 요소와 연결된 형태를 생각하면 된다. 쉽게 생각해서 거미줄 같다고 보면된다. 대표적인 비선형으로 그래프(Graph) , 트리(Tree)가 있다.

 

두가지에 포함되지 않는 자료구조인 집합(Set)이 있다.  set은 table에 가까운 자료구조라고 보면된다.

 

Array란

더보기

배열이란 선형 자료구조(Data Structure)중 하나로 동일한 타입의 연관된 데이터를 메모리에 연속적으로 저장하여 하나의 변수에 묶어서 관리하기 위한 자료 구조입니다. 가장 기본적인 자료구조인 만큼 C, Java, Python 등 거의 모든 언어에 구현되어 있습니다.

 

JAVA Map&구현체

더보기
  • Key와 Value의 한쌍으로 이루어지는 데이터의 집합.
  • Key에 대한 중복이 없으며 순서를 보장하지 않습니다.
  • 뛰어난 검색 속도를 가집니다.
  • 인덱스가 따로 존재하지 않기 때문에 iterator를 사용합니다.
  • 데이터 저장시 빈공간을 찾아서 저장한다.
  1. HashMap
    • Entry<K,V>의 배열로 저장되며, key 값의 hashCode를 index로 Array에 값이 저장된다.
    • 내부 Hash값에 따라서 키 순서가 정해지므로 특정 규칙없이 출력된다.
    • Key와 Value에 Null값을 허용한다.
    • hashCode를 index key로 찾기때문에 검색 속도가 매우 빠르다.
    • 대용량 데이터 관리에 좋은 성능을 발휘한다.
    • 순서를 보장하지 않는다.
  2. LinkHashMap
    • HashMap을 상속받으며, Linked List로 저장된다.
    • 기본적으로 HashMap과 똑같으나, 삽입한 순서가 보장된다.
    • 입력 순서대로 출력된다
    • HashMap보다 LinkedHashMap의 성능이 약간 더 우세하지만, 전체적인 큰 차이는 없다. → HashMap은 순서를 보장하지 않을떄, LinkedHashMap은 순서를 보장할 때 사용한다.
  3. TreeMap
    •  HashMap과 다르게 Entry가 이름 그대로 Tree구조로 이루어져 있는 것이 특징
    • 일반적으로 HashMap보다 성능이 떨어지지만, 정렬된 상태로 Map을 유지해야 하거나, 정렬된 데이터를 조회해야 할 경우 효율적이다.
  4. HashTable
    • HashMap과는 구조가 비슷하지만, 용도는 아예 다르다.
    • Key와 Value를 1:1형태로 가지며, 동기화가 이루어진다.
    • Value에 Null이 불가능,
    • HashMap은 단일 스레드에서 유리하고, HashTable은 동기화를 보장하기 때문에 멀티쓰레드에서 유용하다.
    • Java1.5이전 현재는 잘 사용되지 않는다.

JAVA LIST & 구현체

더보기
  • 순서가 있고 중복을 허용합니다.
  • 인덱스로 원소에 접근이 가능합니다.
  • 크기가 가변적입니다.
  • 데이터 저장시 동일 공간에 뭉텅이로 저장이 된다.
  1. LinkedList
    • 양방향 포인터 구조로 데이터 삽입,삭제가 빠르다
    • ArrayList보다 검색이 느리다.
  2. ArrayList
    • 단방향 포인터 구조로 데이터 순차적 접근에 강점을 가진다.
    • 배열을 기반으로 데이터를 저장한다.
    • 데이터 삽입,삭제가 느리다
    • 데이터 검색이 빠르다.

 

장점

  • 가변적인 배열, 배열이 자동으로 늘어난다
  • 비어있는 데이터공간이 없다.

단점

  • 원하는 데이터가 뒤에 위차할 경우, 검색 속도가 느려질 수있다. ( 순회를 하기 때문에 )

JAVA SET & 구현체

더보기
  • 데이터의 집합이며 순서가 없고 중복된 데이터를 허용하지 않습니다.
  • 중복되지 않은 데이터를 구할 때 유용합니다.
  • 빠른 검색 속도를 가집니다.
  • 인덱스가 따로 존재하지 않기 때문에 iterator를 사용합니다.
  1. HashSet
    • 인스터스의 해시값을 기준으로 저장하기 때문에 순서를 보장하지 않는다.
    • Null값을 허용한다.
    • TreeSet보다 삽입,삭제가 빠르다.
  2. LinkedHashSet
    • 입력된 순서를 보장한다.
  3. TreeSet
    • 이진 탐색트리(Red-Black Tree)를 기반으로 한다.
    • 데이터들이 오름차순으로 정렬된다.
    • 데이터 삽입,삭제에는 시간이 걸리지만 검색,정렬이 빠르다.