자료구조
Data Structure - '일련의 일정 타입들의 데이터 모임 또는 관계를 나타낸 구성체'
어떤 알고리즘 문제를 풀기 위해 문제를 해석한 다음 보통 자료구조를 선택한다. 자료구조를 선택하면 해당 자료구조에 맞는 알고리즘을 선텍하는데 보다 더 효율적인 알고리즘을 선택할 수 있다는 장점이 있다.(선후 관계가 바뀔 수 있다.)
- 선형 자료구조 - 데이터가 일렬로 연결된 형태. (예를 들면 int[] 배열) 대표적으로 리스트(List), 큐(Queue), 덱(Deque)이 있다.
- 비선형 자료구조 - 일렬로 나열된 것이 아닌, 각 요소가 여러 개의 요소와 연결된 형태를 생각하면 된다. 대표적으로 그래프(Graph)와 트리(Tree)가 있다.
- 집합(Set) - 두 가지 분류에 해당되지 않고 데이터가 연결된 형식이 아니다. table에 가까운 자료구조.
Java Collections Framework
점선은 구현관계이고, 실선은 확장 관계이다. (인터페이스 끼리는 다중 상속이 가능하다.) Collection을 구현한 클래스 및 인터페이스는 모드 java.util 패키지에 있다.
리스트(List)
대표적인 선형 자료구조로 주로 순서가 있는 데이터를 목록으로 이용할 수 있도록 만들어진 인터페이스이다.
배열의 기능 + 동적 크기 할당
- List Interface를 구현하는 클래스
- ArrayList
- LinkedList
- Vector (+ Vactor를 상속받은 Stack)
- List Interface에 선언된 대표적인 메서드
- ArrayList는 Object[] 배열을 사용하면서 내부 구현을 통해 동적으로 관리한다. 요소 접근(access elements)에서는 탁월한 성능을 보이나, 중간의 요소가 삽입, 삭제가 일어나는 경우 그 뒤의 요소들은 한 칸씩 밀어야 하거나 당겨야 하기 때문에 삽입, 삭제에서는 비효율적이다.
- LinkedList는 데이터와 주소로 이루어진 클래스를 만들어 서로 연결하는 방식이다. 데이터와 주소로 이루어진 클래스를 노드라고 하는데 각 노드는 이전의 노드와 다음의 노드를 연결하는 방식이다. 요소를 검색해야 할 경우 연결된 노드들을 모두 방문해야한다는 점에서 성능이 떨어지나, 해당 노드를 삭제, 삽입해야 할 경우 해당 노드의 링크를 끊거나 연결만 해주면 되기 때문에 삽입, 삭제에서는 매우 좋은 효율을 보인다.
- Vector는 기본적으로 ArrayList와 같다고 보면 된다. 항상 '동기화'를 지원한다. (여러 쓰레드가 동시에 데이터에 접큰하려하면 순차적으로 처리하도록 한다.) 멀티 쓰레드에서는 안전하지만, 단일 쓰레드에서도 동기화를 하기 때문에 ArrayList에 비해 성능이 약간 느리다.
- Stack은 LIFO(Last in Fist out) 또는 후입선출이라고 한다. 가장 대표적인 예시로는 웹페이지 '뒤로가기'가 있다.
/*
T는 객체 타입을 의미하며 기본적으로
Integer, String, Double, Long 같은 Wrapper Class부터
사용자 정의 객체까지 가능하다.
ex) LinkedList<Integer> list = new LinkedList<>();
primitive type은 불가능하다.
*/
// 방법 1
ArrayList<T> arraylist = new ArrayList<>();
LinkedList<T> linkedlist = new LinkedList<>();
Vector<T> vector = new Vector<>();
Stack<T> stack = new Stack<>();
// 방법 2
List<T> arraylist = new ArrayList<>();
List<T> linkedlist = new LinkedList<>();
List<T> vector = new Vector<>();
List<T> stack = new Stack<>();
// Stack은 Vector를 상속하기 때문에 아래와 같이 생성할 수 있다.
Vector<T> stack = new Stack<>();큐(Queue)
선형 자료구조로 주로 순서가 있는 데이트럴 기반으로 선입선출(FIFO : First-in First-out)을 위해 만들어진 인터페이스이다.
Queue는 한쪽 방향으로만(단방향) 삽입,삭제가 가능한 반면, Deque은 Double ended Queue라는 의미로 양쪽에서 삽입,삭제가 가능한 자료구조이다.
- Queue/Deque Interface를 구현하는 클래스
- LinkedList
- ArrayDeque
- PriorityQueue
- Queue/Deque Interface에 선언된 대표적인 메서드
LinkedList는 List(리스트)를 구현하기도 하지만, Deque(덱)도 구현한다. 그리고 Deque Interface는 Queue Interface를 상속받는다.
즉, LinkedList는 사실상 3가지 용도로 쓸 수 있다.
1. List
2. Deque
3. Queue
Deque 또는 Queue를 LinkedList 처럼 Node 객체로 연결해서 관리하길 원한다면 LinkedList를 쓰면 된다. 원리 자체는 크게 다르지 않기 때문에 LinkedList 하나에 다중 인터페이스를 포함하고 있는 것이다.
일반적인 큐와 덱을 사용하고자 한다면 LinkedList로 생성해서 선언하면 된다.Queue<T> queue = new LinkedList<>(); Deque<T> deque = new LinkedList<>();
- PriorityQueue(우선순위 큐)
'데이터 우선순위'에 기반하여 우선순위가 높은 데이터가 먼저 나오는 원리이다. 따로 정렬방식을 지정하지 않는다면 낮은 숫자가 높은 우선순위를 갖는다. 주어진 데이터들 중 최댓값, 혹은 최솟값을 꺼내올 때 매우 유용하게 사용될 수 있다. 다만, 사용자가 정의한 객체를 타입으로 쓸 경우 반드시 Comparator 또는 Comparable을 통해 정렬방식을 구현해주어야 한다.
/*
T는 객체 타입을 의미하며 기본적으로
Integer, String, Double, Long 같은 Wrapper Class부터
사용자 정의 객체까지 가능하다.
단, primitive type은 불가능하다.
*/
ArrayDeque<T> arraydeque = new ArrayDeque<>();
PriorityQueue<T> priorityqueue = new PriorityQueue<>();
Deque<T> arraydeque = new ArrayDeque<>();
Deque<T> linkedlistdeque = new LinkedList<>();
Queue<T> arraydeque = new ArrayDeque<>();
Queue<T> linkedlistdeque = new LinkedList<>();
Queue<T> priorityqueue = new PriorityQueue<>();셋(Set)
데이터를 중복해서 저장할 수 없고, 입력 순서대로의 저장 순서를 보장하지 않는다. (다만 LinkedHashSet은 입력 순서대로 저장순서를 보장한다.)
- Set/SortedSet Interface를 구현하는 클래스
- HashSet
- LinkedHashSet
- TreeSet
- Set/SortedSet Interface에 선언된 대표적인 메서드
- HashSet은 가장 기본적인 Set 컬렉션의 클래스인데, 입력 순서를 보장하지 않고, 순서도 마찬가지로 보장하지 않는다. '중복확인'에 쓰이는 것이 대표적이다. hash에 의해 데이터의 위치를 특정시켜 해당 데이터를 빠르게 색인할 수 있게 만든 것이다. 삽입, 삭제, 색인이 매우 빠른 컬렉션 중 하나이다.
- LinkedHashSet은 중복은 허용하지 않으면서 순서를 보장받고 싶은 경우에 사용된다.
- TreeSet은 Set Interface를 상속받은 SortedSet Interface를 구현하고 있다. 데이터의 '가중치에 따른 순서'대로 정렬되어 보장한다는 것이다. 중복되지 않으면서 특정규칙에 의해 정렬된 형태의 집합을 쓰고 싶을 때 쓴다. 정렬된 형태로 있다보니 특정 구간의 집합요소들을 탐색할 때 매우 유용하다. (Tree라는 자료구조 자체가 데이터를 일정순서에 의해 정렬하는 구조이다. 거기에 더해진 것이 Set인 중복값 방지 자료구조 인 것이다.)
/*
T는 객체 타입을 의미하며 기본적으로
Integer, String, Double, Long 같은 Wrapper Class부터
사용자 정의 객체까지 가능하다.
단, primitive type은 불가능하다.
*/
HashSet<T> hashset = new HashSet<>();
LinkedHashSet<T> linkedhashset = new LinkedHashSet<>();
TreeSet<T> treeset = new TreeSet<>();
SortedSet<T> treeset = new TreeSet<>();
Set<T> hashset = new HashSet<>();
Set<T> linkedhashset = new LinkedHashSet<>();
Set<T> treeset = new TreeSet<>();
출처 및 참고 : https://st-lab.tistory.com/142
