[Data Structure] 기본적인 자료구조 8가지 정리
기본적인 8가지 자료구조 모음
1. 배열 (Array)
배열은 데이터를 효율적으로 저장하고 관리하기 위한 기본적인 자료구조 중 하나이다.
배열은 동일한 데이터 타입을 가진 여러 항목들이 연속된 메모리 위치에 저장되는 구조이다.
배열의 각 요소는 인덱스를 통해 식별되며, 이 인덱스는 배열 내에서 요소의 위치를 나타낸다.
예를 들어, Array[0] = 11 은 배열 'Array' 의 1번째 위치 (인덱스 0) 의 값 11에 저장되어 있음을 의미한다.
배열의 인덱스는 보통 0부터 시작한다.
장점
1. 인덱스를 통해 배열의 어떤 요소에도 빠르게 접근 가능
2. 동일한 데이터 타입의 요소가 연속적으로 저장되어 메모리를 효율적으로 사용할 수 있음
3. 단일 변수를 통해 대량의 데이터를 관리해 데이터 처리 과정을 간결하게 만들 수 있음
단점
1. 대부분 프로그래밍 언어에서 배열은 생성 시점에 크기가 정해지며, 이후 크기를 동적으로 변경하기 어려움
2. 배열의 중간에 데이터를 삽입하거나 삭제하는 경우, 나머지 요소를 이동시켜야 하므로 시간이 많이 소요
3. 배열의 크기를 데이터의 최대 예상 개수에 맞추어 할당하면, 실제 사용되지 않는 공간이 발생할 수 있어 메모리 낭비
시간복잡도
1. 접근 : O(1) - 인덱스를 통해 배열의 어느 위치에도 즉시 접근
2. 검색 : O(n) - 특정 요소를 찾기 위해서는 최악의 경우 배열의 모든 요소 확인해야 함
3. 삽입/삭제 : O(n) - 배열의 중간에 요소를 삽입하거나 삭제하는 경우 나머지 요소를 이동시켜야 하므로 최악의 경우 배열의 모든 요소를 다루어야 함
❓ Question. 자바스크립트의 배열은 어떨까?
기본적인 배열의 개념과 자바스크립트 배열에서의 구현은 몇 가지 중요한 차이점이 있다.
이 차이점은 주로 자바스크립트의 동적 특성과 언어 설계 철학에서 기인한다.
기본적인 배열의 개념
1. 크기 고정 : 전통적인 배열은 생성 시점에 크기가 정해짐. 이 크기는 배열의 생명주기동안 변경 X
2. 동일 데이터 타입 : 일반적으로 배열은 동일한 데이터 타입의 요소로만 구성됨. (메모리 관리 효율적으로 하기 위해)
3. 연속적인 메모리 위치 : 배열의 모든 요소들은 메모리 상에서 연속적인 위치에 저장. (인덱스를 통해 빠르게 접근 위해)
자바스크립트 배열의 특징
1. 동적 크기 : 자바스크립트 배열은 생성 후에도 크기를 동적으로 변경 가능. 요소를 추가하거나 제거하면서 배열의 크기가 자동으로 조절됨
2. 다양한 데이터 타입 : 한 배열 내에 서로 다른 데이터 타입 가능. (자바스크립트의 동적 타이핑 특성 때문)
3. 객체 : 자바스크립트 배열은 실제로는 'Array' 객체의 인스턴스임. 이는 배열이 고유 매서드와 속성을 가지고, 키-값 쌍으로 데이터를 지정하는 일반 객체와 유사한 방식으로 구현되어 있다는 것.
📌 다양한 데이터 타입 및 동적 크기 조절 등으로 인해 전통적인 배열에 비해 성능이 떨어질 수 있다.
자바스크립트 배열의 시간 복잡도
1. 접근 : O(1)
2. 삽입/삭제 : O(1), 평균적으로 상수 시간이지만 내부적으로 배열 크기를 조절해야 할 경우는 추가적인 시간 소요될 수 있음
3. 탐색 : O(n)
2. 연결된 리스트 (Linked List)
Linked List는 노드들이 연결된 형태로 데이터를 순차적으로 저장하는 추상 데이터 타입(ADT)이다.
각 노드는 데이터 부분과 다음 노드를 가리키는 주소 부분(링크)으로 구성된다. 이 구조는 동적으로 데이터를 관리하기 위해 사용된다.
// 노드 구조 예시
struct Node {
int data; // 데이터 부분
struct Node* next; // 다음 노드를 가리키는 포인터(링크)
};
장점
1. 필요에 따라 메모리를 할당해 크기를 동적으로 조정할 수 있음
2. 어느 위치에나 새로운 노드를 삽입하거나 기존 노드를 삭제하는 과정이 배열에 비해 효율적 -> 주로 링크만 변경하면 됨
단점
1. 배열처럼 인덱스를 통한 접근이 불가능, 특정 요소에 접근하기 위해서는 순차적으로 탐색해야 함
2. 각 노드가 데이터 외에 다음 노드의 주소(링크)를 저장해야 하므로 추가적인 메모리 공간이 필요
시간복잡도
1. 탐색 : O(n) - 특정 요소를 찾기 위해 처음부터 끝까지 순차적으로 탐색해야 함
2. 삽입 및 삭제 : O(1)
Array와의 차이점
1. 배열은 초기에 크기가 고정되고 메모리 상에서 연속적인 공간에 할당됨. 반면 Linked list는 필요에 따라 각 요소(노드)가 메모리의 임의의 위치에 동적으로 할당됨
2. 배열은 크기 조정이 어렵고 크기 변경을 위해서는 새로운 배열을 생성하고 데이터를 복사해야 함. 하지만 Linked list는 노드의 추가 및 제거를 통해 손쉽게 크기 조절 가능
3. 배열은 인덱스를 통해 O(1)에 임의 접근이 가능하지만 Linked list는 O(n)에 순차 접근해야 함
4. Linked list는 추가적인 메모리(링크 정보)를 사용하지만, 배열은 데이터만큼의 메모리만 사용
사용 사례
데이터를 연속적으로 빠르게 삽입 및 제거가 필요한 경우 (사진 앨범, 음악 플레이어 등)
3. 스택 (Stack)
스택은 Last In First Out (LIFO) 원칙을 따르는 선형적인 자료구조이다.
즉, 가장 나중에 스택에 추가된 요소가 가장 먼저 제거된다는 것이다.
장점
1. 스택의 연산은 구현하기 간단하다.
2. 자료의 추가 및 삭제가 매우 빠르다. 스택의 상단에만 요소를 추가하거나 제거하기 때문
단점
1. 스택은 한쪽 끝에서만 모든 연산이 이루어지기 때문에, 큐나 다른 자료구조에 비해 상대적으로 유연성이 부족하다.
2. 스택의 크기가 고정된 경우, 그 크기를 초과하는 데이터를 저장할 수 없다.
시간복잡도
1. 탐색(비어 있는지, 가득 찼는지, 상단의 요소를 조회) : O(1)
2. 삽입 및 삭제 : O(1) -> 스택 연산이 상단의 요소에만 작용하기 때문
사용 사례
웹 브라우저의 뒤로 가기 기능, 함수의 호출 스택 등에 사용됨
4. 큐 (Queue)
큐(Queue)는 한 쪽 끝에서는 추가(addition)만, 반대편에서는 삭제(deletion)만 이루어지는 리스트 형태의 자료구조이다.
큐는 First In First Out(FIFO) 원칙을 따르는데, 즉 가장 먼저 추가된 요소가 가장 먼저 제거된 것이라는 뜻이다.
이는 실생활의 줄 서기와 유사한 방식이라고 생각하면 된다.
큐 자료구조를 배열로 구현한다면, 기본적으로 사용되는 세 가지 주요 구성 요소는 다음과 같다.
1. Queue : 큐의 요소들을 저장하는 배열의 이름. FIFO 원칙을 준수한다.
2. Front : 큐에서 첫 번째 요소가 저장된 배열의 인덱스. 즉 큐에서 다음에 삭제될 요소의 위치를 나타냄. 큐에서 요소가 제거될 때마다 Front 인덱스는 다음 요소를 가리키도로 갱신됨.
3. Rear : 큐에 마지막으로 추가된 요소가 저장된 배열의 인덱스. 즉 큐의 끝 부분이며, 큐에 요소가 추가될 때마다 Rear 인덱스는 새로운 요소가 추가된 위치로 업데이트됨.
동작 원리
1. Enqueue(요소 추가) : 새로운 요소가 큐에 추가되면, 그 요소는 Rear 인덱스가 가리키는 위치에 저장된다. 요소가 추기된 후 Rear 인덱스는 배열의 다음 위치로 이동한다.
2. Dequeue(요소 제거) : 큐에서 요소를 제거하려면, Front 인덱스가 가리키는 위치의 요소가 제거된다. 요소 제거 후 front 인덱스는 배열의 다음 위치로 이동하여 다음으로 제거될 요소를 가리킨다.
장점
1. 자료의 순서를 유지하면서 요소를 관리. 이는 시간에 따른 데이터 처리에 적합
2. 큐의 연산(삽입, 삭제)이 간단
3. 양 끝에서 접근이 가능
단점
1. 중간 요소의 수정 및 접근이 비효율적임. 즉 큐의 주간에 있는 요소에 접근하려면 앞에 있는 요소를 모두 제거해야 함
2. 배열 기반 구현인 경우, 큐가 가득 찬 경우에 재배치가 필요할 수 있음
시간복잡도
1. 삽입 및 삭제 : O(1) - 하지만 동적 배열을 사용하는 경우에는 추가적인 시간이 소요될 수 있음
2. 탐색 (큐의 맨 앞 요소 확인) : O(1)
사용 사례
프린트 작업 대기열, 프로세스 스케줄링 등에 사용됨
5. Hash Table
해시 테이블은 키(Key)를 값(Value)에 매핑할 수 있는 자료구조이다.
이 구조는 해시 함수(Hash Function)를 사용해 키의 저장 위치를 계산한다.
따라서, 특정 키에 대한 값의 검색, 삽입, 삭제 작업을 매우 빠르게 수행할 수 있다.
[해시 함수]
- 데이터를 효율적으로 관리하기 위해 데이터를 수학적 연산을 통해 고정된 길이의 데이터로 매핑하는 함수
[해시 값]
- 해시 함수가 키를 받아 계산한 후 출력되는 고정된 값
- 해시 테이블 내에서 키-값 쌍을 저장할 위치(=버킷)을 결정하는 데 사용함
- 만약 키 'John' 에 대해 해시 함수를 적용하면, 4라는 해시 값을 얻을 수 있음 -> 이때 4는 'John' 이라는 키와 그에 대응하는 값이 저장될 해시 테이블 내의 위치(=버킷)를 의미
장점
1. 빠르게 데이터에 접근할 수 있다.
2. 해시 테이블은 필요한 만큼의 메모리만 사용하여 데이터를 저장하므로 공간 효율성이 높다.
3. 키를 통해 직접 값에 접근할 수 있어 데이터 관리가 용이하다.
단점
1. 두 개 이상의 키가 동일한 해시 값을 가질 때 해시 충돌이 발생할 수 있다.
2. 해시 테이블은 키의 순서를 유지하지 않아 순서가 중요한 경우에는 적합하지 않다.
3. 해시 테이블이 가득 차면 크기를 조정(리해싱)해야 하는데, 이 과정이 복잡하다.
시간복잡도
1. 탐색 : 평균 O(1)이지만 모든 키가 동일한 해시 값을 가지는 경우 최악에서는 O(n)
2. 삽입 및 삭제 : 평균 O(1), 최악의 경우 O(n)
사용 사례
해시 테이블은 주로 빠른 데이터 검색, 삽입, 삭제가 필요할 때 사용된다.
예를 들어, 사용자 이름으로 사용자 정보를 검색하거나, 데이터가 이미 존재하는지 빠르게 확인할 필요가 있을 때 유용하다.
6. Heap
Heap은 모든 노드가 특정한 순서로 정렬된 완전 이진 트리 구조의 자료구조이다.
힙은 두 가지 주요한 특성이 있는데,
1) 구조적 특성 : 힙이 언제나 완전 이진 트리의 형태를 유지하고 있음
2) 순서 특성 : 모든 노드가 자신의 자식 노드보다 큰 값을 가지는 최대 힙(Max Heap) / 모든 노드가 자신의 자식 노드보다 작은 값을 가지는 최소 힙(Min Heap) 의 두가지 형태가 존재한다.
장점
1. 최대 힙에서는 최대값을, 최소 힙에서는 최소값을 O(1)에 접근할 수 있어 최대값과 최소값에 효율적으로 접근할 수 있다.
2. 중간 값을 효율적으로 찾고, 값을 효율적으로 정렬할 수 있다.
3. 동적 데이터 관리에 효율적이다. 데이터가 추가/제거 되어도 힙은 빠르게 재구성할 수 있다.
단점
1. 순차적 접근이 불리하다.
2. 임의의 노드를 삭제하거나 검색하는데 비효율적이다.
시간복잡도
1. 힙 생성 : O(n)
2. 삽입 : O(log n)
3. 삭제 : 최대값 또는 최소값 삭제는 O(log n), 임의의 값 삭제는 O(n)
4. 최대값 또는 최소값 접근 : O(1)
사용 사례
힙은 최대값 및 최소값을 빠르게 찾아낼 수 있고 배열을 효율적으로 정렬하고자 하는 경우 유용하다.
7. Graph
그래프(Graph)는 노드(Node)와 이들을 연결하는 Edge로 구성된 자료구조이다.
그래프는 방향성이 있는 방향 그래프(Directed Graph)와 방향성이 없는 무방향 그래프(Undirected Graph)로 나뉜다.
장점
1. 복잡한 관계를 표현하는 데 유용하다.
2. 새로운 요소의 추가 및 삭제에 용이하다.
단점
1. 그래프는 구조가 복잡하여 구현하기 어려우며, 그래프를 다루는 알고리즘의 이해가 어려울 수 있다.
2. 노드와 edge의 수가 많은 대규모 그래프는 메모리를 많이 소비한다.
시간 복잡도
그래프의 시간 복잡도는 그래프를 표현하는 방법에 따라 달라진다.
그래프를 표현하는 두 가지 일반적인 방식은 인접 리스트(Adjacency List)와 인접 행렬(Adjacency Matrix) 이다.
각각의 시간 복잡도는 다음과 같다.
1. 인접 리스트
- 탐색 : O(N+E) - 모든 노드(N)와 엣지(E)를 방문할 수 있음
- 추가 : O(1)
- 삭제 : 노드의 경우는 O(N+E), 엣지의 경우는 O(E)
2. 인접 행렬
- 탐색 : O(N^2) - 모든 가능한 노드 쌍을 확인해야 함
- 추가 : 노드 추가의 경우는 O(N^2), 엣지 추가의 경우는 O(1)
- 삭제 : 노드 삭제의 경우는 O(N^2), 엣지 삭제의 경우는 O(1)
사용 사례
소셜 네트워크 (유저 간의 친구 관계 및 추천 시스템), 지도의 경로 찾기 및 거리 계산, 네트워크 라우팅 등에 활용됨
8. Tree
트리(Tree)는 노드(Node)들이 Edge로 연결된 계층적인 자료구조이다.
트리는 하나의 루트 노드를 가지며, 루트 노드에서 시작해 자식 노드로 분기하고, 이런 식으로 계속해서 확장된다.
각 노드는 0개 이상의 자식 노드를 가질 수 있다. (자식이 없는 노드는 Leaf라고 한다.)
노드 간에는 순환 구조가 없다.
장점
1. 트리 구조는 계층적인 관계를 표현하는데 적합하다.
2. 이진 검색 트리(BST)와 같은 트리 구조는 데이터 검색, 삽입, 삭제에 효율적이다.
3. 균형 잡힌 트리 구조는 노드 접근 시간을 최소화한다.
단점
1. 구현하기 복잡할 수 있다.
2. 각 노드는 자식 노드에 대한 참조를 저장해야 하므로 추가적인 메모리 사용이 발생한다.
시간복잡도
1. 탐색 : 평균 O(log n), 최악 O(n) (이진 검색 트리에서 편향된 트리의 경우)
2. 삽입 및 삭제 : 평균 O(log n), 최악 O(n)
사용 사례
파일과 디렉토리의 계층적 구조를 표현할 때, 데이터베이스에서 데이터의 효율적인 검색, 삽입, 삭제를 구현할 때 (이진 검색 트리 등을 사용), UI구조, 라우팅 알고리즘 등에서 유용하게 사용된다.
Reference
https://www.educba.com/arrays-in-data-structure/
https://codeforwin.org/data-structures/data-structure-introduction-to-linked-list
https://www.programiz.com/dsa/stack
https://logicmojo.com/hashing-in-data-structure
https://github.com/WooVictory/Ready-For-Tech-Interview
https://www.geeksforgeeks.org/heap-data-structure/
https://www.simplilearn.com/tutorials/data-structure-tutorial/graphs-in-data-structure
https://www.geeksforgeeks.org/adjacency-list-meaning-definition-in-dsa/
https://www.lavivienpost.com/implement-graph-as-adjacency-list/
https://www.scaler.com/topics/data-structures/tree-data-structure/