자료구조는 Data Structure라고 하는데, 데이터 구조, 좀 더 자세하 설명하자면
'일련의 일정 타입들의 데이터 모임 또는 관계를 나타낸 구성체' 라고 할 수 있다.
자료구조와 알고리즘은 의존적인 관계이기 때문에 자료구조에 대한 이해가 있어야한다.
알고리즘 문제를 풀기 위해 보통 자료 구조를 선택한다. 자료구조를 선택하면 해당 자료구조에 맞는 알고리즘을 선택하는데 보다 더 효율적인 알고리즘을 선택할 수 있다는 장점이 있다.
예를 들어 순서이 있는 데이터들이 삽입(insert/add), 삭제(remove,delete)가
빈번하게 발생한다면 LinkedList, 아닐경우 ArrayList를 사용하듯이
각 자료구조별 장단점을 갖고있기 때문에 알고리즘 선택에 있어서 중요한 역할을 담당한다.
대표적으로 선형 자료구조(Linear Data Structure)과 비선형 자료주고(NonLinear Data Structure)로 나눌 수 있는데 이러한 분류를 보통 '형태에 따른 자료구조'라고 보고, 각 자료 구조에 맞게 구제화 된 것들을 '구현된 자료구조'리고 한다.
<선형 자료구조>
데이터가 일렬로 연결된 형태. 우리가 흔히 쓰는 int[] 배열같은 것
대표적으로 리스트(List),큐(Queue),덱(Deque)
<비선형 자료구조>
선형 자료구조의 반대. 일렬로 나열된 것이 아닌, 각 요소가 여러 개의 연결된 형태. 쉽게 말해 거미줄 같다
그래프(Graph), 트리(Tree)
두 가지 분류에 해당되지 않는 자료구조가 있는데 집합(Set)이다. 보통 기타자료구조 또는 집합 자료구조로 본다. 집합의 경우는 데이터가 연결된 형식이 아니다.
파일구조는 순차파일, 색인파일, 직접파일이 있다.
Java - 자바 언어
Collections - 데이터들을 쉽게 다루기 위해 모아놓은 것들을 가공 처리 할 수 있도록 지원하는 자료구조
Framework - 뼈대(기본구조)
= 일정 타입의 데이터들이 모여 쉽게 가공할 수 있도록 지원하는 자료구조들의 뼈대(기본구조)
기본 구조라면 Interface(인터페이스)가 떠오른다.
자바에서 제공하는 Collection은 크게 3가지 인터페이스로 나뉘어져있다.
크게 List(리스트), Queue(큐), Set(집합)으로 나뉘어 있다.
'형태에 따른 자료구조'라고 보면된다. 그리고 각 분야별로 '구현'된 것 들이 있다.
점선은 구현 관계, 실선은 확장 관계, 인터페이스끼리는 다중 상속이 가능하다.
또한 Collection을 구현한 클래스 및 인터페이스들은 모두 java.util 패키지에 있다
List,Queue,Set 이 3가지의 형태에 따른 자료구조들이 있다.
Queue와 Set에는 조금 더 구체화되어 Deque, SortedSet이라는 형태에 따른 자료 구조가 있다
그리고 이 형태에 따른 자료구조들은 각각 구현이 되어 class로 제공된다.
녹색 부분이 구현된 자료구조 라고 보면 된다.
자바에서 Interface를 class파일에서 쓰면 보통 구현한다라고 한다.
Iterable은 반복가능한 정도로 이해하면 된다.
Collection Interface 상위에 있는 이유가 뭘까?
저기서 제공하고 있는 클래스들은 모두 객체형태로 내부 구현 또한 대게 각각의 객체를 갖고 움직인다. (오브젝트 배열 형태아님) 그래서 객체의 데이터들을 모두 순회하면서 출력하려면 사용자들이 각각의 데이터 순회 방법을 알거나 하나씩 get() 같은 메소드르를 통해 데이터를 하나씩 꺼내와야 한다
Map은 Collection이 아니다?
Java에서는 Collection이라고 보지 않는다.
mapping이 collections라고 보기 힘들고, collections또한 mapping이라고 보기 힘들다는 것
그렇기 때문에 의도적으로 Collections Interface를 상속하지 않았다는 뜻
Collection Interface을 상속하여 구현된 클래스들은 모두 단일 데이터를 처리하지만,
Map은 key,value가 쌍을 이루며 처리하기 때문에 굳이 Map을 위해 Collection에서 Map과 관련한 메소드를 만들고 Map에서 Collection을 상속할 필요가 없다,
Iterable은 반복가능한 형태를 의미하는데, Map은 구조상 키에 대응하는 값이라는 특징을 가지고 있다.
반복자로 뱉기위해서는 키와 밸류중 어느 것으로 반복할 지 모른다.
Map은 Collection이라는 것이 의미적으로는 맞을 수 있지만, 자바에선 컬렉션이라고 보지 않는다
List[리스트]
대표적인 선형 자료구조. 주로 순서가 있는 데이터를 목록으로 이용할 수 있도록 만들어진 인터페이스
int[] array = new int[10]처럼 선언한 배열의 경우 정해진 공간 외에는 사용하지 못한다.
이런 단점을 보완하기 위해 List를 통해 구현된 클래스들은 '동적 크기'를 가지며 배열처럼 사용할 수 있게 되어있다.
배열의 기능 + 동적 크기 할당
< List Interface를 구현하는 클래스 >
1. ArrayList
2. LinkedList
3. Vector(+Vector을 상속받은 Stack)
< List Interface에 선언된 대표적인 메소드 >
ArrayList는 Object[] 배열을 사용하면서 내부 구현을 통해 동적으로 관리한다.
우리가 흔히 쓰는 primitive 배열(int[])와 유사한 형태
최상위 타입인 Object 타입으로 배열을 생성하여 사용하기 때문에 요소 접근에서는 탁월한 성능을 보이나, 중간의 요소가 삽입, 삭제가 일어나는 경우 그 뒤의 요소들은 한 칸씩 밀어야 하거나 당겨야 하기 때문에 삽입, 삭제에서는 비효율적인 모습을 보인다.
LinkedList는 데이터와 주소로 이루어진 클래스를 만들어 서료 연결하는 방식
데이터와 주소로 이루어진 클래스를 Node(노드)라고 하는데, 각 노드는 이전의 노드와 다음 노드를 연결하는 방식이다. (이중 연결 리스트) 즉, 객체끼리 연결한 방식이다. 요소를 검색해야 할 경우 처음 노드부터 찾으려는 노드가 나올 때 까지 연결된 노드들을 모두 방문해야한다는 점에서 성능이 떨어지나, 해당 노드를 삭제, 삽입해야할 경우 해당 노드의 링크를 끊거나 연결만 해주면 되기 때문에 삽입, 삭제에서는 매우 좋은 효율을 보인다.
Vector은 기본적으로 ArrayList와 거의 같다고 보면 되는데, Object[] 배열을 사용하며 요소 접근에서 빠른 성능을 보인다. 항상 동기화를 지원한다. 여러 쓰레드가 동시에 데이터에 접근하려하면 순차적으로 처리하도록 한다. 멀티 쓰레드에서는 안전하지만, 단일 쓰레드에서도 동기화를 하기 때문에 ArrayList에 비해 성능이 약간 느리다
Stack은 쌓아 올리는 것이다. LIFO(Last In First Out), 후입선출이라고 한다.
짐을 쌓으면 가장 마지막에 쌓은 짐이 가장 위에 있고, 짐을 뺄때도 가장 위에 있는 짐부터 빼게 된다.
대표적인 예시로는 웹페이지 뒤로가기가 있다. 우리가 새로운 페이지로 넘어갈 때마다 넘어가기 전 페이지를 스텍에 쌓고, 뒤로가기를 누른다면 가장 위에 있는 페이지부터 꺼내오는 방식이다.
참고로 Stack의 경우 Vector클래스를 상속받고 있고, java에서 지원하는 Stack 클래스의 메소드들도 모두 Vector에 있는 메소드를 이용하여 구현되고 있다.
/*
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<>();
new라는 생성자 뒤에 객체를 명시해주기 때문에 상위 타입인 List< T >로 해주어도 무방하다.
만약 부득이하게 list 종류를 중간에 바꿔야하는 경우 List< T >로 선언해주면 된다.
Queue[큐]
큐 인터페이스는 선형 자료구조로 주로 순서가 있는 데이터를 기반으로 선입선출(FIFO : First-in First-out)을 위해 만들어진 인터페이스다. 흔히 스택과 많이 비교를 하는 자료구조다.
큐는 간단히 10,20,30,40 순으로 데이터를 넣고, 데이터를 꺼낼 때(poll) 넣은 순서 그대로 10,20,30,40이 나오는 구조다. 이 때 가장 앞쪽에 있는 위치를 head(헤드)라고 부르고, 가장 후위(뒤)에 있는 위치를 tail(꼬리)라고 부른다. 예를들면 놀익구를 타기 위해 줄 서있는 모습을 상상하면 된다.
Collection 구조를 보면 알겠지만, Queue를 상속하고 있는 Deque(덱)이라는 인터페이스도 있다. 둘 다 같은 부류인데 Queue는 한쪽 반향으로만(단방향) 삽입 삭제가 가능한 반면, Deque는 Double ended Queue라는 의미로 양쪽에서 삽입, 삭제가 가능한 자료구조다. 즉, head에서도 접근 가능하며, tail에서도 접근 가능한 양방향 큐라고 보면된다. (Queue에서 확장된 형태)
예를 들지면 카드 덱을 생각하면 된다. 카드를 중간에서 뺼 수는 없고, 맨 위에 놓거나, 맨 아래 놓거나, 맨 위의 것을 빼거나, 맨 아래 것을 뺄 수 있다는 것을 생각하면 된다.
< Queue/Deque Interface를 구현하는 클래스 >
1. LinkedList
2. ArrayDeque
3. PriorityQueue
< Queue/Deque Interface에 선언된 대표적인 메소드 >
단순히 Deque는 양방향이기 때문에 헤드와 꼬리를 나누어 메소드가 더 생성되었을 뿐이다.
LinkedList는 리스트를 구현하기도 하지만, Deque도 구현한다. 그리고 덱 인터페이스는 큐 인터페이스를 상속받는다.
LinkedList는 사실상 3가지 용도로 쓸 수 있다.
1. List
2. Deque
3. Queue
Deque 또는 Queue를 LinkedList 처럼 Node 객체로 연결해서 관리하려면 LinkedList를 쓰면 된다.
반대로 ArryList처럼 Object[] 배열로 구현되어 있는 것은 ArrayDeque이다.
물론 LinkedList와 ArrayDeque 둘 다 Deque을 구현하고 있고, Deque은 Queue를 상속받기 때문에 Queue로도 쓰일 수 있다.
'일반적인 큐'를 사용하고자 한다면 LinkedList로 생성하여 Queue로 선언하면 되고, Deque(덱)도 마찬가지다.
Queue<T> queue = new LinkedList<>();
Deque<T> queue = new LinkedList<>();PriorityQueue란 '우선순위 큐'다. PriorityQueue는 '데이터 우선순위'에 기반하여 우선순위가 높은 데이터가 먼저 나오는 원리다. 따로 정렬방식을 지정하지 않는다면 낮은 숫자가 높은 우선 순위를 갖는다. 쉽게 생각하면 정렬메소드인 sort()와 같은 순서로 데이터 우선순위를 갖는다는 의미다
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[셋/세트]
Set(세트)는 말 그대로 '집합'이다. Set의 가장 큰 특징이라 하면 크게 두가지가 있다.
1. 데이터를 중복해서 저장할 수 없다
2. 입력 순서대로의 저장 순서를 보장하지 않는다.
다만 LinkedHashSet은 Set임에도 불구하고 입력 순서대로의 저장순서를 보장하고 있다.
그러나 데이터를 중복해서 저장할 수 없는 것은 같다
기본적으로 List계열은 index(Node)로 관리하기 때문에 add()같은 메소드를 쓰면 순서대로 저장되었다.
Queue 계열 또한 우선순위 큐(PriorityQueue)를 제외하고는 기본적으로 입력한 순서대로 객체가 연결되어 있다.
하지만 Set의 경우는 일반적으로 입력받은 순서와 상관없이 데이터를 집합시키기 때문에 입력받은 순서를 보장할 수 없다.
순서 보장이 안된다는 불편함을 개선시키기 위해 만들어져 있는 것이 LinkedHashSet이다. 만약 데이터 중복을 허용하고 싶지 않은데 입력 순서를 보장받고 싶다면 LinkedHashSet을 사용하면 된다.
그리고 Queue와 유사하게 Set을 상속받고 있는 SortedSet Interface도 있다.
<Set/SortedSet Interface를 구현하는 클래스>
1. HashSet
2. LinkedHashSet
3. TreeSet
<Set/ Interface에 선언된 대표적인 메소드>
Set Interface을 구현하는 클래스들은 HashSet, LinkedHashSet, TreeSet 이렇게 3가지가 있다.
좀더 구체적으로 TreeSet은 Set Interface를 상속받은 SortedSet Interface를 구현하고 있다.
그리고 Set의 가장 큰 특징은 '중복되는 데이터를 넣지 못한다는 점'이고,
LinkedHashSet을 제외하고 대부분의 Set은 '입력 순서대로의 저장순서를 보장하지 않는다는 점'이다.
HashSet은 가장 기본적인 Set 컬렉션의 클래스인데, 입력 순서를 보장하지 않고, 순서도 보장되지 않는다.
가장 쉽게 이해할 수 있는 예로는 닉네임이나 아이디를 생성할때 중복확인을 눌러 중복된 닉네임 또는 아이디인지 확인하는 것이다.
이는 데이터가 정렬되어있을 필요도 없고, 빠르게 중복되는 값인지만 찾으면 되기 때문에 유용한 방법이 될 수 있다.
hash에 의해 데이터의 위치를 특정시켜 해당 데이터를 빠르게 색인(search)할 수 있게 만든 것이다. 즉 Hash기능과 Set컬렉션이 합쳐진 것이 HashSet이다. 그렇게 때문에 삽입, 삭제, 검색이 매우 빠른 컬렉션 중 하나다
LinkedHashSet의 경우 이름에서 볼 수 있듯이 Link + Hash + Set 이 결합된 형태다. LinkedList에서 보면 add() 메소드를 통해 요소들을 넣은 순서대로 연결한다. 즉, LinkedList의 첫번째 요소부터 차례대로 출력하면 입력했던 순서대로 출력된다는 것이고 이는 순서를 보장한다는 의미다.
Set의 경우 기본적으로 입력 순서대로의 저장순서를 보장하지 않아 '중복은 허용하지 않으면서 순서를 보장받고 싶은경우'에는 불편할 수밖에 없다. 이를 보완하기 위해 존재하는 것이 바로 LinkedHashSet인 것이다. 실생활에서 그나마 예로 들자면 페이지를 열 때 만약 해당 페이지가 중복되경우 cache는 다시 적재할 필요는 없지만, 새로운 페이지를 할당해야 할 경우 최근에 사용되지 않은 cache을 비우고자 할 때, 가장 오래된 cache를 비우는 것이 현명할 것이다. 이를 LRU 알고리즘(Least Recently Used Algorithm)이라고 하는데, 이럴 때 입력된(저장된) 순서를 알아야 오래된 캐시를 비울 수 있다. 이에 적용할 수 있는 자료구조 중 하나다. (현실적으로는 LRU기법으로 LinkedHashMap이라는 자료구조가 대부분을 차지하고 있어 많이 쓰이진 않으나 그나마 이해하기 쉬운 예시를 위해..)
TreeSet은 HashSet과 마찬가지로 입력 순서대로의 저장 순서를 보장하지 않으며 중복 데이터 또한 넣지 못한다. 다만 특별한 점이 있다면 SortedSet Interface의 이름을 보면 알 수 있듯 이를 구현한 TreeSet은 데이터의 '가중치에 따른 순서'대로 정렬되어 보장한다는 것이다. 앞서 PriorityQueue를 생각해보자. 데이터들이 입력한 순서대로가 아닌 값에 따라 정렬되어 Queue에 담아진다. 마찬가지로 TreeSet은 '중복되지 않으면서 특정 규칙에 의해 정렬된 형태의 집합을 쓰고 싶을 때 쓴다. 정렬된 형태로 있다보니 특정 구간의 집합요소들을 탐색할 때 매우 유용하다.
(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<>();적절한 자료구조 사용하기
•ArrayList
•LinkedList
•Vector
•Stack
•Queue(by LinkedList)
•PriorityQueue
•Deque(by LinkedList)
•ArrayDeque
•HashSet
•LinkedHashSet
•TreeSet
어떤 상황에서 어떤 자료구조를 쓰는 것이 알맞을까?
