시작하며.
선형 / 비선형 자료구조 공부하면서 이해 안되는 부분도 많고
머리속에서 두둥실 떠다니는 개념들을 자리잡기 위해
자료구조란 무엇이고 어떻게 분류되는지 어떤 것들이 있는지
간단하게라도 정리하고 넘어가려 한다.
비선형 자료구조는 아직 모르는게 많아서 제대로 정리가 안된거 같다.
자료구조란.
- 프로그램에서 사용할 많은 데이터를 메모리 상에서 관리하는 여러 구현방법들
- 효율적인 자료구조가 성능 좋은 알고리즘의 기반이 됨.
- 자료의 효율적인 관리는 프로그램의 수행속도와 밀접한 관련이 있음
- 여러 자료구조 중에서 구현하려는 프로그램에 맞는
최적의 자료구조를 활용해야 해 자료구조에 대한 이해가 중요
자료구조 형태에 따른 분류.
- 선형 자료구조
데이터 요소가 순차적 또는 선형으로 배열되고 일대일 관계에 있으며
각 요소가 이전 및 다음 인접 요소에 연결되는 자료구조
- 정적 자료구조 : 프로그램 실행 중에 크기가 고정되어 있는 자료구조
배열은 정적 자료구조의 대표적인 예로 선언시 배열의 크기가 정해지고 이후에 변경 불가
미리 할당된 메모리 공간에 데이터를 저장하기 때문에 데이터 추가, 삭제, 크기 변경 등이 제한적
- 동적 자료구조 : 프로그램 실행 중 크기가 동적으로 조정될 수 있는 자료구조
필요에 따라 메모리에서 유연하게 공간을 할당하고 해제헤 데이터를 저장할 수 있어
데이터 추가, 삭제, 크기 변경 등이 가능함
대표적인 예로 ArrayList, LinkedList, Queue, Stack 등이 있음 - 비선형 자료구조
데이터 요소가 순차적 또는 선형으로 배치되지 않은 자료구조
계층 구조를 가지며 요소들 간에 관계를 표현하기 위해 사용됨
대표적인 예로 Tree, Graph 등이 있음
선형 자료구조
- 배열(Array)
배열은 인덱스를 사용하여 배열의 각 요소를 쉽게 식별하는 인덱스 기반 데이터 구조 사용
동일한 데이터 유형의 여러 값을 저장하려는 경우 효율적으로 활용할 수 있음
스택, 큐, 힙, 해시테이블 등 다른 데이터 구조를 구현하는데에도 사용할 수 있음
각 요소의 인덱스 접근이 용이함 - 연결 리스트 (LinkedList)
각 요소가 인접한 메모리 위치에 저장되지 않는 선형 자료구조로 포인터로 연결됨
자료가 추가될 때마다 메모리를 할당 받고, 자료는 링크로 연결됨.
자료의 물리적 위치와 논리적 위치가 다를 수 있음
스택, 큐, 그래프 등을 구현하는데 사용
첫번째 노드는 Head, 마지막 노드의 다음 포인터는 항상 NULL
- 스택(Stack)
스택은 작업이 수행되는 특정 순서를 따르는 선형자료구조
순서는 후입선출(LIFO : Last In First Out)로 데이터 입력 및 검색은 한쪽 끝에서만 가능
자바에서 제공하는 클래스에서 데이터 입력은 push(), 데이터 삭제는 pop(), 최상단 값 반환은 peek() 등이 있다.
- 큐(Queue)
큐는 작업이 수행되는 특정 순서를 따르는 선형자료구조로
선입선출(FIFO : First In First Out) 자료구조
큐의 마지막 요소를 제거하려면 큐 안의 새 요소 앞 모든 요소를 제거해야 함
Enqueue, Dequeue, Peak - 데크(Deque)
양쪽 끝에서 삽입과 삭제가 모두 가능한 자료구조
Deque : Doubly-ended Queue
Stack과 Queue를 합친 상태
- 해시 테이블(Hash Table)
해싱은 해시 함수를 사용해 키와 값을 해시테이블에 매핑하는 기술 또는 프로세스, 자료구조
요소에 대한 빠른 접근이 가능
비선형 자료구조
- 트리(Tree)
트리는 요소가 트리와 같은 구조로 배열된 비선형 및 계층적 자료구조
트리에서 최상위 노드를 root노드라고 하며 부모와 자식 관계로 이루어짐
각 노드에는 일부 데이터가 포함되어 있음
트리에서 루트의 높이는 루트 노드에서 리프 노드까지의 가장 긴 경로로 정의
자바에서는 이진 트리, 이진 검색 트리, AVL트리, B-트리 등
다양한 종류의 트리를 구현하는 클래스와 인터페이스를 제공
- 그래프(Graph)
정점(또는 노드)과 가장자리로 구성된 비선형 자료구조
노드 쌍으로 연결하는 유한한 정점 세트와 모서리 세트로 구성
그래프는 가장 어렵고 복잡한 프로그래밍 문제를 해결하는데 사용
노드와 간선으로 이루어진 자료구조로,
네트워크, 도로망, 소셜 네트워크 등 다양한 현실 세계의 관계를 모델링하는 데 사용
- 힙(Heap)
힙은 트리가 완전한 이진 트리인 특별한 트리 기반 데이터 구조
Priority queue를 구현 (우선 큐)
Max heap : 부모 노드는 자식 노드보다 항상 크거나 같은 값을 갖는 경우
Min heap : 부모 노드는 자식 노드보다 항상 작거나 같은 값을 갖는 경우
힙 자료구조는 보통 배열을 사용하며 0번째 인덱스는 계산을 편하게 하기위해 사용하지 않음
부모 노드의 인덱스가 1이 되어짐
- 트라이(Trie)
트리 자료구조의 일종으로 연관 배열을 저장하는데 사용되는 자료구조
문자열과 관련되어 있으며 검색어 관련 할때 많이 사용됨
트라이는 자식노드를 Map<Key, Value> 형태로 지니고 있음
루트 노드를 제외한 노드의 자손들은 해당 노드와 공통 접두어를 가짐
정렬된 트리구조, 데이터에 따라 이진트리일 때도 있음
'BACKEND > Data Structure & Algorithm' 카테고리의 다른 글
| 선형자료구조 - 데크/덱(Deque) (1) | 2023.05.19 |
|---|---|
| 선형자료구조 - 큐(Queue) (0) | 2023.05.18 |
| 선형자료구조 - 스택(Stack) (8) | 2023.05.16 |
| 선형자료구조 - 연결리스트(LinkedList) (1) | 2023.05.15 |
| 선형자료구조 - Array / ArrayList (0) | 2023.05.15 |