자료구조의 개념과 종류

1. 개요

이번 챕터에서는 자료구조란 무엇이며 어떤 종류가 있는지 살펴본다. 자료 구조의 종류는 단순히 어떤 것이 있고 해당 자료구조의 특징과 장, 단점 그리고 쓰임에 대해서만 살펴보고 넘어간다. 보다 자세한 내용은 해당 자료구조 챕터에서 다룬다.

---

2. 자료구조의 개념

자료구조의 개념 및 특징을 정리하면 아래와 같다.

• 컴퓨터 과학에서 효율적인 접근 및 수정을 가능체 하는 자료의 조직, 관리, 저장을 의미

• 자료 구조는 데이터 값의 모임, 데이터 간의 관계, 그리고 데이터에 적용할 수 있는 함수나 명령을 의미

• 신중히 선택한 자료구조는 보다 효율적인 알고리즘을 사용할 수 있음

• 효과적으로 설계된 자료구조는 실행시간 혹은 메모리 용량과 같은 자원을 최소한으로 사용하면서 연산을 수행

---

3. 자료 구조의 종류

1. 선형 구조: 자료를 구성하는 데이터를 순차적으로 나열시킨 형태를 의미

   • 배열(Array)

   • 연결리스트(Linked List)

   • 스택

   • 큐

2. 비선형 구조: 하나의 자료안에 여러개의 자료가 존재할 수 있는 것을 의미

   • 그래프

   • 트리

아래에서 각각의 자료 구조의 특징과 장, 단점 그리고 쓰임에 대해 살펴보자.

---

4. 배열(Array)

Array

4-1. 배열의 특징

• 가장 기본적인 데이터 구조

• 생성되는 순간 설정되는 셀에 인덱스가 부여되고 해당 셀의 개수는 고정

• 부여된 인덱스를 통해 원하는 데이터에 접근할 수 있음

---

4-2. 배열의 장점

• 바로 만들어 활용하기 쉬움

• 원하는 데이터를 효율적으로 검색하여 가져올 수 있음

• 배열을 기반으로 하여 더 복잡한 자료 구조를 만들 수 있음

• 정렬이 쉬움

---

4-3. 배열의 단점

• 생성될 때 셀의 개수가 고정되므로 데이터를 저장할 수 있는 메모리의 크기가 고정되어 있음

• 데이터를 추가, 삭제하는 과정이 비효율적

• 데이터를 삭제되고 남은 셀은 빈 공간이 되므로 메모리의 낭비가 심함

---

4-4. 배열의 쓰임

• 배열 목록, 힙, 해시 테이브, 벡터 및 행렬과 같은 기타 데이터 구조를 구축하기 위한 빌딩 블록으로 사용

• 삽입 정렬, 빠른 정렬, 버블 정렬 및 병합 정렬과 같은 다양한 알고리즘에 사용

---

5. 연결 리스트(Linked List)

Linked List

• Node: 각 요소

• key: 노드(요소)에 저장된 데이터

• next: 다음 노드를 가리키는 포인터

• Head: 연결 리스트의 첫 번째 노드(요소)

• Tail: 연결 리스트의 마지막 노드(요소)

---

5-1. 연결 리스트의 특징

• 각 데이터 시퀀스가 순서를 가지고 연결된 순차적 구조

• 데이터를 임의의 기억공간에 기억

• 데이터 항목의 순서에 따라 노드의 포인터를 이용하여 서로 연결

---

5-2. 연결 리스트의 장점

• 새로운 데이터를 추가하고 삭제하는 것이 쉽고 효율적

• 배열처럼 메모리에 연속적으로 위치하지 않고 구조의 재구성이 필요없음

• 메모리를 더 효율적으로 사용할 수 있기 때문에 대용량 데이터 처리에 적합

---

5-3. 연결 리스트의 단점

• 연결이 끊어지면 다음 노드를 찾기가 어렵고 속도가 느림

---

5-4. 연결 리스트의 쓰임

• 배열과 마찬가지로 다른 자료 구조들을 구현하는 데 사용됨(빌딩 블록의 역할)

---

6. 스택(Stack)

Stack

---

6-1. 스택의 특징

• 순서가 보존되는 선형 데이터 구조

• 가장 마지막 요소(가장 최근 요소)부터 처리하는 LIFO(Last In First Out)

---

6-2. 스택의 장점

• 동적인 메모리 크기

• 데이터를 받은 순서대로 정렬

• 빠른 런타임

---

6-3. 스택의 단점

• 한 번에 하나의 데이터만 처리 가능

---

6-4. 스택의 쓰임

• 실행 취소

• 재귀 프로그래밍에서 함수 호출을 구현

---

7. 큐(Queue)

Queue

---

7-1. 큐의 특징

• 가장 먼저 입력된 요소를 처리하는 FIFO(First In First Out)

• 리스트의 한쪽에서는 삽입이 일어나고 다른 쪽에서는 삭제가 일어남

• 데이터의 시작 부분을 프런트(Front)라 하고 끝 부분은 리어(Rear)라고 함

---

7-2. 큐의 장점

• 동적인 메모리 크기와 빠른 런타임

• 데이터를 받는 순서대로 정렬

---

7-3. 큐의 단점

• 한 번에 하나의 데이터만 처리 가능

• 가장 오래된 요소만 가져옴

---

7-4. 큐의 쓰임

• 멀티스레딩에서 스레드를 관리

• 대기열 시스템

---

8. 해시 테이블(Hash table)

Hash table

---

8-1. 해시 테이블의 특징

• 대량의 정보를 저장하고 특정 요소를 효율적으로 검색할 수 있는 복잡한 데이터구조

• 테이블 내에 더 작은 서브 그룹인 키와 값의 쌍을 저장

• 필요할 때만 메모리 크기를 늘리고, 가능한 작은 크기를 유지

• 키는 검색 시 사용되는 문자열

• 값은 키와 쌍을 이룬 데이터

• 검색된 각 키는 미리 정의된 해시함수를 통해 해시값을 받고 버킷을 기리킴

• 해시 숫자는 버킷의 인덱스를 의미

• 버킷에서 검색할 때 입력된 키를 찾고 해당 키와 관련된 값을 반환

---

8-2. 해시 테이블의 장점

• 해소운 요소들의 추가, 삭제가 용이하고 효율적

• 원하는 값의 검색, 가져오기가 빠르고 효율적

• 동적인 메모리 크기

---

8-3. 해시 테이블의 단점

• 충돌이 일어날 수 있음

• 충돌이 자주 일어날 수 있으며 해시 함수의 정비가 필요한 경우가 많음

---

8-4. 해시 테이블의 쓰임

• 데이터베이스의 인덱스 구현

• 사용자 로그인 인증

• "set" 데이터 구조 구현

---

9. 그래프(Graph)

Graph

---

9-1. 그래프의 특징

• 정점(Vertex)과 간선(Edge)으로 이루어진 데이터 구조

• 노드 사이에 엣지가 있는 자료구조

• 구조를 어떻게 설계 그리고 무엇을 하고 싶냐에 따라 시간복자도가 달라짐

• 사이클이 없는 그래프를 특별히 트리라고 함

• 방향 그래프(일방통행)와 무방향 그래프(양방향)가 있음

---

9-2. 그래프의 장점

• 새로운 요소들의 추가, 삭제가 용이하고 효율적

• 구조의 응용이 가능

---

9-3. 그래프의 단점

• 데이터간의 충돌이 발생할 수 있음

---

9-4. 그래프의 쓰임

• 소셜 미디어 네트워크를 나타내는 데 사용(팔로우, 팔로잉)

• 검색 엔진에 의해 웹 페이지 및 링크를 나타내는 데 사용

• GPS에서 위치와 경로를 나타내는 데 사용

---

10. 트리(Tree)

Tree

---

10-1. 트리의 특징

• 트리는 노드로 구성된 계층적인 자료구조

• 최상위 노드(루트, Root)를 만들고 그 아래에 자식을 추가하는 방식으로 트리구조는 다양하게 구현 가능

• 간선(Edge): 노드와 노드를 잇는 선

• 부모(Parent)노드: 상위 노드

• 자식(Child)노드: 하위 노드

• 형제(Siblings)노드: 같은 부모(Parent)노드를 가지며 같은 레벨에 있는 노드

• 단말(Terminal)노드: 자식이 없는 노드

---

10-2. 트리의 종류

• 이진 트리(Binary Tree): 기본적으로 자식노드를 최대 2개 가지는 트리

• 완전 이진 트리(Complete Binary Tree): 왼쪽 자식노드부터 채워지며 마지막 레벨을 제외하고는 모든 자식노드가 채워져있는 트리

• 힙: 부모 자식 노드 간의 대소 관계는 정의되어 있으나 형제간의 대소관계는 정의되어 있지 않은 완전 이진트리 자료구조

  • 최대 힙: 부모노드의 키값이 자식노드의 키값보다 항상 큰 힙

  • 최소 힙: 부모노드의 키값이 자식노드의 키값보다 항상 작은 힙

그 외 많은 트리의 종류가 있지만 해당 트리를 실제로 사용을 하게 될 때 정리를 하도록 한다.

---

11. 자료구조의 시간 복잡도

자료구조의 시간 복잡도

자료구조	가져오기(값)	추가하기	삭제하기
배열(Array)	O(n)	O(n)	O(n)
연결리스트(Linked list)	O(n)	O(1)	O(1)
스택(Stack)	O(n)	O(1)	O(1)
큐(Queue)	O(n)	O(1)	O(1)
해시테이블(Hash Table)	O(1)	O(1)	O(1)

자료구조	가져오기(값)	노드/엣지 추가하기	노드 삭제하기	엣지 삭제하기
그래프(Graph)	O(N+E)	O(1)	O(N+E)	O(E)

---

12. Conclusion

여러가지의 자료구조에 대해 정리를 하였지만 아직 정확히 자료구조에 대한 이해는 하지 못했다. 앞으로 코딩 테스트를 준비하면서 자료구조, 알고리즘을 공부하여 오늘 정리한 자료구조에 대해 많이 사용해보도록 하자. 지금까지 배열만 사용했던지라 많은 자료구조가 있다는 것이 재밌고 많은 자료구조를 적용할 수 있다는 것이 흥미롭게 느껴진다.

---

참고

자료 구조(Data Structure) 개념 및 종류 정리 [DS] 자료구조 개념 및 종류 [자료구조] 자료구조란?(선형구조, 비선형구조) 7가지 자료구조(Data Structure)의 종류와 각각의 장단점 [Data Structure] 꼭 알아야 할 7가지 자료구조 [자료구조] 트리의 종류 및 특징

---

📅 2022-08-27 📅 2022-08-28