Data Structure-데이터 구조

데이터구조란?

데이터 구조는 데이터를 구성, 처리, 검색 및 저장하기 위한 특수형식이다.

여러가지 기본 및 고급 유형의 데이터 구조가 있고, 모두 특정 목적에 맞게 데이터를 정리하도록 설계 되었다.

 

데이터 구조 및 알고리즘(Data Structure and Algorithm,DSA)란 컴퓨터 프로그래밍에서 데이터 구조가 다양한 알고리즘과 함께 사용할 목적으로 데이터를 저장하도록 선택되거나 설계될 수 있다.

 

데이터 구조가 중요한 이유

정수나 부동 소수점(** floating point : 하나의 수를 고정 소수점 부분을 나타내는 부분(가수)과 고정 소수점 위치를 나타내는 부분(지수)으로 나누어 표현하는 표기법) 값과 같이 대부분의 컴퓨터 프로그래밍 언어에서 사용할 수 있는 일반적인 기본 데이터 유형은 일반적으로 데이터 처리 및 사용에 대한 논리적 의도를 알아내기에 충분치 않다. 그러나, 수집, 조작 및 생성하는 애플리케이션은 처리를 단순화하기 위해 데이터를 어떻게 구성해야하는지 이해 해야만 한다. 그 때, 데이터 구조는 논리적인 방식으로 데이터 요소를 통합하고, 데이터의 효과적인 사용, 지속성 및 공유를 용이하게 한다.

데이터 구조 사용 예시

일반적으로, 추상데이터 유형의 물리적 형태를 구현하는 데에 사용된다.

• 데이터 저장 : 데이터 구조는 효율적인 데이터 지속성을 위해 사용
• 리소스 및 서비스 관리 : 핵심 운영 체제 리소스 및 서비스는 데이터 구조를 사용하여 활성화한다.
• 데이터 교환 : 데이터 구조는 TCP/IP 패킷과 같은 애플리케이션 간에 공유되는 정보의 구성을 정의한다.
• 정렬 및 정렬 : 이진검색트리와 같은 데이터 구조는 태그로 사용되는 문자열과 같은 객체를 정렬하는 효율적인 방법을 제공.
• 인덱싱 : B-트리와 같은 훨씬 더 정교한 데이터 구조는 DB에 저장된 것과 같은 객체를 인덱싱하는데 사용된다.
• 검색 : 이진검색트리, B-트리 또는 해시테이블을 사용하여 만든 인덱스는 특정 검색 항목을 찾는 능력을 가속화한다.
• 확장성 :빅데이터 애플리케이션은 분산된 스토리지 위치에 데이터 스토리지를 할당하고 관리하기 위해 데이터 구조를 사용하여 확장성과 성능을 보장한다.

데이터 구조의 특성

• 선형 또는 비선형 : 데이터 항목이 배열과 같이 순차적인 순서로 배열되어 있는지, 아니면 graph와 같이 순서 없는 순서로 배열되어 있는지를 설명한다.
• 동종 또는 이종 : 특정 저장소의 모든 데이터 항목이 동일한 유형인지 여부를 설명한다.
• 정적 및 동적 : 데이터 구조가 컴파일 되는 방식. 정적 데이터 구조는 컴파일 시 고정된 크기, 구조 및 메모리 위치를 갖는다.      동적 데이터 구조는 사용에 따라 축소되거나 확장될 수 있는 크기, 구조 및 메모리 위치를 갖습니다.

데이터 유형

• 'boolean(bool)'은 참 또는 거짓인 논리 값을 저장한다.
• 'integer(int)'는 수학적 정수 또는 계산 숫자에 대한 범위를 지정한다.
• 'floating-point number'는 실수의 공식적 표현을 저장
• 'fixed-point number'는 일부 프로그래밍 언어에서 사용되며 실수 값을 갖지만 소수점 왼쪽과 오른쪽의 숫자로 관리됨.
• 'character(char)'는 정수값에서 기호로 정의된 mapping을 사용한다.
• 'pointer'는 다른 값을 가리키는 참조값이다.
• 'String'은 중지코드(일반적으로 "0"값)가 뒤에 오는 문자 배열이거나 정수 값이 길이 필드를 사용하여 관리됨.

데이터 구조의 종류

• 배열 : 인접한 메모리 위치에 항목 모음을 저장한다. 동일한 항목은 함께 저장됨.
• 스택 : 작업이 적용되는 선형 순서로 항목 컬렉션을 저장한다. 이 순서는 LIFO 또는 FIFO 이다.
• 큐 : 스택과 같은 항목 컬렉션을 저장한다. 작업순서는 오로지 FIFO만 가능하다.
• 연결리스트 : 선형 순서로 항목 모음을 저장한다. 연결리스트 각 요소 또는 노드에는 데이터 항목과 리스트의 다음 항목에 대한 참조 또는 링크가 포함된다.
• 트리 : 트리는 추상적이고 계층적인 방식으로 항목 컬렉션을 저장한다. 각 노드는 키 값과 연관되어 있으며, 부모 노드는 자식 노드 또는 하위 노드에 연결된다. 트리의 모든 노드의 조상인 루트노드가 하나 있다. 루트 노드에서 이러한 트리 구조를 따라 아래로 이동하여 모든 후속 노드에 액세스 하는 것을 트래버설이라고 하며 다양한 순소러 수행할 수 있으며, 그 중 일부는 트리 DSA의 성능에 영향을 미칠 수 있다.
• 힙 : 각 부모 노드의 연관된 키 값이 모든 자식 노드의 키 값보다 크거나 같은 트리 기반 구조이다.
• 그래프 : 비선형 방식으로 항목 모음을 저장한다. 정점이라고도 하는 유한한 노드 집합과 이를 연결하는 선, 즉 Edge로 구성된다. 이는 컴퓨터 네트워크와 같은 실제 시스템을 표현하는데 유용하다.
• 트라이 : 키워드 트리라고도 불린다. 문자열을 시각적 그래프로 구성할 수 있는 데이터 항목으로 저장하는 데이터 구조다.
• 해시테이블 : 해시 맵(hash map)이라고도 부른다. 키에서 값으로 ploting하는 연관 배여에 항목 컬렉션을 저장한다. 해시 테이블은 해시 함수를 사용하여 index를 원하는 데이터 항목이 포함된 bucket배열로 변환한다. hashing은 충돌로 고유한 복잡성을 제공한다. 두 키가 같은 값을 생성하는 반면, 새 키는 테이블의 이미 점유된 위치에 mapping된다. chaning은 같은 위치에 해시된 각 요소를 저장하는 local연결 목록을 생성하여 이를 해결한다.

 

References

TechTarget

TTA정보통신용어사전