자료구조와 자료구조의 종류

목차

• 자료구조

• 자료구조 목적/이유

• 자료구조의 고려사항

• 자료구조의 종류

• 선형 자료구조와 비선형 자료구조

 

<자료 구조>

자료 구조 (Data Structure)

• 문제 해결을 위해 데이터를 조직화하고 저장하고 표현하는 방법. 즉, 알고리즘에서 효과적으로 접근,변경,처리 가능하도록 만들어진 특화된 데이터 체제/형태
• 자료 및 그 처리를 함께 고려하는 데이터 형식. 즉, 자료와 그 작동을 함께 고려하면서, 이를 컴퓨터에 효과적으로 표현,저장,처리하는 기술. 특히, 이 둘을 잘 감싸는(캡슐화) 것을 추상자료형 이라고 함  

 

자료구조의 목적/이유

• 효율적으로 데이터를 사용하기 위함. 일반적으로, 좋은 자료구조는 연산의 횟수를 작아지게할 수 있지만, 모든 목적에 적합한 단일한 자료구조는 없으며, 응용에 따라 달라짐
• 자료구조 관련 연산의 다양성 및 효율성 제고. 통상의 사칙연산 이외에도, 읽기,삽입,삭제,비교,교환,검색 등의 용이성,효율성도 고려

 

자료구조의 선택(고려 사항)

• 데이터의 양
• 데이터 사용 횟수 및 방법
• 요구되는 기억장치의 양
• 데이터 수정에 필요한 시간
• 알고리즘 복잡도 등

 

<자료구조의 종류>

자료구조의 종류

단순 구조 - 문자형,문자열형,숫자형,논리형 등 (자료구조로써 구분 포함시키지 않음)

자료 간의 연결 형태/모양에 따른 구분
① 선형 자료구조 (linear, 전후 1:1 연결 형태)

    - 기본 선형 자료구조 : 리스트, 연결 리스트, 배열, 레코드 등 제한

    - 선형 자료구조 : 스택, 큐, 데크(스택과 큐가 혼합된 형태) 등

② 비선형 자료구조 (nonlinear, 전후 n:m 연결 형태) - 트리, 그래프 등

 

자료 간에 연속,연결 구조에 따른 구분
① 배열 기반의 연속 방식 - 문자열, 튜플, 리스트,딕셔너리 등

② 포인터 기반의 연결 방식 - 스택, 큐, 데크, 우선순위 큐와 힙, 연결 리스트, 해시 테이블 등

 

선형 자료구조와 비선형 자료구조
선형 자료구조 (Linear Data Structure)
  ㅇ 한 원소 뒤에 하나의 원소 만이 존재함
     - 자료들이 직선 형태로 나열되어 있는 구조 (원소들간에 순서를 고려함)
     - 전후/인접/선후 원소들 간에 1:1 관계로 나열됨
  ㅇ 선형 자료구조
     - 기본 선형 자료구조 : 리스트, 연결 리스트, 배열, 레코드 등
        . 자료의 삽입 및 삭제가 어느 위치에서도 이루어짐 
     - 제한 선형 자료구조 : 스택, 큐, 데크(스택과 큐가 혼합된 형태) 등
        . 자료의 삽입 및 삭제가 정해진 위치에서만 이루어짐 

비선형 자료구조 (Nonlinear Data Structure)
  ㅇ 한 원소 뒤에 여러개의 원소들이 존재할 수 있음
     - 인접(전후) 원소들 간에 多:多 관계로 배치됨
  ㅇ 특징
     - 계층적 구조(Hierarchical Structure)를 나타내기에 적절

       ex) 가계도상에서 조상-자손 간의 관계, 직장 상사-부하 간의 관계, 컴퓨터 폴더 구조 등
  ㅇ 비선형 자료구조  - 트리, 그래프 등