자료구조 기본

컴퓨터의 데이터 취급 방법
- 실제 컴퓨터는 0과 1만을 다룰 수 있기 때문에 다룰 수 있는 기본형은 세가지 뿐이다.
- 숫자, 문자(아스키코드값), T/F

사용자 정의 자료형
- 사용자는 숫자, 문자, T/F를 여러 개 묶어서 새로운 자료형을 선언할 수 있으며, 이 것을 사용자 정의 자료형이라고 한다.
- 대표적인 사용자 정의 자료형
배열 : 동일한 기본 자료형을 여러 개 모은 것
구조체 : 기본 자료형을 여러 개 모은 것
클래스 : 구조체에 함수까지 모아서 자료형으로 선언한 것
재정의 자료형 : enum, def 등을 이용하여 이름을 재정의하거나 넣을 수 있는 종류를 제한하는 것

자료구조(Data Structure)
- 컴퓨터가 다루어야 할 자료가 많을 때, 자료를 다루는 방법
- 물리적인 구현 방법은 리스트와 연결 리스트 2가지가 있다.
- 리스트와 연결 리스트, 두 가지 물리적 구조를 기반으로 다양한 사용법을 구현한 자료구조가 있다. 즉, 대부분의 자료구조는 내부적으로 리스트 또는 연결 리스트를 이용하여 구현한 것이다.

리스트와 연결 리스트
- 리스트 : 각 데이터를 연이어 저장하는 기술.
- 연결 리스트 : 각 데이터를 임의의 위치에 저장하고 서로를 연결하는 기술.

자료구조의 분류
- 단순구조(Simple Structure) : T/F, 정수, 실수, 문자 및 문자열과 같이 컴퓨터가 기본 제공하는 자료형 혹은 기본 자료형만을 여러 개 모아 만든 사용자 정의 자료형을 사용하는 경우.
- 선형구조(Linear Structure) : 데이터들이 일렬로 쭉 저장되어 있는 형태. 리스트, 연결 리스트, 스택, 큐, 테크.
- 비선형구조(Non-Linear Structure) : 데이터가 트리 형태로 저장되어 있다고 생각하고 사용하는 자료구조. 트리, 그래프. 물리적으로는 리스트와 연결 리스트로 구현되어있음.
- 파일구조(File Structure) : 다양한 자료구조의 데이터를 파일에 저장하는 방식. 순차 파일(Sequential File), 색인 파일(Index File), 직접 파일(Direct File)의 세 가지 방식이 있다.

 

자료구조의 구현
- 자료구조의 구현 기술은 리스트와 연결 리스트 두 가지이다. 각 구현 기술에 따른 자료구조를 알아보자.

1. 리스트형 자료구조 : 연속적인 저장의 형태를 가짐. 메모리에서 데이터들이 연속적인 공간을 할당받는다.

만약 리스트의 원소들 사이에 순서를 가지면 선형 리스트(Linear List)라고 한다.

- 배열 : 크기가 변하지 않는 자료구조. 중간의 값을 지워도 빈칸으로 유지된다.
- 리스트 : 크기가 변하는 자료구조. 중간의 값을 지우면 뒤의 것이 앞으로 이동한다.

2. 연결 리스트 자료구조 : 저장하는 각 데이터가 다음과 이전의 데이터의 위치 정보(포인터)를 가지고 있는 구조.
- 연결 리스트 : 저장된 각 데이터가 (데이터)+(다음 데이터의 포인터)로 이루어진 것. 한 방향으로만 탐색 가능.
- 더블 연결 리스트 : 저장된 각 데이터가 (이전 데이터의 포인터)+(데이터)+(다음 데이터의 포인터)로 이루어진 것. 양방향 탐색 가능.
- 환형 연결 리스트 : 더블 연결 리스트의 양끝이 연결되어있는 구조.

이런 특성 때문에 연결 리스트 자료구조에서는 한 데이터를 삽입, 삭제해도 전체 데이터의 변동이 없고 앞, 뒤의 연관된 데이터만 변동하면 된다. 그래서 중간에 넣거나 지우는 과정을 빠르게 수행할 수 있다. 하지만 특정 데이터를 검색하는 것은 포인터를 따라 이동해야하므로 성능이 떨어진다.