Data Structure(자료구조)
- 대규모 데이터들을 관리 및 활용에 용이하게 한다.
- 데이터베이스에서 원하는 데이터를 찾을 수 있게 한다.
- 사용자가 원하는 또는 프로그램이 필요한 맞춤 알고리즘을 설계할 수 있다.
- 사용자들의 여러 요청을 한 번에 처리할 수 있다.
- 데이터 처리 과정을 단순화하면서 처리 속도를 향상시킬 수 있다.
꼭 알아야 할 7가지 자료구조
배열(Array)
배열은 가장 기본적인 자료구조이다. 배열은 생성시 설정된 크기가 고정되고, 각 셀에는 인덱스 번호가 부여된다. 배열을 활용 시 부여된 인덱스를 통해 해당 셀 안에 있는 데이터에 접근할 수 있다.
[시간 복잡도]
| 자료구조 | 가져오기(값) | 추가하기 | 삭제하기 |
|---|---|---|---|
| 배열(Array) | O(n) | O(n) | O(n) |
[장점]
- 바로 만들어서 활용하기 쉽다.
- 더 복잡한 자료구조의 기초가 될 수 있다.
- 원하는 데이터를 효율적으로 탐색/가져올 수 있다.
- 정렬에 용이하다.
[단점]
- 데이터를 저장할 수 있는 메모리 크기가 고정되어있다.
- 데이터 추가/삭제 방법이 비효율적이다.
- 구조 재구성 시 정렬하는 방식이 비효율적이다.
스택(Stack)
스택은 순서가 보존되는 선형 데이터 구조 유형이다. 가장 마지막 요소부터 처리하는 LIFO(Last In First Out)특성을 갖고있다. 스택은 쌓여있는 접시 더미와 같이 동작한다. 새로운 접시가 쌓일때도 맨 위에서 쌓이고, 접시를 가져갈 때도 맨 위에서 가져가는 것과 같다.
[시간 복잡도]
| 자료구조 | 가져오기(값) | 추가하기 | 삭제하기 |
|---|---|---|---|
| 스택(Stack) | O(n) | O(1) | O(1) |
[장점]
- 동적인 메모리 크기
- 데이터를 받는 순서대로 정렬된다.
- 빠른 런타임
[단점]
- 한 번에 하나의 데이터만 처리가능하다.
큐(Queue)
큐는 스택과 비슷하지만 가장 먼저 입력된 요소를 처리하는 FIFO(First In First Out)특성을 갖고있다. 큐는 놀이공원에서 서는 줄과 같이 동작한다. 사람들이 맨 끝에 줄을 서고, 맨 앞에서부터 놀이기구에 탑승하는 것과 같다.
[시간 복잡도]
| 자료구조 | 가져오기(값) | 추가하기 | 삭제하기 |
|---|---|---|---|
| 큐(Queue) | O(n) | O(1) | O(1) |
[장점]
- 동적인 메모리 크기
- 데이터를 받는 순서대로 정렬된다.
- 빠른 런타임
[단점]
- 가장 오래된 요소만 가져온다.
- 한번에 하나의 데이터만 처리 가능하다.
연결 리스트(Linked list)
연결리스트는 데이터의 물리적 배치를 사용하지 않는 구조이다. 각 요소는 노드라는 것에 저장되는데 다음 노드 연결에 대한 포인터 또는 주소가 포함된 또 다른 노드에 저장된다. 모든 노드가 연결될때 까지 반복이 되어 노드의 연결로 이루어진 자료구조다.
연결 리스트에는 단일 연결 리스트, 이중 연결 리스트가 있다.
[시간 복잡도]
| 자료구조 | 가져오기(값) | 추가하기 | 삭제하기 |
|---|---|---|---|
| 연결리스트(Linked list) | O(n) | O(1) | O(1) |
[장점]
- 새로운 요소들의 추가 및 삭제가 용이하고 효율적이다.
- 배열처럼 메모리에 연속적으로 위치하지 않는다.
- 배열처럼 구조의 재구성이 필요없다.
- 동적인 메모리 크기
- 메모리를 더 효율적으로 쓸 수 있기 때문에 대용량 데이터 처리에 적합하다.
[단점]
- 배열보다 메모리를 더 사용한다.
- 처음부터 끝까지 순회하기 때문에 원하는 값을 비효율적으로 검색한다.
- 노드를 반대 방향으로 검색할 때 비효율적이다. (이중 연결 리스트의 경우)
해시 테이블(Hash table)
해시 테이블은 대량의 정보를 저장하고 특정 요소를 효율적으로 검색할 수 있는 복잡한 데이터구조이다. 이 데이터 구조는 테이블 내에 더 작은 서브그룹인 버킷에 키와 값의 쌍을 저장한다. 해시 테이블은 키를 저장할 때 메모리 공간을 덜 사용할 수 있도록 키를 해시 함수를 통해 해시라는 특정 숫자값으로 변환한다. 해시 테이블은 필요할 때만 메모리 크기를 늘리고, 가능한 작은 크기를 유지한다.
키는 검색 시 사용되는 문자열이고 값은 해당 키와 쌍을 이룬 데이터다. 검색된 각 키는 미리 정의된 해시함수를 통해 해시값을 받고 버킷을 가리킨다. 해시 숫자는 버킷의 인덱스를 의미한다. 버킷에서 검색할 때 입력된 키를 찾고 해당 키와 관련된 값을 반환한다.
[시간 복잡도]
| 자료구조 | 가져오기(값) | 추가하기 | 삭제하기 |
|---|---|---|---|
| 해시테이블(Hash Table) | O(1) | O(1) | O(1) |
[장점]
- 새로운 요소들의 추가, 삭제가 용이하고 효율적이다.
- 원하는 값의 검색/가져오기가 빠르고 효율적이다.
- 동적인 메모리 크기
[단점]
- 충돌이 일어날 수 있다. (입력된 키의 해시 값이 이미 데이터가 저장된 버킷을 가리킬 수 있다.)
- 충돌이 자주 일어날 수 있으며 해시함수의 정비가 필요한 경우가 많다.
그래프(Graph)
그래프틑 노드 사이에 엣지가 있는 자료구조이다. 그래프는 방향이 있을 수 있고 없을 수도 있다. 그래프로 구조를 어떻게 설계 그리고 무엇을 하고 싶냐에 따라 시간복잡도가 달라진다.
[시간 복잡도]
| 자료구조 | 가져오기(값) | 노드/엣지 추가하기 | 노드 삭제하기 | 엣지 삭제하기 |
|---|---|---|---|---|
| 그래프(Graph) | O(N+E) | O(1) | O(N+E) | O(E) |
[장점]
- 새로운 요소들의 추가/삭제가 용이하고 효율적이다.
- 구조의 응용이 가능하다.
[단점]
- 충돌이 발생할 수 있다.
