자료구조(Data Structure)의 정의와 중요성
자료구조(Data Structure)란 컴퓨터 과학에서 데이터를 조직적으로 관리하여 구조적으로 표현하는 방식과 이를 구현하는데 필요한 기능을 가능하게 하는 기술이다.
자료구조는 데이터 값의 집합과 각 데이터의 관계, 데이터에 적용시킬 수 있는 함수나 명령이 포함되어 있는 것이다.
잘 짜인 자료구조는 메모리 용량을 최소한으로 사용하게 할 수 있고 실행시간을 단축시킴으로써 보다 효율적인 알고리즘을 실행할 수 있는 데에 도움을 준다.
자료구조를 통해 대규모의 데이터를 쉽게 관리하고 활용하는 데 있어 어려움이 줄어든다.
또한 데이터베이스에서 원하는 데이터를 찾기도 시워진다.
개발자는 사용자의 요구사항에 알맞는, 개발하고자 하는 프로그램에 필요한 맞춤 알고리즘을 설계할 수 있다. 또한 동시에 사용자들이 요구하는 여러 요청사항을 한 번에 처리하여 데이터 처리속도를 향상하고 처리과정도 단순화할 수 있다.
- 대규모 데이터들을 관리 및 활용에 용이
- 데이터베이스에서 원하는 데이터를 찾을 수 있게 한다.
- 사용자가 원하는 또는 프로그램이 필요한 맞춤 알고리즘을 설계 할 수 있다.
- 사용자들의 여러 요청을 한번에 처리 할 수 있다.
- 데이터 처리 과정을 단순화하면서 처리 속도를 향상 할 수 있다.
기본 자료 구조의 유형
1) 단순 구조 : 프로그래밍에서 사용되는 기본 데이터 타입
2) 선형 구조 : 자료의 사이의 관계가 1 : 1
3) 비 선형 구조 : 자료사이의 관계가 1 : n 또는 n : m
4) 파일 구조 : 서로 관련된 필드들로 구성된 레코드의 집합인 파일에 대한 자료 구조
7가지 자료구조
첫째로, 배열(Array)은 가장 기본적인 데이터 구조이다.
배열은 생성되는 순간 설정되는 셀에 인덱스가 부여되고 해당 셀의 개수는 고정된다.
이때 부여된 인덱스를 통해 원하는 데이터에 접근할 수 있다.
배열은 바로 만들어서 활용하기가 쉽고 원하는 데이터를 효율적으로 검색하여 가져오는게 가능하다.
배열을 기반으로 하여 더 복잡한 자료구조를 만들 수 있으며 정렬이 용이하다는 장점이 있다.
그러나 생성될 때 셀의 개수가 고정되므로 데이터를 저장할 수 있는 메모리의 크기가 고정되어 있고 데이터를 추가, 삭제하는 과정이 비효율적이다. 데이터가 삭제되고 나면 남는 셀은 빈 공간이 되므로 메모리의 낭비가 심하다.
장점
- 바로 만들어서 활용하기 쉽다
- 더 복잡한 자료 구조의 기초가 될 수 있다.
- 원하는 데이터를 효율적으로 탐색/가져올 수 있다.
- 정렬에 용이하다.
단점
- 데이터를 저장 할 수 있는 메모리 크기가 고정되어 있다.
- 데이터 추가 / 삭제 방법이 비효율적이다.
- 구조 재구성 시 정렬하는 방식이 비효율적이다.
두번째로 연결 리스트(Linked List)는 데이터를 임의의 기억공간에 기억시키되, 데이터 항목의 순서에 따라 노드의 포인터를 이용하여 서로 연결시킨 자료구조이다.
새로운 데이터를 추가하고 삭제하는 것이 용이하고 효율적이다. 배열처럼 메모리에 연속적으로 위치하지 않고 구조의 재구성이 필요없다. 메모리를 더 효율적으로 사용할 수 있기 때문에 대용량의 데이터의 처리에 적합하다. 하지만 연결이 끊어지면 다음 노드를 찾기가 어렵고 속도가 느리다는 단점이 있다.
장점
- 새로운 요소들의 추가 및 삭제가 용이하고 효율적이다.
- 배열처럼 메모리에 연속적으로 위치하지 않는다.
- 배열처럼 구조의 재구성이 필요없다.
- 동적인 메모리 크기
- 메모리를 더 효율적으로 쓸 수 있기 때문에 대용량 데이터 처리 적합
단점
- 배열보다 메모리를 더 사용한다.
- 처음부터 끝까지 순회하기 때문에 원하는 값을 비효율적으로 검색/가져온다.
- 노드를 반대 방향으로 검색할 때 비효율적이다. (이중 연결 리스트의 경우)
사용
- 메모리 크기가 정해져 있지 않을 때
- 데이터를 연속적으로 빠르게 삽입/제거가 필요할 때
- 이미지 뷰어, 갤러리
- 음악 플레이어
세번째로 스택(Stack)은 순서가 유지되는 선형 데이터 구조이다.
리스트의 한쪽에서만 데이터의 삽입과 삭제가 일어나므로, 가장 마지막 요소부터 가장 처음 요소를 처리하는 LIFO(Last In First Out) 메커니즘을 갖고 있다. 기억공간이 부족한 경우 데이터를 삽입하는 경우 오버플로(Overflow)가 발생하고 삭제할 데이터가 없을 때 데이터를 삭제하고자 하면 언더 플로(Underflow)가 발생한다. 데이터를 받는 순서대로 정렬되고 메모리의 크기가 동적이지만 한 번에 하나의 데이터만 처리할 수 있는 불편함이 있다.
장점
- 동적인 메모리 크기
- 데이터를 받는 순서대로 정렬된다
- 빠른 런타임(runtime)
단점
- 가장 최신 요소만 가져온다.
- 한번에 하나의 데이터만 처리 가능하다.
사용
- 가장 마지막으로 입력된 것을 순차적으로 바로 처리하고 싶을 때
- 브라우저의 뒤로가기
- 실행 취소
- 재귀
네번째로 큐(Queue)는 스택과 비슷하지만 먼저 입력된 요소를 먼저 처리하는 FIFO(First In First Out) 메커니즘을 가진다.
리스트의 한쪽에서는 삽입이 일어나고 다른 쪽에서는 삭제가 일어난다. 데이터의 시작 부분을 프런트(Front)라 하고 끝 부분을 리어(Rear)라고 한다. 동적인 메모리 크기와 빠른 런타임을 자랑하지만 가장 오래된 요소만을 가져오고 한 번에 하나의 데이터만 처리하는 단점이 있다.
장점
- 동적인 메모리 크기
- 데이터를 받는 순서대로 정렬된다.
- 빠른 런타임 (runtime)
단점
- 가장 오래된 요소만 가져온다
- 한번에 하나의 데이터만 처리 가능하다.
사용
- 반복적이고 자주 받는 데이터를 비동기적으로 처리 할 때 효율적
- 음성 데이터처럼 순서에 민감한 데이터를 처리 할 때
- 프린트 대기열처럼 가장 먼저 입력 받은 데이터를 먼저 처리해야 할 때
- 캐시(Cache) 구현
다섯번째로 그래프는 정점(Vertex)과 간선(Edge)으로 이루어진 데이터 구조이며 사이클이 없는 그래프를 특별히 트리라고 한다. 방향 그래프와 무방향 그래프가 있다. 새로운 요소들의 추가나 삭제가 용이하고 구조를 응용하기에 적합하다. 하지만 데이터 간에 충돌이 일어날 수 있다는 단점도 있다.
장점
- 새로운 요소들의 추가/삭제가 용이하고 효율적이다.
- 구조의 응용이 가능하다
단점
- 충돌이 일어날 수 있다. (입력된 키의 해시값이 이미 데이터가 저장된 버킷을 가리킬 수 있다.)
사용
- 데이터베이스 : 주소 찾기, 이름 찾기, 번호 찾기
- 사용자 로그인 인증
여섯번째로 해시 테이블 (Hash tables / Hash map)은 대량의 정보를 저장하고 특정 요소를 효율적으로 검색할 수 있는 복잡한 데이터 구조다.
이 데이터 구조는 테이블 내에 더 작은 서브그룹인 버킷(bucket)에 키/값(key/value) 쌍(pair)을 저장한다. 해시 테이블은 키를 저장할 때에 메모리 공간을 덜 사용할 수 있도록, 키를 "해시 함수" (Hash function)라는 함수를 통해 해시(hash)라는 특정 숫자값으로 변환한다. 해시 테이블은 필요할 때에만 메모리 크기를 늘리고, 가능한 작은 크기를 유지한다.
키(key)는 검색 시 사용되는 문자열이고 값(value)은 해당 키와 쌍을 이룬 데이터다. 검색된 각 키는 미리 정의된 해시함수(hash function)을 통해 해시(hash) 값을 받고 버킷(bucket)을 가리킨다. 즉, 해시 숫자는 버킷의 index라는 뜻이다. 그리고 버킷에서 검색할 때 입력된 키를 찾고 해당 키와 관련된 값을 반환한다.
장점
- 새로운 요소들의 추가/삭제가 용이하고 효율적이다.
- 원하는 값의 검색/가져오기가 빠르고 효율적이다.
- 동적인 메모리 크기(그러나 직접 크기를 늘리거나 줄여야 한다)
단점
- 충돌이 일어날 수 있다. (입력된 키의 해시값이 이미 데이터가 저장된 버킷을 가리킬 수 있다.)
- 충돌이 자주 일어날 수 있으며 해시함수의 정비가 필요한 경우가 많다.
사용
- 데이터베이스 : 주소 찾기, 이름 찾기, 번호 찾기
- 사용자 로그인 인증
마지막으로 트리(Tree)는 노드(Node)로 구성된 계층적인 자료구조이다.
최상위 노드(루트, Root)를 만들고 그 아래에 자식을 추가하는 방식으로 트리구조는 다양하게 구현할 수 있다. 노드와 노드를 잇는 선을 간선(Edge)이라 한다. 같은 부모(Parent) 노드를 가지며 같은 레벨에 있는 노드를 형제(Siblings) 노드라 하고 자식이 없는 노드를 단말(Terminal) 노드라고 한다.
'컴퓨터개론' 카테고리의 다른 글
| [컴퓨터개론] 알고리즘 (0) | 2022.06.08 |
|---|---|
| [컴퓨터개론] CTI(Computer Telephony Integration) (0) | 2022.06.07 |
| [컴퓨터개론] 계층 파일 시스템 (0) | 2022.06.07 |
| [컴퓨터개론] OS 운영체제 (0) | 2022.06.03 |
| [컴퓨터개론] 하드웨어 구성 (0) | 2022.06.03 |
댓글