[자료구조] 선형/비선형 자료 구조

 

[자료구조] 시간 복잡도, 공간 복잡도

---

 

자료구조 복잡도에 이어서 자료구조 종류에 대해 정리해보려고 한다.

 

선형 자료 구조

요소가 일렬로 나열되어 있는 자료 구조를 말한다.

 

연결 리스트(Linked List)

데이터를 감싼 노드를 포인터로 연결해서 공간적인 효율성을 극대화시킨 자료 구조

• 삽입과 삭제는 O(1), 탐색은 O(n)이 걸린다.

 

아래의 그림처럼 prev 포인터와 next 포인터로 앞과 뒤의 노드를 연결시킨 것이 연결 리스트

연결 리스트

• 싱글 연결 리스트 : next 포인터만 가짐
• 이중 연결 리스트 : next 포인터와 prev 포인터를 가짐
• 원형 이중 연결 리스트 : 이중 연결 리스트와 같지만 마지막 노트의 next 포인터가 헤드 노드를 가리키는 것을 말함

 

배열(Array)

같은 타입의 변수들로 이루어져 있고, 크기가 정해져 있으며, 인접한 메모리 위치에 있는 데이터를 모아놓은 집합

• 중복을 허용하고 순서가 있다.
• 접근(참조)에 O(1)의 시간 복잡도를 가지며 랜덤 접근이 가능하다.
• 삽입과 삭제는 O(n)이 걸린다.

 

랜덤 접근과 순차적 접근

직접 접근이라고 하는 랜덤 접근은 동일한 시간에 배열과 같은 순차적인 데이터가 있을 때 임의의 인덱스에 해당하는 데이터에 접근할 수 있는 기능이다. 데이터를 저장된 순서대로 검색해야 하는 순차적 접근과는 반대다.

 

📌 배열과 연결 리스트 비교

배열은 상자를 순서대로 나열한 데이터 구조이며 몇 번째 상자인지만 알면 해당 상자의 요소를 끄집어낼 수 있다.
=> 랜덤 접근이 가능 
연결 리스트는 상자를 선으로 연결한 형태의 데이터 주고이며, 상자 안의 요소를 알기 위해서는 하나씩 상자 내부를 확인해봐야 한다는 점이 다르다.
=> 랜덤 접근이 불가능

그렇기 때문에 데이터 추가와 삭제를 많이 하는 것은 연결 리스트, 접근(참조)을 많이 하는 것은 배열로 하는 것이 좋다.

 

스택(Stack)

가장 마지막으로 들어간 데이터가 가장 첫 번째로 나오는 성질(LIFO, Last In First Out)을 가진 자료구조

• 재귀적인 함수, 알고리즘에 사용되며 웹 브라우저 방문 기록 등에 쓰인다.
• 삽입 및 삭제는 O(1), 탐색은 O(n)이 걸린다.

 

큐(Queue)

먼저 집어넣은 데이터가 가장 먼저 나오는 성질(FIFO, First In First Out)을 가진 자료구조

• CPU 작업을 기다리는 프로세스, 스레드 행렬 또는 네트워크 접속을 기다리는 행렬, 너비 우선 탐색, 캐시 등에 사용된다.
• 삽입 및 삭제는 O(1), 탐색은 O(n)이 걸린다.

 

데크(Deque)

스택과 큐를 합친 자료구조

• 큐의 양쪽 끝에서 삽입과 삭제가 가능하다.

 

비선형 자료 구조

일렬로 나열하지 않고 자료 순서나 관계가 복잡한 구조를 말한다.

 

그래프(Graph)

정점과 간선으로 이루어진 자료 구조

 

정점과 간선

어떠한 곳에서 어떠한 곳으로 무언가를 통해 간다고 했을 때 '어떠한 곳'은 정점(vertex)이 되고 '무언가'는 간선(edge)이 된다.

• 정점으로 나가는 간선을 해당 정점의 outdegree라고 하며, 들어오는 간선을 해당 정점의 indegree라고 한다.
• 정점은 약자로 V 또는 U라고 하며, 보통 어떤 정점으로부터 시작해서 어떤 정점까지 간다를 "U에서부터 V로 간다."라고 표현한다.

                                                                                                                          

가중치

간선과 정점 사이에 드는 비용을 뜻한다.1번 노드와 2번 노드까지 가는 비용이 한 칸이라면 1번 노드에서 2번 노드까지의 가중치는 한 칸이다.

 

트리(Tree)

그래프 중 하나로 그래프의 특징처럼 정점과 간선으로 이루어져 있고, 트리 구조로 배열된 일종의 계층적 데이터의 집합

 

트리 구조

• 부모, 자식 계층 구조를 가진다.
  • 5번 노드는 6번 노드와 7번 노드의 부모 노드이고, 6번 노드와 7번 노드는 5번 노드의 자식 노드이다.
• V - 1 = E라는 특징이 있다. 간선 수는 노드 수 - 1
• 임의의 두 노드 사이의 경로는 '유일무이'하게 '존재'한다. 즉, 트리 내의 어떤 노드와 어떤 노드까지의 경로는 반드시 있다.

이진 트리

자식의 노드 수가 두 개 이하인 트리

 

이진 탐색 트리

노드의 오른쪽 하위 트리에는 '노드 값보다 큰 값'이 있는 노드만 포함, 왼쪽 하위 트리에는 '노드 값보다 작은 값'이 들어있는 트리

 

힙(Heap)

완전 이진 트리 기반의 자료 구조

• 최대힙 : 루트 노드에 있는 키는 모든 자식에 있는 키 중에서 가장 커야 한다. 또한, 각 노드의 자식 노드와의 관계도 이와 같은 특징이 재귀적으로 이루어져야 한다.
• 최소힙 : 루트 노드에 있는 키는 모든 자식에 있는 키 중에서 최솟값이어야 한다. 또한, 각 노드의 자식 노드와의 관계도 이와 같은 특징이 재귀적으로 이루어져야 한다.

우선순위 큐

우선순위 대기열이라고도 하며, 대길열에서 우선순위가 높은 요소가 우선 순위가 낮은 요소보다 먼저 제공되는 자료 구조

• 힙을 기반으로 구현된다.

 

 

 

출처

면접을 위한 CS 전공지식 노트, 주홍철