20241007 - 자료구조

자료구조

어떤 데이터를 보관하는 방식에 대해서 말한다

 

자료구조는 [1][0][2] => 자료를 배치하라고 했을 때
[1][0][2] 배치 => std::vector
[0][1][2] 배치 => std::set

메모리 형태로 2가지로 구분

배열형 노드형 자료구조

 

배열형 자료구조

배열형 자료구조는 데이터를 연속적인 메모리 공간에 저장하는 방식이다. 

인덱스를 통해 접근할 수 있기 때문에 매우 효율적이고, 정해진 크기의 데이터들을 저장하는데 적합하다.

- 크기가 고정되어 있으며, 모든 원소는 연속적인 메모리 공간에 저장된다.

- 인덱스를 통해 빠르게 접근할 수 있다.

- 크기를 미리 정해야 하고, 삽입이나 삭제 시 전체 데이터를 이동해야 할 수 있기 때문에 비효율적일 수 있다.

- 배열이 여기에 속한다.

 

노드형 자료구조

노드형 데이터 구조는 데이터를 노드 단위로 저장하고, 각 노드는 다른 노드를 가리키는 포인터를 가지고 있다.

동적인 크기 변경이 가능하고, 삽입 삭제가 용이하다.

- 각 노드는 데이터와 다음 노드를 가리키는 포인터로 이루어져 있습니다.

- 메모리 공간이 연속적이지 않아도 된다.

- 동적 크기 조정이 가능하고, 삽입 및 삭제가 효율적일 수 있다.

- 직접 접근 속도는 배열에 비해 느리다. (노드를 하나 하나 따라가야하기 때문에)

- 연결리스트, 트리, 그래프가 여기에 속한다.

 

형태에 따라 2가지의 구분

선형 비선형 자료구조 

 

선형 데이터 구조

데이터가 순차적으로 나열된 구조를 말한다.

각 요소는 하나의 다음 요소만을 가리키거나, 배열처럼 인덱스를 통해 순서대로 접근할 수 있는 자료구조를 말한다.

- 데이터가 직선 형태로 배치되어 있어 순차적으로 접근할 수 있다.

- 배열, 연결리스트, 스택, 큐 등의 자료구조가 선형 데이터 구조에 속한다.

 

비선형 데이터 구조

비선형 데이터 구조는 데이터 간의 관계가 복잡한 구조를 말한다.

한 요소가 여러 요소와 연결될 수 있다. 이러한 구조는 계층적이거나 네트워크 형태로 데이터가 배치된다.

- 데이터 간의 관계가 여러방향으로 나뉘거나 계층적으로 구성된다.

- 트리, 그래프 등이 비선형 데이터 구조에 속한다.

- 비선형 구조에서는 한 요소가 여러 다른 요소와 연결될 수 있어 복잡한 관계를 나타낼 수 있습니다.

자료를 저장하는 방식과 관리하는 방식에 따라 3가지 컨테이너로 분류하기도 한다.
이 부분은 생소해서 잘 모르겠다.

시퀀스 컨테이너

- 데이터를 선형으로 저장하며, 특별한 제약이나 규칙이 없는 가장 일반적인 컨테이너

- 삽입된 요소의 순서가 그대로 유지된다.

종류 - vector, deque, list, forward_list

 

연관 컨테이너

- 데이터를 일정 규칙에 따라 조직화 하여 저장하고 관리하는 컨테이너

- 키와 값처럼 관련있는 데이터를 하나의 쌍으로 저장하는 컨테이너

- 키를 통해 요소에 대한 빠른 접근 제공

- 삽입되는 요소의 위치를 지정할 수 는 없다.

- 균형 이진 트리 또는 해쉬 테이블을 사용하여 구현

종류 - set, multiset, map, multimap

 

어댑터 컨테이너

- 간결함과 명료성을 위해 인터페이스를 제한한 시퀀스나 연관 컨테이너의 변형

- 반복자(iterator)를 지원하지 않는다.

- 특정 형태의 동작만을 수행하게 한다.

종류 - stack, queue, priority_queue