[자료구조] Collection

선형 자료구조

• 선형 자료구조는 데이터가 일렬로 연결된 형태라고 보면 된다. 예를 들면 자주 사용하는 int[] 배열같은 것
• 대표적으로 리스트(List)와 큐(Queue), 덱(Deque)이 있다.

비선형 자료구조

• 일렬로 나열된 것이 아닌, 각 요소가 여러 개의 요소와 연결 된 형태이다. 거미줄을 상상하면 편하게 이해 할 수 있다.
• 대표적으로 그래프(Graph)와 트리(Tree)이 있다.

Java Collections FrameWork

• 일정 타입의 데이터들이 모여 쉽게 가공 할 수 있도록 지원하는 자료구조들의 뼈대(기본 구조)라는 의미를 가지고 있다.
• 자바에서 제공하는 Collection은 크게 3가지 인터페이스로 나뉘어 있다.
  • List(리스크)
  • Queue(큐)
  • Set(집합)
• 위에 3가지 인터페이스를 구현 한 것들이 있다. Collection을 구현한 클래스 및 인터페이스들은 모두 java.util 패키지에 있다.

List[리스트]

• List Interface는 대표적인 선형 자료구조로 주로 순서가 있는 데이터를 목록으로 이용할 수 있도록 만들어진 인터페이스다.
• List Interface를 구현하는 클래스
  1.  ArrayList
     • Object[] 배열을 사용하면서 내부 구현을 통해 동적으로 관리를 한다.
     • 최상위 타입인 Object 타입으로 배열을 생성하여 사용하기 때문에 요소 접근(access elements) 에서는 탁월한 성능을 보인다.
     • 중간의 요소가 삽입, 삭제가 일어나는 경우 그 뒤의 요소들은 한 칸씩 밀어야 하거나 당겨야 하기 때문에 삽입, 삭제에서는 비효율적인 모습을 보인다.
  2. LinkedList
     • 데이터와 주소로 이루어진 클래스를 만들어 서로 연결하는 방식이다.
     • 데이터와 주소로 이루어진 클래스를 Node(노드)라고 하는데, 각 노드는 이전의 노드와 다음 노드를 연결하는 방식인 것이다.(이중 연결 리스트라고도 함) 즉 객체끼리 연결한 방식이다.
     • 검색에서는 성능이 떨어질 수 있으나, 해당 노드를 삭제, 삽입해야 할 경우 해당 노드의 링크를 끊거나 연결만 해주면 되기 때문에 삽입, 삭제에서는 매우 좋은 효율을 보인다.
  3. Vector(+ Vector를 상속받은 Stack)
     • 자주 사용되지는 않는 클래스이며 기본적으로는 ArrayList와 거의 같다고 보면 된다.
     • Vector는 Collection Framework가 도입되기 전부터 지원하던 클래스다.
     • 항상 '동기화'를 지원한다. 여러 쓰레드가 동시에 데이터에 접근하려하면 순차적으로 처리하도록 한다.
     • 멀티쓰레드에서는 안전할 수 있지만 단일 쓰레드에서도 동기화를 하기 때문에 ArrayList에 비해 성능이 느릴 수 있다.
  4. Stack
     • 우리가 흔히 생각하는 쌓아 올린다는 뜻이다. 개발용어로 말하면 LIFO(Last in First out) 또는 후입선출이라고 한다.

Queue [큐]

• Queue Interface(큐 인터페이스)는 선형 자료구조로 주로 순서가 있는 데이터를 기반으로 '선입선출, FIFO : First-in-First-out'을 위해 만들어진 인터페이스다.
• 흔히 스택과 많이 비교를 하는 자료구조이다
• 자바에서 '일반적인 큐'를 사용하고자 한다면 LinkedList로 생성하여 Queue로 선언하면 된다.

Set [셋 / 세트]

• Set는 말 그대로 '집합'이다. 
• 데이터를 중복해서 저장 할 수 없음 , 입력 순서대로의 저장 순서를 보장하지 않음. (다만 LinkedHashSet은 Set임에도 불구하고 입력 순서대로의 저장순서를 보장하고 있다. 그러나 데이터를 중복해서 저장할 수 없는 것은 같다.
• Set을 구현하는 클래스
  1. HashSet
     • 가장 기본적인 Set 컬렉션의 클래스이며 입력 순서를 보장하지 않고, 순서도 마찬가지로 보장되지 않는다.
     • hash에 의해 데이터의 위치를 특정시켜 해당 데이터를 빠르게 색인(search)할 수 있게 만든 것이다. 즉 Hash 기능과 Set 컬렉션이 합쳐진 것이 HashSet이다. 그렇기 때문에 삽입, 삭제, 색인이 매우 빠른 컬렉션 중 하나다.
  2. LinkedHashSet
     
     • add() 메소드를 통해 요소들을 넣은 순서대로 연결한다. 즉 LinkedList의 첫번째 요소부터 차례대로 출력하면 입력했던 순서대로 출력된다는 것이고 이는 순서를 보장한다는 의미이다.
     • Set의 경우 중복 허용 x , 순서를 보장하지 않는데 '중복은 허용하지 않으면서 순서를 보장받고 싶은경우'에는 불편할 수 밖에 없다. 이를 보완하기 위해 LinkedHashSet이 존재하는 것이라고 봐도 무방하다.
  3. TreeSet
     
     • HashSet과 마찬가지로 입력 순서대로의 저장 순서를 보장하지 않으며 중복 데이터 또한 넣지 못한다.
     • 가중치에 따른 순서대로 정렬되어 보장한다는 것을 의미한다.

 

Collection에 대해 간단하게 알아보고 종류를 정리해보았다. 이제 백준 알고리즘 문제를 풀며 나오는 자료구조를 깊이 공부하고 정리해서 블로그에 기록해야겠다. 개인적으로 Stack에 대해 먼저 공부를 해보고 싶다는 생각이 많아 Stack에 대한 공부를 빠르게 시작해야겠다.

 

해당 요점정리는 https://st-lab.tistory.com/142 님의 블로그를 보며 정리하였습니다.