[Data Structure] Summary 1
Seongje kim, 29 September 2020
자료구조 요약입니다.
배열(Array) vs 연결 리스트(LinkedList)
Array
고정된 크기를 가지며 인덱스를 이용하여 데이터를 삽입하거나 참조할 수 있는 선형 자료구조이다. 찾고자 하는 원소의 인덱스 값을 미리 알고 있다면 O(1)으로 접근할 수 있다. 즉, Random Access가 가능하다.
하지만 삽입/삭제 과정에서 배열의 연속적인 특징을 유지하기 위해 데이터들을 옮겨줘야 하는 비용이 발생하고, 이는 결국 O(N)의 시간복잡도를 요구한다.
LinkedList
LinkedList는 이와 같은 배열의 문제점을 해결해 줄 수 있는 자료구조이다. 각 원소는 자신의 다음 원소를 참조하면서 서로 연결되어 있고, 삽입/삭제 시 변경 사항을 저장함으로써 O(1)으로 해결된다. 하지만 특정 원소를 참조하기 위해 해당 위치를 탐색하는 과정으로부터 O(N)의 시간 복잡도를 요구하게 되고, 이는 삽입/삭제에도 적용된다.
또한, 고정된 크기를 가지고 컴파일 시점에 메모리 할당이 이루어지는 배열과 달리 런타임 시점에 동적으로 할당된다. 때문에 원소 간의 참조를 유지하기 위해 추가적인 메모리가 요구되지만 효율적으로 메모리를 사용할 수 있다.
추가적으로 LinkedList에 비해 더 나은 캐시 지역성을 가진 배열은 성능 면에서 상당한 차이를 만들 수 있다.
스택(Stack) vs 큐(Queue)
Stack
LIFO(Last In First Out)의 특성을 가지는 선형 자료구조로써 가장 최근에 추가된 원소가 맨 위에 위치한다. 이와 같은 Stack의 특성상 재귀의 방식과 유사하게 활용될 수 있다. 대표적으로 후위 표기법 계산에 사용된다.
Queue
FIFO(First In First Out)의 특성을 가지는 선형 자료구조로써 저장된 원소의 순서에 따라 처리된다. 주로 순서를 보장되는 처리를 위해 활용되며 대표적으로 OS의 프로세스 관리에 사용된다.
그래프(Graph) vs 트리(Tree)
Graph
노드(Node)와 노드들을 연결하는 간선(Edge)으로 구성된 자료구조로써 연결되어 있는 객체 간의 관계를 표현할 수 있다. 그래프는 방향성을 가질 수 있으며 사이클(Cycle)이 존재해도 무방하다. 또한 네트워크 모델로써 활용되며 간선마다 가중치가 할당될 수 있다.
표현 예 : (무)방향 그래프, (비)순환 그래프, 가중치 그래프
Tree
트리는 그래프와 마찬가지로 노드와 간선들로 구성되어 있지만 차이점이 있다. 트리는 DAG(Directed Acyclic Graph, 방향성이 있는 비순환 그래프)의 한 종류로써 계층 모델이다.
- 단 1개의 루트(Root) 노드를 가진다.
- 노드 간의 관계는 부모-자식의 관계로 표현된다. 부모는 0개 이상의 자식을 가지며 자식은 단 1개의 부모를 가진다.
- 사이클이 존재할 수 없다.
- N개의 노드를 가지는 트리는 항상 N-1개의 간선을 가진다.