Computer Science/Data Structure
선형자료구조 총정리
simDev1234
2022. 7. 12. 09:43
| 자료구조란?
- 자료를 목적에 따라 효율적으로 관리하기 위한 구조이다.
- 데이터를 CRUD할 때 유용하다.
- 적절히 사용하면 속도를 높히고, 메모리 사용도 줄일 수 있다.
| 자료구조의 분류
| 분류 | 특징 | 종류 |
| 선형 자료구조 | 데이터가 1:1관계로 들어가있다. | 배열, 연결리스트, 스택/큐/데크, 해시테이블 |
| 비선형 자료구조 | 데이터가 1:N, N:N 관계로 들어가 있다. | 트리, 그래프, 힙/우선순위 큐, 트라이 |
* 선형 자료구조는 기차처럼 길쭉하게 하나의 몸으로 구성되어 있다.
* 자료구조를 직접 구현하여(=추상 자료형) 사용할 수도 있다.
| 선형 자료 구조
| 종류 | 구분 | 내용 | 언제 쓰는 게 좋을까 |
| Array | 특징 | - 정해진 크기만큼 공간 할당 - 데이터가 연속적으로 하나씩 저장되어 있다. - 데이터와 인덱스가 1 : 1로 매칭 |
- 많은 양의 데이터를 다룰때 - 특정 위치 자료를 빠르게 선택할때 |
| 장점 | - 인덱스를 통해 빠르게 데이터에 접근할 수 있다. | ||
| 단점 | - 길이를 미리 설정해야 한다. | ||
| ArrayList | 특징 | - 가변 길이 배열 - 삽입 & 삭제 시, 배열을 새로 생성하고 복사한다. |
|
| 장점 | - 크기가 고정되어 있지 않다 (유동적) | ||
| 단점 | - 처음 또는 중간에 데이터를 삽입하거나 삭제할 때마다 배열을 새로 생성&복사하거나, 데이터를 모두 앞으로 미뤄야 한다. |
||
| LinkedList |
특징 | - 각 노드가 연결된 상태 - 각 노드의 메모리 주소는 항상 연속적이지 않다. - head / tail (양방향 이상) |
- 자료의 삽입과 삭제가 많은 경우 |
| 장점 | - 데이터의 삽입 및 삭제가 잦을 때 유리 * 삽입, 삭제 시 새로운 배열 생성 없이 링크만 연결한다. |
||
| 단점 | - 특정 인덱스를 조회하는 데 시간이 O(n)만큼 소요된다. * 처음~끝까지 인덱스를 돌기 때문에 Array보다 느리다. |
||
| 양방향 | - 각 노드가 prev / next 두 가지의 연결점을 가진다. | ||
| 원형 | - head -> tail -> head 식으로 원형으로 연결된 상태 | ||
| Stack | 특징 | - 후입선출 - top / bottom - push, pop, peek |
- 데이터가 입력된 순서의 역순으로 처리되어야 할 때 Ex. - 함수 콜스택,역추적,인터럽트 처리 - 재귀, DFS - 괄호 검사, 후위 연산, 문자열 역순출력, 실행취소 |
| 장점 | - top을 통한 접근, 삽입, 삭제가 빠르다. (시간복잡도 O(1)) |
||
| 단점 | - top 이외의 데이터에 접근 불가(탐색x) | ||
| Queue | 특징 | - 선입선출 - front / rear - enqueue(offer), dequeue(poll) |
- 데이터를 순차적으로 삽입하고 꺼낼 때 Ex. - 요세푸스 순열, 프로세스 관리, 대기 순서 관리(프린트 대기열) - BFS |
| 장점 | - front/rear를 통한 접근, 삽입, 삭제가 빠르다. (시간복잡도 O(1)) |
||
| 단점 | - 중간 위치의 데이터에 접근 불가 | ||
| Deque | 특징 | = double-ended queue, stack + queue - 양쪽에서 삽입 삭제가 가능 - front / rear - add(offer), remove(poll) - addFirst, addLast, removeFirst, removeLast |
- 데이터를 앞, 뒤쪽에서 삽입/삭제 처리 필요할 때 Ex. 팰린드롬 찾기, 카드묶음의 순서 변경하기 등 |
| 장점 | - front / rear 양쪽을 통한 삽입, 삭제가 빠르다 (시간복잡도 O(1)) - Stack, Queue와 달리 idx를 통해 임의 원소에 접근 가능 - 새로운 원소 삽입 시 메모리를 재할당하지 않고 메모리 블록을 재할당하여 삽입한다.(chunk 사용) |
||
| 단점 | - 중간 위치에 데이터를 삽입, 삭제가 어렵다 | ||
| Scroll | - 입력제한 데크 - 한 쪽의 입력을 제한한 데크 |
||
| Shelf | - 출력제한 데크 - 한 쪽의 출력을 제한한 데크 |
||
| HashTable | 특징 | - 해싱 함수를 통해 키 -> 해시로 변환한다 - key + value |
- 특정 키와 값을 연결할 때(알파벳-단어, 사전, 전화번호부) - 중복을 제거해야할 때(전체 명단 중 투표 여부 확인) |
| 장점 | - 해시 충돌이 없을 때 검색, 삽입, 삭제가 빠르다 (시간복잡도 : 평균 O(1), 최악 O(n)) - 보안성이 높다 (Key와 Hash간의 연관성X) - 데이터 캐싱에 자주 사용된다. - 중복 제거에 유리하다. |
||
| 단점 | - 해시 충돌 : key1과 key2가 해시함수를 거쳐 동일한 해시값(공간)을 가지는 상태 - 공간 복잡도가 커진다 - 순서가 있는 경우에는 맞지 않는다 - 해시 함수 의존도가 높다 |
* queue, deque에서 poll을 사용하면 비어있는 공간일지라도 null을 반환한다. 그러나 remove를 사용하면 예외가 발생
(offer / poll 보다는 add / remove 를 사용하는 것이 안정성면에서 더 좋다)
| 자바 컬렉션들의 시간 복잡도
1. List
| add() | remove() | get() | contains() | |
| ArrayList | O(1) or O(n) | O(1) or O(n) | O(1) | O(n) |
| LinkedList | O(1) | O(1) | O(n) | O(n) |
2. Set
| add() | contains() | next() | |
| HashSet | O(1) | O(1) | O(h/n) |
| LinkedHashSet | O(1) | O(1) | O(1) |
| TreeSet | O(log n) | O(log n) | O(log n) |
3. Map
| add() | containsKey() | next() | |
| HashMap | O(1) | O(1) | O(h/n) |
| LinkedHashMap | O(1) | O(1) | O(1) |
| TreeMap | O(1) | O(1) | O(h/n) |
4. Queue
| offer() | peak() | poll() | size() | |
| LinkedList | O(1) | O(1) | O(1) | O(1) |
| ArrayDequeue | O(1) | O(1) | O(1) | O(1) |
| PriorityQueue | O(log n) | O(1) | O(log n) | O(1) |
[ 참조 ]
스택, 큐
데크
- https://hbase.tistory.com/128
- https://jee-young.tistory.com/31
해시테이블
- https://hee96-story.tistory.com/48
- https://jtoday.tistory.com/73
자바 컬렉션의 시간 복잡도