자료구조

자료구조란 자료를 효율적으로 관리하기 위한 구조이다. 따라서 목적에 맞게 사용한 좋은 자료구조는 실행시간 단축과 메모리 용량 절감 효과가 있다. 또 알고리즘과 밀접한 관계를 갖는다.

자료구조는 크게 선형 자료구조와 비선형 자료구조로 나눌 수 있다.

선형 자료구조(Linear Data Structures)

선형 자료구조는 데이터를 선의 형태로 순차적으로 저장하는 구조를 가지고 있다. 각 데이터 요소의 바로 전에 오는 요소와 다음에 오는 요소와의 관계가 명확하게 정의되기 때문에 자료들간 앞뒤 관계가 1:1이라고 할 수 있다.

주요 선형 자료구조

• 배열 (Array) : 메모리 상에 연속적으로 저장된 데이터 요소들의 모음. 각 요소는 인덱스를 사용하여 접근 가능.

• 연결 리스트 (Linked List) : 각 요소가 데이터와 다음 요소를 가리키는 포인터로 이루어진 노드로 구성. 메모리는 불연속적으로 할당될 수 있음.

• 스택 (Stack) : 데이터를 후입선출(LIFO, Last-In-First-Out)의 원칙에 따라 저장하는 구조. push(삽입)과 pop(삭제) 연산을 지원.

• 큐 (Queue) : 데이터를 선입선출(FIFO, First-In-First-Out)의 원칙에 따라 저장하는 구조. enqueue(삽입)와 dequeue(삭제) 연산을 지원.

비선형 자료구조(Non-linear Data Structures)

비선형 자료구조는 각 데이터 요소가 한 개 이상의 요소와 직접적인 관계를 맺고 있으며 계층적인 구조를 가지고 있다.

주요 비선형 자료구조

• 트리 (Tree) : 계층적인 구조로, 루트 노드에서 시작하여 각 노드가 여러 자식 노드를 가질 수 있음. 이진 트리, 이진 탐색 트리 등이 트리의 일반적인 형태.

• 그래프 (Graph) : 노드와 간선의 집합으로 이루어진 구조. 방향 그래프와 무방향 그래프로 나뉘며, 순환 및 비순환 그래프가 있음.

• 해시 테이블 (Hash Table) : 키와 값의 쌍으로 데이터를 저장하는 자료구조. 해시 함수를 사용하여 키를 해시 값으로 변환하고, 이를 인덱스로 사용하여 빠르게 데이터에 접근.

• 힙 (Heap) : 특정한 규칙에 따라 정렬된 완전 이진 트리의 형태를 가지는 자료구조. 일반적으로 최댓값 또는 최솟값을 빠르게 찾기 위해 사용된다.

• 트라이 (Trie) : 키(key)를 검색하는 데 사용되는 트리 형태의 자료구조. 각 노드는 문자 또는 키의 일부를 나타낸다.