자료구조 정리
작성중 초안: 2019-05-12 1차 수정: 2019-06-27 개요 자료(data)는 정수, 실수, 문자, 등으로 구분할 수 있는 것들이다. 이 자료들을 효율적으로 저장하거나, 저장된 자료들을 활용하기 위해 자료구조라는 것이 등장하였다. 자료구조란 메모리에 자료를 저장하고, 메모리로부터 불러오는 방식을 의미한다. 보통 자료구조에 저장되는 자료를 원소(element)라고 부른다. 자료 구조의 기본 형태 대표적으로 배열(Array)과 연결 리스트(Linked List)가 있다. 배열 <그림 1. 배열의 논리적 구조> <그림 2. 메모리 공간에 배치된 배열> 배열의 특징은 다음과 같다. 동일한 타입의 자료를 저장. 메모리 상에 자료가 연속적으로 저장이 되어 있음. Index라고 불리는 키(key)값으로 배열에 저장된 자료, 즉 원소(element)에 임의 접근 이 가능함. 일반적으로 프로그램 실행 중에 크기를 변경할 수 없음. 즉, 정적 인 특성을 지님. 연결리스트에 구조가 간단하고 구현이 쉽다. 연결 리스트 <그림 3. 연결 리스트의 논리적 구조> <그림 4. 메모리 공간에 배치된 연결리스트> 연결리스트의 특징은 다음과 같다. 동일한 타입의 자료를 저장 메모리 상에 자료가 연속적으로 저장되어 있지 않으며, 하나의 원소는 다음 원소의 주소를 가지고 있음. 원소(element)에 접근하기 위해서 모든 원소를 순회해야 하는 순차 접근 이 필요함. 프로그램 실행 중에 크기를 변경할 수 있음. 즉, 동적 인 특성을 지님. 배열에 비해 구조가 복잡하고 구현하기 어렵다. 추상 자료형 한편 자료구조에서 수행되는 연산과 동작만 정의한 것을 추상 자료형 (Abstract Data Type; ADT)라고 부르며, 추상 자료형은 배열 또는 연결리스트를 기반으로 구현된다. 선형 자료 구조 선형