자료구조 종류 총 정리

자료구조 (Data Structure)

데이터 값의 모임으로 각 원소들이 논리적으로 정의된 규칙에 의해 나열되며 자료에 대한 처리를 효율적으로 수행할 수 있도록 구분하여 표현한 것

 

- 자료구조가 필요한 이유

책꽂이에 책을 꽂는다고 했을때 책을 무작위로 꽂으면 읽고 싶은 책을 찾기가 어렵다

이때 책을 분야별로 층으로 구분하면 책을 찾기가 훨씬 수월해진다

그러나 책꽂이의 불필요하게 남는 부분이 발생하기 때문에 공간의 비효율이 발생하게 된다

이를 해결하기 위해서 층이 아닌 가림막을 통해 구분하면 공간의 효율성도 지키면서 책을 찾기도 편해진다

즉, 자료구조는 데이터가 사용하는 리소스(메모리)의 효율성을 높이면서 데이터를 편리하게 사용하기 위해 필요한 것이다

 

- 자료구조의 성능

메모리 공간의 효율

실행 시간의 효율

 

 

 

 

 

자료구조와 알고리즘의 관계

보통 자료구조가 선택이 되면 그에 적용할 알고리즘이 거의 명확해지기 때문에 자료구조를 사용하면 효율적인 알고리즘을 사용할 수 있게되고, 이는 두 개념이 매우 밀접한 관계를 가진다는 것을 의미한다

 

 

 

 

 

자료구조의 종류

대부분의 자료구조는 리스트 또는 연결 리스트를 이용하여 구현

 

- List

각 데이터를 연이어 저장

 

- Linked List

각 데이터를 임의의 위치에 저장하고 서로를 연결

 

 

 

 

자료구조의 분류

- 단순구조 (Simple Structure)

컴퓨터가 기본적으로 제공하는 자료형

> 정수 / 실수 / 문자 / 문자열 / Boolean

 

- 선형구조 (Linear Structure)

원소들을 하나씩 순차적으로 나열시킨 형태

앞,뒤 원소 간 관계가 1:1 관계

> 순차 리스트 / 연결 리스트 / 스택 / 큐 / 덱

 

- 비선형 구조 (Non-Linear Structure)

하나의 자료 뒤에 여러 개의 자료가 존재할 수 있는 형태

앞, 뒤 원소 간 관계가 1:n 또는 n:n 관계

> 트리 / 그래프

 

- 파일 구조

보조 기억장치에 파일을 구성하는 레코드들을 편성하는 방식

> 순차 파일 / 직접 파일 / 색인 순차 파일

 

 

 

 

 

단순구조

- 정수

자연수와 0, 자연수에 - 기호를 붙인 수

> 자연수 (1부터 시작하여 1씩 커지는 수)

 

- 실수

유리수와 무리수

> 유리수 (정수의 비로 나타낼 수 있는 수. 정수와 분수가 있으며, 소수로 나타내면 유한 소수나 순환 소수가 된다)

> 무리수 (간단한 분수로 고칠 수 없는 수. 소수점 아래의 수가 반복되지 않고 무한히 계속되는 소수)

 

- 문자

단일 문자

 

- 문자열

둘 이상의 결합 문자

 

- Boolean

true 와 false 두 가지의 값만 가지는 값

 

 

 

 

 

선형 구조

- 순차리스트 / 배열

같은 유형의 데이터를 순차적으로 저장

각 원소에는 인덱스를 통해 접근할 수 있으며, 모든 원소는 메모리 상에서 연속적인 위치에 저장된다

배열의 크기는 생성 시 결정되며 이후에 변경할 수 없다

 

- 순차리스트 / 레코드

데이터베이스 테이블의 행을 구성하는 요소로 특정 항목에 대한 모든 필드의 값을 포함

배열과 달리 각 원소의 크기와 데이터 형이 다르다

 

- 연결리스트 / 단순 연결리스트

각 노드들은 이전 노드의 링크 필드를 통해 연결되어지며, 리스트의 접근은 가장 처음 노드를 가리키는 포인터를 통해 접근하는 방식

 

- 연결리스트 / 이중 연결리스트

하나의 노드의 선행 노드와 후속 노드에 대한 두개의 링크를 가지는 연결리스트

양방향으로 검색, 순회가 가능

 

- 연결리스트 / 원형 연결리스트

마지막 노드가 첫 번째 노드를 가리키게하여 리스트의 구조를 원형으로 만든 연결리스트

 

- 스택

한 쪽 끝에서만 자료를 넣고 빼는 작업이 이루어지는 자료구조

LIFO (Last In First Out) 방식으로 동작하며, 가장 최근에 스택에 삽입된 자료의 위치를 top이라고 함

스택에 데이터를 저장하는 것을 push, 데이터를 빼내는 것을 pop이라고 한다

 

- 큐

양쪽 끝에서 데이터의 삽입과 삭제가 이루어지는 자료구조

FIFO (First In First Out) 방식으로 동작하며, 데이터가 삽입되는 곳을 rear, 제거되는 곳을 front 라고 한다

 

- 덱

양쪽 front와 rear에서 삽입 및 삭제가 모두 가능한 큐

Double Ended Queue 의 줄임말

연속적인 메모리를 기반으로 하는 시퀀스 컨테이너이고 선언 이후 크기를 줄이거나 늘릴 수 있는 가변적 크기를 갖는다

또한 중간에 데이터가 삽입될 때 다른 요소들을 앞, 뒤로 밀 수 있다

 

 

 

 

 

비선형 구조

- 트리 / 일반트리

노드(데이터)들을 간선으로 연결한 계층형 자료구조

값을 가진 노드(Node)와 노드를 연결해주는 간선(Edge)로 이루어져 있다

트리에는 사이클이 존재할 수 없다 (있다면 그것은 그래프이다)

루트에서 한 노드로 가는 경로는 유일한 경로 뿐이라는 특징을 가진다

 

- 트리 / 이진트리

각각의 노드가 최대 두 개의 자식 노드를 가지는 트리

자식 노드를 각각 왼쪽 자식 노드와 오른쪽 자식 노드라고 한다

서브트리는 공백이 될 수 있다

구조에 따라 편향 이진트리 / 포화 이진트리 / 완전 이진트리로 나뉘게 된다

 

- 그래프

정점을 나타내는 노드와 간선으로 이루어져 있는 자료구조

정점은 데이터를 나타내고, 간선은 정점들 간의 관계를 표현

방향성 유무에 따라 방향 그래프와 무방향 그래프로 나뉜다

 

 

 

 

 

파일구조

- 순차 파일

레코드를 논리적인 처리 순서에 따라 연속된 물리적 저장공간에 기록하는 방식

 

- 직접 파일

레코드 내의 키 필드를 해시 함수에 의해 물리적 저장 장치의 주소로 변환하여 레코드를 기록하는 방식

> 해시함수 (임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수)

 

- 색인 순차 파일

순차 처리와 랜덤 처리가 모두 가능하도록 레코드들을 키 값순으로 정렬시켜 기록하고, 레코드의 키 항목만을 모은 색인을 구성하여 편성하는 방식

 

 

 

 

 

 

 

 

Reference

 

자료 구조(Data Structure) 개념 및 종류 정리

 

[Data structure] 자료구조 종류와 분류

[Data Structure] 선형(Linear) & 비선형(NonLinear) 자료구조

[자료구조] 파일의 구조(색인 파일, 직접 파일, 색인 순차 파일)

[2] [알고리즘 - 자료구조] 단순구조란? 정수, 실수, 문자, 문자열

1. 자료구조의 이해

[자료구조] 스택 Stack, 큐 Queue, 덱 Deque

비선형 구조 - (일반)트리, 이진 트리

[Java/자료구조] 비선형구조 이해하기 -3 : 그래프 (방향, 무방향 그래프)