선형 자료구조(linear data structure)는 연속적으로 데이터가 나열되는 자료구조를 나타낸다.
대표적인 선형 자료구조로는 배열, 리스트, 스택, 큐 등이 있다.
배열
배열(array)은 정해진 크기만큼 데이터가 일렬로 저장되는 정적 자료구조다.
각 데이터를 배열의 요소(element)라고 하며 데이터를 가리키는 번호를 인덱스(index)라고 한다.
접근 시간복잡도 : O(1)
검색시간복잡도 :O(n)
삽입시간복잡도 :O(n)
삭제시간복잡도 :O(n)
연결 리스트
연결 리스트(linked list)는 배열과 달리 크기가 정해져 있지 않은 동적(dynamic) 자료구조다.여러 개의 노드로 구성되어 있고, 노드는 데이터와 다음 노드가 저장된 주소 값을 가지고 있다.연결리스트는 헤드(head) 포인터와 테일(tail) 포인터로 시작과 끝을 알 수 있다.
검색시간복잡도 :O(n)
추가시간복잡도 : O(n)
삭제시간복잡도 :O(n)
✏️ 하나 더 알기
- 이중 연결 리스트(double linked linear list) 노드는 앞 노드의 주소값과 다음 노드의 주소 값을 모두 저장한다. ➡️ 단순 연결 리스트와는 달리 양방향 탐색이 가능하다.
장점 : 단순 연결 리스트 대비 시간 면에서 효율적이다. 단점 : 구현이 어렵고, 한 노드 당 주소 값 2개를 저장해야 해서 메모리를 많이 차지한다. - 원형 연결 리스트(circular linked linear list) 마지막 노드가 NULL 값이 아니라 첫 번째 노드의 주소값을 가리키는 구조이다.
장점 : 새로운 노드를 맨 마지막 또는 맨 앞에 삽입할 때 상수 시간 소요된다.
스택
스택(stack)은 데이터를 쌓는 형태로, 마지막에 들어온 데이터가 먼저 나가는 LIFO(후입선출)형태의 자료구조다.
스택에 데이터를 삽입하는 연산은 push라 하고,
스택에 있는 데이터를 삭제하는 연산을 pop이라고 한다.
스택의 기본 연산은 시간 복잡도 O(1)을 갖는다.
(push / pop / peek / isEmpty / isFull)
스택은 주로 어떤 작업의 실행을 취소할 때,
웹 브라우저에서 뒤로가기 할 때 등 최근에 처리한 작업들을 하나씩 꺼낼 때 사용한다.
큐
큐(queue)는 데이터가 순차적으로 들어오는 형태로, 먼저 들어온 데이터가 먼저 나가는 FIFO(선입선출) 형태의 자료구조다.
큐의 맨 앞을 front, 맨 뒤를 rear라고 한다.
큐에 데이터를 추가하면 큐의 맨 뒤에 데이터가 삽입되는 데, 이를 인큐(enqueue)라고 한다.
큐에서 데이터를 삭제하면 큐의 앞 맨앞에서 삭제되며, 이를 디큐(dequeue)라고 한다.
큐의 기본 연산은 시간 복잡도 O(1)을 갖는다.
(enqueue / dequeue / peek / isEmpty / isFull)
큐는 대표적인 예로, 운영체제에서 프로세스가 CPU를 할당받기 전까지 대기하는 준비 큐가 있다.
이 외에도 어떤한 작업을 처리할 때 작업 요청이 들어온 순서대로 처리하기 위해 주로 큐를 사용한다.
✏️ 깊게 알기
덱(deque, double-ended queue)은 양쪽 끝에서 데이터의 삽입과 삭제가 모두 가능한 자료구조로, 큐와 스택을 합친 형태다. 출처 : https://m.blog.naver.com/kisooofficial/223260970037
비선형 자료구조
비선형 자료구조(non-linear data structure)는 하나의 데이터 뒤에 N개의 데이터가 이어질 수 있는,1:N 또는 N:N 구조로 데이터가 나열되는 자료구조를 뜻한다. 계층적 구조를 나타내기에 편리하다.선형 자료구조와 달리 데이터를 하나하나 탐색하지 않아도 원하는 데이터를 찾을 수 있다.
그래프
그래프(graph)는 데이터를 포함하는 정점(vertex)과 정점을 잇는 간선(edge)으로 구성된 자료구조이다.정점은 노드(node)라고도 한다. 그래프는 G=(V, E)로 표현한다.
관련 용어
인접(adjacent) : 두 정점이 간선으로 연결되어 있으면 인접하다고 한다.
차수(degree) : 정점에 연결된 간선의 수를 나타낸다.
진입 차수(in-degree) : 해당 정점으로 향하는 간선의 수를 의미한다.
진출 차수(out-degree) : 해당 점정에서 나가는 간선의 수를 의미한다.
경로(path) : 한 정점에서 다른 정점으로 이어지는 정점들의 리스트를 뜻한다.
경로 길이(path length) : 경로를 구성하는 간선의 수다.
단순 경로(simple path) : 모두 다른 정점으로 구성된 경로를 의미한다.
사이클(cycle) : 한 정점에서 시작해 같은 정점으로 돌아올 수 있는 경로를 의미한다.
그래프의 종류
그래프는 간선의 방향성 유무에 따라 구분할 수 있다.
무방향 그래프(undirected graph)
간선에 방향성이 없는 그래프이다. 두 정점이 연결되어 있을 때 순서가 없으므로 (A, B)와 (B, A)는 동일한 간선을 의미한다. 정점의 개수가 n일 때 최대 간선의 개수는 n * (n - 1) / 2이다.
방향 그래프(directed graph)
간선에 방향이 있는 그래프이다. 두 정점이 연결되어 있을 때 A에서 B로 향하는 간선을 <A, B>로 표기한다.
따라서 <A, B>와 <B, A>는 다른 간선을 의미한다.
정점의 개수가 n일 때 최대 간선의 개수는 n * (n -1)이다.
✏️ 하나 더 알기
- 부분 그래프(sub graph) : 기존 그래프에서 일부 정점 또는 간선을 제외한 그래프 - 가중치 그래프(weighted graph) : 간선에 비용이나 가중치가 할당된 그래프 - 완전 그래프(complete graph) : 간선을 최대로 가진 그래프 - 유향 비순환 그래프(DAG, Directed Acyclic Graph) : 방향 그래프이면서 사이클이 없는 그래프
경로 탐색
시작 정점이 주어졌을 때 간선을 거쳐 모든 정점을 탐색한다.
너비 우선 탐색(BFS, Breadth-First Search)
탐색을 시작하는 정점에서 가까운 정점을 먼저 탐색하는 방식이다.
먼저 발견한 정점과 인접한 정점들을 탐색하면서 큐에 삽입한다. 탐색한 정점을 큐에 넣기 전에 이전에 방문했는지 반드시 확인해야 한다.
너비 우선 탐색을 하면 비가중치 그래프에서 시작 정점부터 특정 정점까지의 최단 거리를 알 수 있다.
깊이 우선 탐색(DFS, Depth-First Search)
시작 정점에서 탐색 가능한 최대 깊이의 정점까지 탐색한다.
만약 최대 깊이인 정점에 도달했다면 방문한 정점들을 역순으로 재방문하면서 탐색 가능한 정점이 있는지 확인한다. 탐색 가능한 정점이 있다면 해당 정점부터 다시 최대 깊이를 정점까지 탐색을 진행한다.
재귀 호출 또는 스택으로 구현할 수 있다.
트리
트리(tree)는 그래프의 한 종류로 사이클이 없어서 계층적 관계를 표현할 수 있다.
관련 용어
루트 노드(root node) : 부모 노드가 없는 노드로, 트리에는 하나의 루트 노드가 존재한다.
부모 노드(parent node) : 루트 노드 방향으로 연결한 노드다.
자식 노드(child node) : 루트 노드의 반대 방향으로 연결된 노드다.
단말 노드(leaf node) : 자식 노드가 없는 노드다.
형제 노드(sibling node) : 부모 노드가 같은 노드다.
레벨(level) : 루트 노드로부터 노드의 상대적 위치를 의미한다. 일반적으로 루트 노드의 레벨은 0이다.
높이(height) : 트리의 최대 레벨 + 1을 의미한다.
차수(degree) : 자식 노드의 개수를 나타낸다.
이진 트리
이진 트리(binary tree)는 자식 노드가 최대 2개인 트리다.
완전 이진 트리(complete binary tree)
트리의 마지막 레벨을 제외한 모든 레벨의 노드가 채워져 있으며,
마지막 레벨은 왼쪽에서부터 오른쪽으로 노드가 채워져 있는 이진 트리다.
포화 이진 트리(perfect binary tree)
트리의 마지막 레벨까지 노드가 모두 채워져 있는 이진 트리다.
따라서 완전 이진 트리라고 할 수 있다.
이진 탐색 트리(BST, Binary Search Tree)
한 노드의 왼쪽 서브 트리는 해당 노드의 값보다 작은 값을 가진 노드로 구성되고, 오른쪽 서브 트리는 해당 노드의 값보다 큰 값을 가진 노드로 구성된 트리다.
균형 잡힌 이진 탐색 트리에서는 루트 노드와 가까운 노드일수록 검색해야 하는 노드 개수가 절반으로 줄어든다.
값을 검색하는 데 O(lon n)이 소요된다. 하지만 균형이 잡히지 않은 이진 탐색 트리는 O(n)이 소요된다.
그래서 완전 이진 트리로 이진 탐색 트리를 구성하려면 균형 이진 탐색 트리(balanced BST)가 필요하다.
균형 이진 탐색 트리로 레드-블랙 트리와 AVL 트리가 있다.
우선순위 큐
우선순위 큐(priority queue)는 우선순위가 높은 데이터가 먼저 나오는 자료구조다.
데이터 삭제 연산을 수행하면 우선순위가 가장 높은 데이터를 얻을 수 있다.
우선순위 큐를 구현하는 방식은 배열, 연결 리스트, 완전 이진 트리인 힙이 있다.
힙
완전 이진 트리로, 최댓값 또는 최솟값을 빠르게 찾을 수 있는 자료구조다.
우선 순위 큐를 구현하는 데 자주 사용한다.
최대 힙(max heap) : 부모 노드의 값이 자식 노드의 값보다 크거나 같은 완전 이진 트리다.
최소 힙(min heap) : 부모 노드의 값이 자식 노드의 값보다 작거나 같은 완전 이진 트리다.
해시 테이블
해시 테이블(hash table)은 하나의 키(key)에 대해 하나의 값(value)을 저장하는 형태의 자료구조다.
